Multiplicative inverse of $47 \mod 64$.

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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$

Answer 6

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