|
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. |
||||
|
|
|
Hint: Use Fermat's Little Theorem to find the period of $[20]_{251}$. Then, use this to simplify $20^{1234567}$. |
|||||||||||
|
|
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. |
|||
|
|
