Calculate the remainder of 5 to the power of 120

I was going through this thread

And the first answer made me think.

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. How to get the first line, out of nothing? I mean what is the tricks? How to come up with the number 18 in the first line?

2. I didn't understand this two line. I mean how they are calculated -

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

1 Answer

See my comment for why you use $18$ and how it relates to your previous questions.

So we want to know the remainder of $5^{120}$ when divided by $19$ and we write this as $5^{120} \mod 19$.

We know that because $(5,19)=1$ (they have no common factor greater than $1$) we have $5^{18}\equiv 1 \mod 19$ - This is because of Fermat's Little Theorem applied with $p=19$.

Since $120=18\cdot 6 + 12$, we have $5^{120}=(5^{18})^65^{12} \equiv 5^{12}\mod 19$

In a comment on one of your previous questions I noted that we could do arithmetic modulo $19$ without having to keep track of multiples of $19$ (in fact my comment was for any $p$ - and it works with a little care for any integer - division can go wrong for non-primes) - we are only interested in the remainders. We are now looking for the remainder for $5^{12}$ which we have shown is the same as that for $5^{120}$ by application of little Fermat.

Now we note that $5^{12}=(5^4)^3$. Noticing that $5^4=625$ we can get rid of some extra multiples of $19$ because $625= 32\cdot 19+ 17=33\cdot 19 -2 \equiv -2 \mod 19$. Since we want small numbers to simplify the arithmetic as much as possible we choose $-2$.

So the remainder for $5^4$ is the same as that for $-2$, and the remainder for $(5^4)^3$ is the same as for $(-2)^3=-8$.

Now there is a near convention that we choose the smallest possible positive remainder (there occasions where another choice is useful*). So we note that $-8=11-1\cdot 19\equiv 11 \mod 19$ to finish off.

I suggest that now you have asked a few questions about this, you try some examples for yourself. You need to get used to the language a bit - you will have noticed how naturally it comes to the people who have been posting answers and comments - and how much longer I had to make this answer to avoid using it.

*eg some proofs of quadratic reciprocity