# Multiplicative Inverse Using Euler's Theorem

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?

• Well, it certainly helps to start by noting that $1989\equiv 317\pmod {836}$ From there, I suppose I'd try iterated squares. Compute $317^2$ then square that, and so on. – lulu Dec 4 '17 at 14:37
• An alternative is to split the modulus into its prime-power factors, compute the inverse modulo each of them, and assemble the results according to the Chinese remainder theorem. – Daniel Fischer Dec 4 '17 at 14:39

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.

• Thank you! I see what I was doing now! – Anonymous Dec 4 '17 at 20:53

HINT

$a^{-1}\equiv a^{360-1} \pmod {836}\equiv1989^{359} \pmod {836}$

$1989\equiv 317\pmod {836}$

$\implies a^{-1}\equiv317^{359} \pmod {836}$