0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lulu Dec 4 '17 at 14:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Daniel Fischer Dec 4 '17 at 14:39
1
$\begingroup$

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.

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

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

$\endgroup$

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.