# Thread: x and x^5 have the same final digit

1. ## 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?

2. 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.

3. 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, $\displaystyle x^{\varphi(n)} \equiv x (\bmod n)$
Here, n=10. So $\displaystyle \varphi(n)=1 \cdot 4=4$

Hence for any x, $\displaystyle x^4 \equiv x (\bmod 10)$
This means that they have the same last digit

4. No, no. It’s $\displaystyle x^{\phi(n)}\equiv1\pmod n$ provided $\displaystyle \gcd(x,n)=1.$

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

You still have to check the cases $\displaystyle x=2,4,5,6,8$ by other methods.

5. Okay, for 1, 3, 7, 9, you apply $\displaystyle \phi(10)=4$ as above.

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

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

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

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

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

Hence $\displaystyle x^5\equiv x\pmod{10}$ for $\displaystyle 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.

6. 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).

7. 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 $\displaystyle 3$ is a primitive root module $\displaystyle 29$

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

Now, we have: $\displaystyle \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 $\displaystyle q$

And $\displaystyle \tfrac{{q - 1}} {2}$ non-quadratics residues module q. (if $\displaystyle g$ is a primitive root module q they are of the form $\displaystyle 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 $\displaystyle q\equiv{1}(\bmod.4)$ it follows that $\displaystyle x^2 \equiv - 1\left( {\bmod .q} \right)$ is soluble and has 2 incongruent solutions. For which $\displaystyle 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: $\displaystyle 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)$ $\displaystyle \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 $\displaystyle x^2 \equiv - 1\left( {\bmod .q} \right)$ are primitive roots!

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

Now in our case it remains to check that $\displaystyle 3^2 \not\equiv - 1\left( {\bmod .29} \right)$ which indeed holds !

8. 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 ?

9. 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

10. Since 3 is a primitive root, $\displaystyle x\equiv 3^k$ for some k (if such a solution exists), hence $\displaystyle 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 $\displaystyle 28s=5k+1$ (1) for some $\displaystyle s\in \mathbb Z$. Read this equation mod 5, we have $\displaystyle 3s\equiv 1 (\bmod.5)$ if and only if $\displaystyle 3s\equiv 1+5 =6(\bmod.5)$ thus, dividing through by 3 which is coprime to the module: $\displaystyle s\equiv 2 (\bmod.5)$ thus $\displaystyle s=5m+2$

Substitute this back into (1) to get $\displaystyle 28\cdot 5\cdot m +56 = 5k+1$ thus $\displaystyle 28\cdot 5\cdot m +55 = 5k$ divide by 5: $\displaystyle 28m+11=k$ thus $\displaystyle 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 $\displaystyle g^{\tfrac{\phi(n)}{2}}\equiv -1 (\bmod.n)$ (3)

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

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

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

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

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

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