= Modular inversion converges to a p-adic inverse
{title2=$r_n\equiv a^{-1}\pmod{p^n}\ \Longrightarrow\ r_n\to a^{-1}$}
Let $a$ be an <integer> not divisible by $p$. Its <modular inverse> modulo $p^n$ has a unique least nonnegative representative $r_n$. Reducing the inverse equation modulo $p^n$ shows that the representatives are compatible. Since $a$ is a <p-adic unit>,
$$
|r_n-a^{-1}|_p=|ar_n-1|_p\leq p^{-n},
$$
so the sequence converges to the inverse $a^{-1}$ in $\mathbb Z_p$. This computes a fraction through finite <integer> operations.
For $a=3$ and $p=2$, the first eight representatives are \b[$1,3,3,11,11,43,43,171$]. Each satisfies $3r_n\equiv1\pmod{2^n}$. The resulting expansion is
$$
\boxed{\frac13=1+2+8+32+\cdots
=1+\sum_{k\geq0}2^{2k+1}\quad\text{in }\mathbb Z_2.}
$$
The <geometric series> has ratio $4$, whose <2-adic absolute value> is $1/4$, and its sum is $1+2/(1-4)=1/3$. In the ordinary <real number> <absolute value>, the representatives grow. Different <metrics> impose different meanings of a good approximation. The periodic digits here are a specific instance of the rational expansions studied in Conrad's authored note.<The p-adic expansion of rational numbers by Keith Conrad>[§1, printed p. 1: p-adic rational expansions and explicit low-order-first convention; §3, Theorem 3.1, printed pp. 3–5: eventual periodicity]{ref}
\Image[/padic-inverse-three-finite-precision-errors.png]
{title=Finite modular inverses approximate one third in the 2-adic metric}
{description=Original exact least nonnegative inverses of $3$ modulo $2^n$. The left panel plots $|r_n-1/3|_2$ and the bound $2^{-n}$. The right plots the ordinary real error $|r_n-1/3|$. Equal neighbouring representatives arise when the next binary digit is zero, so their exact errors also agree.}
Back to article page
