# modular arithmetic with a very big number

I need to compute $147^{65}\pmod{679}$. I need to get it to be congruent to a number less than $676\pmod{679}$. Anyone who can help? I tried the power of $2$ trick but I couldn't make it work.

• Since $679 = 7\cdot 97$, one thing you could do is calculate $147^{65}\mod 7$ and $147^{65}\mod 97$ and then use those results to get the final answer from the Chinese Remainder Theorem.
– MJD
Oct 23 '13 at 7:20

First, we have $$147^2 \equiv 560 \pmod{679}$$ This gives us $$147^4 \equiv 560^2 \pmod{679} \equiv 581 \pmod{679}$$ which in turn gives us $$147^8 \equiv 581^2 \pmod{679} \equiv 98 \pmod{679}$$

Now note that $98^2 \equiv 98 \pmod{679}$. This implies $98^n \equiv 98 \pmod{679}$.

Hence, $$147^{8n+1} \equiv 98^n \cdot 147 \pmod{679} \equiv 98 \cdot 147 \pmod{679} \equiv 147 \pmod{679}$$

You could brute force: $147^2 \equiv 560 \mod 679$.

Similarly, $560^2 \equiv 581 \mod 679$ and $581^2 \equiv 98 \mod 679$.

This has already involved far too much computation, but you are pretty much done now.

We find $98\cdot 98 \equiv 98 \mod 679$, so we put the pieces together as follows:

$147^8 \equiv 98 \mod 679$ hence $147^{64} \equiv (147^8)^8 \equiv 98^8 \equiv 98 \mod 679$.

A final multiplication by $147$ gives the answer: $147^{65} \equiv 147 \cdot 98 \equiv 147 \mod 679$.

• So how would you solve a modular problem if we didn't get a number congruent to itself. for example 579^65 mod 679 is a case where it doesnt happen. I followed you steps until i got to 275^2 is congruent to 256 mod 679. Now I'm stuck Oct 23 '13 at 3:34
• You can still do it by brute force pretty fast in this case. Three squarings got you to the eighth power: another 3 squarings will get you to the 64th power and you are almost done. Oct 23 '13 at 3:47