# Thread: Mods

1. ## Mods

1.) By using mods: for any pos. integer n, show n^5 has the same last digit as n.

2.) Again, using mods, show if gcd(n,100) = 1, then n^41 has the same last 2 digits as n. Explain if it is true for ALL n, that n and n^41 have the same last 2 digits.

2. Originally Posted by Ideasman
1.) By using mods: for any pos. integer n, show n^5 has the same last digit as n.

.
When you are working with the last digits you work mod 10.

When, let n be any arbitary integer.
Thus, (by division algorithm),
N=0,1,2,3,4,5,6,7,8,9 (mod 10).

Meaning, N has to be congruent to exaclty one of those numbers, i.e. that are the possible endings for the integer.

Then, by inspection, we see that, by mod 10,
0^5 = 0
1^5 = 1
2^5 = 2
3^5 = 3
4^5 = 4
5^5 = 5
6^6 = 6
7^5 = 7
8^5 = 8
9^5 = 9

Hence, n^5 is congruent to the same number under mod 10.

Q.E.D.

3. Originally Posted by Ideasman

2.) Again, using mods, show if gcd(n,100) = 1, then n^41 has the same last 2 digits as n. Explain if it is true for ALL n, that n and n^41 have the same last 2 digits.
By Euler Elegant Generalization of the Super Little Theorem of the Cool Fermat, we have that,

a^{phi(n)} = 1 (mod n)

In this case let n=100.
Thus, phi(100)=40.
Thus,
a^{40} = 1 (mod 100)
Where gcd(a,n)=100.
Then, multiplication by "a" yield,
a^{41} = a (mod 100}
Thus they have the same last two digits for they are congruent to each other.

----
Consider n=2. The last two digits are 02 (if that is how you want to think of it).

Then, n^41=2199023255552
Where the last two digits are 52.
It fails.

Note gcd(2,100) not = 1.