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
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,
Here, n=10. So
Hence for any x,
This means that they have the same last digit
here (it's pretty much the same)
Here there's an interesting way to see that is a primitive root module
First note that , so, more generally consider the primes of the form with prime
Now, we have: primitive roots module
And non-quadratics residues module q. (if is a primitive root module q they are of the form 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 it follows that is soluble and has 2 incongruent solutions. For which thus by Euler's criterion both solutions are non-quadratic residues.
But: 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 are primitive roots!
3 is a non-quadratic residue mod 29 since (the rest follows by Euler's Criterion). We may also do this by applying the Quadratic Reciprocity Theorem, indeed: hence and since it follows that and it's a non-quadratic residue
Now in our case it remains to check that which indeed holds !
Since 3 is a primitive root, for some k (if such a solution exists), hence and this happens if and only if 28 divides 5k+1, again because 3 is a primitive root module 29.
Okay, we have (1) for some . Read this equation mod 5, we have if and only if thus, dividing through by 3 which is coprime to the module: thus
Substitute this back into (1) to get thus divide by 5: thus (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 (3)
Okay, it should be easy to note that now multiply by (by (3) ) hence
Now, since 3 is a primitive root, it follows that if and only if
So if and only if
We can now also simplify (2) fastly using property (3), we have
Again which is evidently since
Thus we get