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?
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.
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
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.
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.
Read the thread here (it's pretty much the same)
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 !
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)$