Find the multiplicative inverse of 1989 (mod 836) using Euler's Theorem.
Euler's Theorem:
$a^{-1} \pmod n = a^{\phi(n)-1} \pmod n$
I know the $\phi(836) = 360$.
Plugging that back in I get:
$=a^{360-1} \pmod {836}=1989^{359} \pmod {836}$
…and I'm stuck here. I know I'm suppose to split up the exponent (strategically) so that it makes it easier to solve, but all the video and notes provided online skip the explanation of how you know what numbers to split up the exponent into.
Can someone please explain this to me?
Best Answer
First of all, there's no reason to work with the number $1989$ modulo $836$. We can reduce it, and obtain $1989\equiv 317$, so $1989^{359}\equiv 317^{359}$.
Now, we can write $359$ in binary: $359=101100111_2$. Thus, we want $317^{1+2+4+32+64+256}$. Squaring repeatedly, we obtain:
$317^1\equiv 317\\ 317^2\equiv 169\\ 317^4\equiv 137\\ 317^8\equiv 377\\ 317^{16}\equiv 9\\ 317^{32}\equiv 81\\ 317^{64}\equiv 709\\ 317^{128}\equiv 245\\ 317^{256}\equiv 669\\ $
It appears the number you want is equivalent to $669\times709\times81\times137\times169\times317$.
If you've seen a specific solution breaking up the exponent in some other way, feel free to post a link, and we can probably help explain what is happening.