Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
I didn't understand how you calculated in the first line. Please explain. –  Man_From_India Apr 1 at 15:11
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.