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

share|improve this question

2 Answers 2

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

share|improve this answer
    
...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

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.

share|improve this answer

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.