1
$\begingroup$

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.

3 Answers 3

4

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

1

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.

  • 0
    I didn't understand how you calculated in the first line. Please explain.2014-04-01
0

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$