I need help in the use of Fermat’s Little Theorem, in order to calculate the remainder of $5^{120}$ when divided by 19.
Thank you.
Fermats Little Theorem
3 Answers
Fermat's Little Theorem tells us that $5^{18} = 1$ mod $19$.
Observe next that $5^{120} = (5^{18})^6 \cdot 5^{12}$.
Reducing modulo $19$, we have $5^{120} = 1^{6} \cdot 5^{12} = 5^{12}$ mod $19$.
All that's left now is to calculate $5^{12}$ mod $19$, which can be done quickly by brute force.
For example, $5^4 = 625 = 608 + 17 = 32\cdot19 + 17 = -2$ mod $19$.
Then $5^{12} = (5^4)^3 = (-2)^3 = -8$ mod $19$, which is the same as $11$ mod $19$.
And there you have it: the remainder is $11$.
The powers of $5$ modulo $19$ go like (starting with exponent $0$:) $1,5,6, -8, -2, 9,... $ (I calculated like, for example $6\cdot 5=30=19+11\equiv 11 \equiv -8$, and $-8\cdot 5=-40=-38-2$, etc.)
Continue. At most the $18^{th}$ is going to be $1$ again.
-
0I didn't understand how you calculated in the first line. Please explain. – 2014-04-01
Start with $ 5^{120}\bmod 19=(5^6)^{18}5^{12}\bmod 19, $ then FLT says $a^{p-1}\equiv 1\bmod p$. Therefore we continue $ =1\cdot 5^{12}\bmod 19=(5^3)^4 \bmod 19= (125)^4 \bmod 19 \\ = 11^3\cdot11 \bmod 19= (70\cdot19+1)\cdot11\bmod 19 = 11 $
You recognize that there exists smaller periods than $p-1$ from the FLT: $11^3\equiv 1 \bmod 19$