I have to compute the multiplicative inverse of $47 \mod 64$. What is the fastest way to do this?

  • 1
    PowerMod[47,-1,64] on wolfram alpha gives 15. But if you're on an exam or don't have a computer which can do modular arithmetic quickly, you should probably use euclidean algorithm. – Batman Dec 20 '15 at 13:40
  • You can use Euler's Theorem en.wikipedia.org/wiki/Euler%27s_theorem – Element118 Dec 20 '15 at 13:43
up vote 2 down vote accepted

We can use the extended Euclidean algorithm to solve for the inverse of $47 \pmod{64}$.

We use the Euclidean algorithm to solve for $\gcd(47, 64)$. \begin{align*} 64 & = 1 \cdot 47 + 17\\ 47 & = 2 \cdot 17 + 13\\ 17 & = 1 \cdot 13 + 4\\ 13 & = 3 \cdot 4 + 1\\ 4 & = 4 \cdot 1 \end{align*} Hence, $\gcd(47, 64) = 1$, so $47$ has an inverse modulo $64$.

Now, we work backwards to express $1$ as a linear combination of $47$ and $64$.
\begin{align*} 1 & = 13 - 3 \cdot 4\\ & = 13 - 3 \cdot (17 - 13)\\ & = 4 \cdot 13 - 3 \cdot 17\\ & = 4(47 - 2 \cdot 17) - 3 \cdot 17\\ & = 4 \cdot 47 - 11 \cdot 17\\ & = 4 \cdot 47 - 11(64 - 1 \cdot 47)\\ & = 15 \cdot 47 - 11 \cdot 64 \end{align*} Since $15 \cdot 47 - 11 \cdot 64 = 1$, $$15 \cdot 47 \equiv 1 + 11 \cdot 64 \equiv 1 \pmod{64}$$ Hence, $47^{-1} \equiv 15 \pmod{64}$.

Check: $15 \cdot 47 \equiv 705 \equiv 11 \cdot 64 + 1 \equiv 1 \pmod{64}$.

  • IMO the method of applying EEA in my answer is more efficient and less confusing. – user236182 Dec 20 '15 at 16:09

In a word, $47=48-1$, and we know that $(48-1)(48+1)=48^2-1\equiv-1\pmod{64}$. Thus $47^{-1}\equiv-49\equiv15\pmod{64}$.

  • Nice spot - makes my more cumbersome calculation look a bit unnecessary. +1 – Mark Bennet Dec 20 '15 at 14:08

This uses Euler's totient theorem.

By Euler's totient theorem, since $\gcd(47,64)=1$, we have:

$47^{\varphi(64)}\equiv1 \pmod{64}$, or $47^{\varphi(64)-1}\equiv47^{-1} \pmod{64}$

Since $\varphi(64)=32$ (All odd numbers less that $64$ are coprime to $64$), we can now get the multiplicative inverse via repeated squaring.

$47^2=2209\equiv33$

$47^4\equiv33^2=1089\equiv1$ (Notice that this came quite quickly. If you see a small number you are comfortable raising to higher powers, you may want to try it.)

$47^{31}=47^{4\times7}\times47^3\equiv1^7\times47^2\times47\equiv33\times47\equiv1551\equiv15\pmod{64}$

You can use the Extended Euclidean Algorithm to find $s$ and $t$ such that:

$$47s+64t=\gcd(47,64)=1$$

Then $s$ is clearly congruent to the multiplicative inverse of $47$ mod $64$.

The fact that $47=3\cdot 16-1$ suggests trying $$1\equiv(3\cdot 16 -1)(a\cdot 16 +b)\equiv (3b-a)\cdot 16-b$$ whence $b=-1$ and $a=-3$ will do, giving the inverse as $-49\equiv 15$

Apply the Extended Euclidean Algorithm to find $x,y\in\mathbb Z$ such that $64x+47y=\gcd(64,47)=1$. Subtract consecutive equations:

$$64=64(1)+47(0)\\47=64(0)+47(1)\\17=64(1)+47(-1)\\13=64(-2)+47(3)\\4=64(3)+47(-4)\\1=64(-11)+47(15)$$

Therefore $47(15)\equiv 1\pmod{64}$, so $47^{-1}\equiv 15\pmod{64}$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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