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.
Asked
Active
Viewed 95 times
1
-
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 07:20
2 Answers
1
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}$$
0
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$.
Benjamin Dickman
- 14,451
-
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 – user2510809 Oct 23 '13 at 03: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. – Penguino Oct 23 '13 at 03:47