How to determine the multiplicative inverse modulo 64 (or other power of two)? I am trying to determine the multiplicative inverse of $47$ modulo $64$. So I have looked for an algorithm or scheme in order to perform this.

I found this wiki explaining how to find a multiplicative inverse. I tried to perform all the calculations, but the result was incorrect. I got $5$ as a multiplicative inverse, but this cannot be true: $47\times5\not\equiv1\pmod{64}$. Who can help me?
A boring method is to carefully apply the (partially) extended Euclidean algorithm.



But in the question, the modulus is a power of two (specifically $2^6$), and we can use that
$$a\,x\equiv1\pmod{2^k}\implies a\,x\,(2-a\,x)\equiv1\pmod{2^{2k}}$$
from which it follows this fact:


  if the modular inverse of $a$ modulo $2^k$ is (the lower $k$ bits of) $x$, then
  the modular inverse of $a$ modulo $2^{2k}$ is (the lower $2k$ bits of) $x\,(2-a\,x)$
  (where negative integers are in 2's-complement convention, dominant in modern CPUs).


This not-so-much-known fact allows computation of multiplicative inverse modulo $2^k$. We start from an inverse $x$ of $a$ over few bits (that can be $x=a$, perhaps $\bmod 7$, which is the inverse for any odd $a$ over three bits), and iterate $x\gets x\,(2-a\,x)$, possibly truncated to the number of known-correct result bits. That number of bits doubles at each iteration, thus about $\log_2(k)$ steps are enough, and it is only used product, subtraction, and bit truncation on values no wider than $k$ bits. That is blindingly fast compared to the Euclidean algorithm's $O(k)$ steps; and eases getting data-independent execution time, which comes handy in some cryptographic computations (e.g. the preliminary computation of $m'$ in Montgomery multiplication, algorithm 14.36 of Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography).

I learned the technique from Colin Plumb's Computing multiplicative inverses (post on sci.crypt with Message-ID: &lt;1994Apr6.093116.27805@mnemosyne.cs.du.edu>, 1994). His statement applies to inverse modulo a prime power, and points the relation to the Newton's iteration for finding $x = 1/a$ in $\Bbb R$.

A modern exposition, with benchmarks, is in Jean-Guillaume Dumas: On Newton-Raphson iteration for multiplicative inverses modulo prime powers.

A bibliography, and other techniques faster than the Euclidean algorithm, are in Çetin Kaya Koç: A New Algorithm for Inversion mod $p^k$. 



Here, to perform the desired computation quickly, we use $k=3$, $a=47$, and compute $a\bmod2^k=47\bmod8=7$, which multiplicative inverse modulo $8$ is also $x=7$. Now we compute
$$\begin{align}
(x\,(2-a\,x))\bmod2^{2k}&amp;=(7\,(2-47\times7))\bmod 64\\
&amp;=15\end{align}$$

Hence the desired modular inverse of $47$ modulo $64$ is $15$.