Calculate $20^{1234567} \mod 251$

Question

I need to calculate the following

$$20^{1234567} \mod 251$$

I am struggling with that because $251$ is a prime number, so I can't simplify anything and I don't have a clue how to go on. Moreover how do I figure out the period of $[20]_{251}$? Any suggestions, remarks, nudges in the right direction are very appreciated.

score 3 · Answer 1 · answered Jan 28 '13 at 18:01

3

Hint: Use Fermat's Little Theorem to find the period of $[20]_{251}$. Then, use this to simplify $20^{1234567}$.

answered Jan 28 '13 at 18:01

Joe Z.

6,719

...and then you're left with $20^{67} \bmod 251$. – Fly by Night Jan 28 '13 at 18:27
1

Then do some exponentiation by squaring. – Joe Z. Jan 28 '13 at 18:30
How does that help? – Fly by Night Jan 28 '13 at 18:37
If you square 20 six times, then multiply by 400 and then by 20, taking the factor mod 251 each time, you will have calculated $20^{67}$ modulo 251. – Joe Z. Jan 28 '13 at 19:00

score 1 · Answer 2 · answered Jan 28 '13 at 18:36

If you do not know the little theorem, a painful but -I think- still plausible method is to observe that $2^{10} = 1024 \equiv 20$, and $10^3 = 1000 \equiv -4$. Then, we may proceed like this:

$20^{1234567} = 2^{1234567}10^{1234567} = 2^{123456\times 10 + 7}10^{411522\times 3 + 1} = 1280\times 1024^{123456}1000^{411522} \equiv 1280\times 20^{123456}4^{411522}$.

Observe that after one pass, we are still left with the powers of $2$ and the powers of $20$ that we can handle with the same equivalences above.

We still have to make some calculations obviously (divisions etc), but it is at least not as hopeless as before.

Calculate $20^{1234567} \mod 251$

2 Answers2

Linked