3

My question relates to inverses modulo $p^k$ for prime $p$.

I came across an article that gave a recurrence relation for computing inverses modulo $p^{2^n}$, but it did not make clear how (or even if) they might be combined to produce the inverse modulo an arbitrary power $k$.

The recurrence relation in question is $U_0 = a^{-1}$ mod $p$, then $U_{n+1} = U_n(2 - aU_n)$, which produces $U_n = a^{-1}$ mod $p^{2^n}$.

But how would I calculate $a^{-1}$ mod $p^5$, say?

Jim White
  • 616

1 Answers1

3

Hint: If $b$ is the inverse of $a$ modulo $p^8$, then $b$ (if you wish reduced modulo $p^5$) is the inverse of $a$ modulo $p^5$.

André Nicolas
  • 507,029
  • Well thank you very much! That simple fact seems to have eluded me thus far. Can you give me a reference to where I might find why that is so? – Jim White Dec 04 '14 at 16:41
  • 1
    No reference needed. If $p^8$ divides $ab-1$, then $p^5$ divides $ab-1$, so $ab\equiv 1\pmod{p^5}$. In general, if you want the inverse modulo $p^k$, use the algorithm to compute the inverse $b$ modulo $p^{2^e}$, where $2^e$ is the smallest power of $2$ that is $\ge k$. Then $ab\equiv 1\pmod{p^k}$, so $b$ is the inverse of $a$ modulo $p^k$. The point is that we can use the algorithm to climb "fast." – André Nicolas Dec 04 '14 at 16:46
  • Understood, thank you very much! – Jim White Dec 04 '14 at 16:52
  • You are welcome. The only fact that is used is that if $x\equiv y\pmod{n}$ then $x\equiv y\pmod{m}$ for any divisor $m$ of $n$. – André Nicolas Dec 04 '14 at 16:56