# x and x^5 have the same final digit

• Feb 17th 2009, 08:19 AM
mathisthebestpuzzle
x and x^5 have the same final digit
This seems as though it is a simple problem....but i'm stuck.

Prove that x and x^5 have the same final digit for any integer x.

is this done by induction?
• Feb 17th 2009, 08:42 AM
oswaldo
This may not be the most ellequent proof but actually you enumerate this easily. Because there are only 10 possibilities for last digit. You can write last digit for x^2 then for x^4 and finally x^5. Last digits upto 4:

x x^2 x^4 x^5
0 0 0 0
1 1 1 1
2 4 6 2
3 9 1 3
4 6 6 4
...
9 1 1 9

-O

Do not let the theory murder practice.
• Feb 17th 2009, 09:56 AM
Moo
The last digit represents the congruence modulo 10.

If x=0 mod 10, then x^5=0 mod 10
If x=1 mod 10, then x^5=1 mod 10
If x=2 mod 10, then x^5=32 mod 10=2 mod 10
and so on...

Also, there is another way, if you've Studied Euler's theorem :
For any x, $x^{\varphi(n)} \equiv x (\bmod n)$
Here, n=10. So $\varphi(n)=1 \cdot 4=4$

Hence for any x, $x^4 \equiv x (\bmod 10)$
This means that they have the same last digit
• Feb 17th 2009, 02:17 PM
JaneBennet
No, no. It’s $x^{\phi(n)}\equiv1\pmod n$ provided $\gcd(x,n)=1.$

Hence $x^5\equiv x\pmod{10}$ when $x=1,3,7,9.$

You still have to check the cases $x=2,4,5,6,8$ by other methods.
• Feb 17th 2009, 02:45 PM
JaneBennet
Okay, for 1, 3, 7, 9, you apply $\phi(10)=4$ as above.

For the even digits, try $\phi(5)=4.$

So $y^4\equiv1\pmod 5$ for $y=1,2,3,4.$

$\therefore\ 2^4y^4\equiv16\pmod 5\equiv1\pmod 5$

$\Rightarrow\ 2^5y^4\equiv2\pmod{10}$ (multiply through by 2)

$\Rightarrow\ (2y)^5\equiv2y\pmod{10}$

Hence $x^5\equiv x\pmod{10}$ for $x=2y=2,4,6,8.$

Finally, any power of any integer ending in 5 also ends in 5 and any power of any integer ending in 0 also ends in 0.
• Feb 17th 2009, 02:47 PM
mathisthebestpuzzle
would you happen to know how to use discrete logarithms to find all solutions to the congruences 3x^5 = 1 (mod 29) and
3^x = 2 (mod 29).
• Feb 17th 2009, 05:46 PM
PaulRS
Quote:

Originally Posted by mathisthebestpuzzle
would you happen to know how to use discrete logarithms to find all solutions to the congruences 3x^5 = 1 (mod 29) and
3^x = 2 (mod 29).

Here there's an interesting way to see that $3$ is a primitive root module $29$ (Happy)

First note that $
29 = 4 \cdot 7 + 1
$
, so, more generally consider the primes $q$ of the form $
q = 4 \cdot p + 1
$
with $p>2$ prime

Now, we have: $
\phi \left( {q - 1} \right) = \phi \left( {4p} \right) = \phi \left( 4 \right) \cdot \phi \left( p \right) = 2 \cdot \left( {p - 1} \right) = \tfrac{{q - 1}}
{2} - 2
$
primitive roots module $q$

And $
\tfrac{{q - 1}}
{2}
$
non-quadratics residues module q. (if $
g
$
is a primitive root module q they are of the form $g^{2s+1}$ and that is sufficient )

Every primitive root is a non-quadratic residue (here), thus all quadratic residues save for 2 of them are primitive roots.

Since $
q\equiv{1}(\bmod.4)
$
it follows that $
x^2 \equiv - 1\left( {\bmod .q} \right)
$
is soluble and has 2 incongruent solutions. For which $
x^2 \equiv - 1\left( {\bmod .q} \right) \Rightarrow x^{\tfrac{{q - 1}}
{2}} = \left( {x^2 } \right)^{\left( {\tfrac{{q - 1}}
{4}} \right)} \equiv \left( { - 1} \right)^{\left( {\tfrac{{q - 1}}
{4}} \right)} = - 1\left( {\bmod .q} \right)
$
thus by Euler's criterion both solutions are non-quadratic residues.

But: $
x^2 \equiv - 1\left( {\bmod .q} \right) \Rightarrow x^2 \cdot x^{\tfrac{{q - 1}}
{2}} \equiv \left( { - 1} \right) \cdot \left( { - 1} \right) = 1\left( {\bmod .q} \right)
$
$
\Rightarrow x^{\tfrac{{q + 1}}
{2}} \equiv \left( { - 1} \right) \cdot \left( { - 1} \right) = 1\left( {\bmod .q} \right)
$
thus, the 2 incongruent solutions are non-quadratic residues and are not primitive roots!

Hence all the non-quadratic residues mod. q save from the solutions to $
x^2 \equiv - 1\left( {\bmod .q} \right)
$
are primitive roots!

3 is a non-quadratic residue mod 29 since $29|(3^{14}+1)$ (the rest follows by Euler's Criterion). We may also do this by applying the Quadratic Reciprocity Theorem, indeed: $\left(\tfrac{3}{29}\right)_L\cdot\left(\tfrac{29}{ 3}\right)_L=(-1)^{\tfrac{29-1}{2}\cdot \tfrac{3-1}{2}}=1$ hence $\left(\tfrac{3}{29}\right)_L=\left(\tfrac{29}{3}\r ight)_L$ and since $\left(\tfrac{29}{3}\right)_L\equiv{29^{\tfrac{3-1}{2}}}\equiv{-1}(\bmod.3)$ it follows that $\left(\tfrac{3}{29}\right)_L=-1$ and it's a non-quadratic residue

Now in our case it remains to check that $
3^2 \not\equiv - 1\left( {\bmod .29} \right)
$
which indeed holds ! (Happy)
• Feb 17th 2009, 08:05 PM
mathisthebestpuzzle
i need more explanation.

so 3x^5 is congruent to 1 mod 29

then x is congruent to 3^k mod 29

3x^5 is congruent to 3^5k+1 is congruent to 1 mod 29

3 is a primitive root iff 28|5k+1 ?

• Feb 17th 2009, 08:24 PM
mathisthebestpuzzle
ok, so i just checked the primitive roots of 29. until i found that

15^5 is congruent to 10 mod 29.

therefore x is congruent to 15 mod 29.

How do i solve the second congruence?

3^x is congruent to 2 mod 29.?!?!?1
• Feb 18th 2009, 05:13 AM
PaulRS
Since 3 is a primitive root, $x\equiv 3^k$ for some k (if such a solution exists), hence $3^{5k+1}\equiv 1 (\bmod.29)$ and this happens if and only if 28 divides 5k+1, again because 3 is a primitive root module 29.

Okay, we have $28s=5k+1$ (1) for some $s\in \mathbb Z$. Read this equation mod 5, we have $3s\equiv 1 (\bmod.5)$ if and only if $3s\equiv 1+5 =6(\bmod.5)$ thus, dividing through by 3 which is coprime to the module: $s\equiv 2 (\bmod.5)$ thus $s=5m+2$

Substitute this back into (1) to get $28\cdot 5\cdot m +56 = 5k+1$ thus $28\cdot 5\cdot m +55 = 5k$ divide by 5: $28m+11=k$ thus $x=3^{28m+11}=(3^{28})^m\cdot 3^{11}\equiv 3^{11} (\bmod. 29)$ (2)

Now let's go to the second question.

First I'll remark a property of the primitive roots which will fasten the calculations.

Let g be a primitive root module n, then $g^{\tfrac{\phi(n)}{2}}\equiv -1 (\bmod.n)$ (3)

Okay, it should be easy to note that $3^3=27\equiv{-2}(\bmod.29)$ now multiply by $3^{14}\equiv{-1}(\bmod.29)$ (by (3) ) hence $3^{17}\equiv{2}(\bmod.29)$

Now, since 3 is a primitive root, it follows that $3^a\equiv 3^b (\bmod. 29)$ if and only if $a\equiv b (\bmod. 28)$

So $3^x\equiv 2 (\bmod. 29)$ if and only if $x\equiv 17 (\bmod.28)$

We can now also simplify (2) fastly using property (3), we have $3^{11}\equiv{3^{14}3^{-3}}\equiv (-1)\cdot (3^3)^{-1}(\bmod.29)$

Again $(3^3)^{-1}\equiv (-2)^{-1}(\bmod.29)$ which is evidently $-15$ since $(-2)\cdot (-15)=30=29+1$

Thus we get $3^{11}\equiv 15 (\bmod.29)$