Fermats Little Theorem

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.

-

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.

-
I didn't understand how you calculated in the first line. Please explain. –  Man_From_India Apr 1 '14 at 15:11

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$

-