Fermats Little Theorem

Question

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.

Answer 1

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$.

Answer 2

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$

Answer 3

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.