0
$\begingroup$

So, I've figured out that: $12 \equiv 2 \mod 10$

And hence,

$$ 12^{157} \equiv 2^{157} \mod 10$$

I thought of expanding out $2^{157} = 2^{156} \cdot 2 = 4^{78} \cdot 2 = 16^{39} \cdot 2$, then I could write: $$ 12^{157} \equiv 2^{157} \equiv 16^{39} \cdot 2 \equiv 6^{39} \cdot 2 \equiv 36^{19}\cdot 12\equiv 6^{19} \cdot 2 \equiv 36^9 \cdot 12 \equiv 6^9 \cdot 2 \equiv 36^4 \cdot 12 \equiv 6^4 \cdot 2 \equiv 72 \cdot 36 \equiv 2 \cdot 6 \equiv 2 $$

This is quite a long process. I found that you could use fermats little theorem to speed up the case when the number we taking mod with is prime, however are there any theorems/methods which can be used to speed up calculations when we take a composite numbers?

$\endgroup$
2
  • 3
    $\begingroup$ You can use the fact that $2^5=32\equiv 2 = 2^1 \bmod 10$. $\endgroup$ Mar 15 '21 at 8:30
  • $\begingroup$ Same as in the dupes (the mod Distributive Law is generally the easiest way to do such computations). $\endgroup$ Mar 15 '21 at 8:43
2
$\begingroup$

You could use Fermat`s Little Theorem and Chinese Remainder Theorem together.

Note that

$12^{157} \equiv 0 \pmod{2} \Rightarrow 12^{157}=2k$

$12^4 \equiv 1 \pmod{5} \Rightarrow 12^{157} \equiv 2 \pmod{5}$

$2k \equiv 2\pmod{5} \Rightarrow k \equiv 1 \pmod{5}$

$k \equiv 1 \pmod{5} \Rightarrow k=5x+1 $ so $12^{157}=2k=10x+2 \equiv 2 \pmod{10}$

$\endgroup$

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