1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – MJD
    Oct 23 '13 at 7:20
1
$\begingroup$

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}$$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Oct 23 '13 at 3:34
  • $\begingroup$ 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. $\endgroup$
    – Penguino
    Oct 23 '13 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.