Explanation of argument: inverse of a $p$-adic integer

Question

Let $a=a_0+a_1p+a_2p^2+\cdots$ be a $p$-adic integer with $0\le a_i<p$ and $a_0\neq 0$.

Then $a$ has multiplicative $p$-adic inverse $c_0+c_1p+c_2p^2+\cdots$ with $0\le c_i<p$, and is obtained as follows: the following arguments are from Algebra by Mac Lane and Birkhoff. I could not understand them, so can anybody explain it?

• $a_0c_0\equiv 1\pmod p$ i.e. $a_0c_0-1=b_1p$.

• $a_0c_1+a_1c_0+b_1\equiv 0\pmod{p}$ i.e. $a_0c_0+(a_0c_1+a_1c_0)p-1=p^2b_2$.

• $\cdots$

• $a_0c_k+a_1c_{k-1}+\cdots + a_kc_0+b_k\equiv 0\pmod{p}$ i.e. $a_0c_0 + (a_0c_1+a_1c_0)p+\cdots + (a_0c_k+\cdots + a_kc_0)p^k-1=p^{k+1}b_{k+1}$.

---

I got only first step: $a_0\neq 0\pmod p$ so it has inverse in $\mathbb{Z}/p$, so we get $c_0\in \{1,2,\ldots,p-1\}$ with $a_0c_0\equiv 1 \pmod{p}$, so $a_0c_0=1+b_1p$. Then $b_1$ is carry.

Next steps, unclear to me.

Answer 1

Expanding on the idea in the comments, to view this as ordinary division: We are trying to compute $1/a$ with $a = a_0 + a_1 p + a_2 p^2 + \dots$.

Write $1 = 1 + 0 p + 0 p^2 + \dots$, and set up the long division $$ \begin{array}{l r} & \underline{~~\; \phantom{aaaaaaaaaaaaaaa}} \\ a_0 + a_1 p + a_2 p^2 + \dots & \big) ~ 1 + 0p + 0p^2 + \dots \\ & \end{array} $$ To execute the first step, we look for a number $c_0$ that makes $a_0 c_0 = 1$, except of course our digits work modulo $p$< so really we want $a_0 c_0 \equiv 1 \pmod{p}$, or as you say $a_0 c_0 - 1 = b_1 p$ for some integer $b_1$.

Hence the next step becomes: $$ \begin{array}{l l} & \underline{~~\; c_0 \phantom{aaaaaaaaaaaaa}} \\ a_0 + a_1 p + a_2 p^2 + \dots & \big) ~ 1 + 0p + 0p^2 + \dots \\ & ~~\; a_0 c_0 + a_1 c_0 p \end{array} $$ which given the above relation is the same as $$ \begin{array}{l l} & \underline{~~\; c_0 \phantom{aaaaaaaaaaaaa}} \\ a_0 + a_1 p + a_2 p^2 + \dots & \big) ~ 1 + 0p + 0p^2 + \dots \\ & \underline{~~\; 1 + (b_1 + a_1 c_0) p} \\ & ~~\;~~\; -(b_1 + a_1 c_0)p \end{array} $$

Thus our goal in the next step is to multiply $a = a_0 + a_1 p + a_2 p^2 + \dots$ by something so that the leading term matches $-(b_1 + a_1 c_0) p$. It has to be a multiple of $p$ for the power of $p$ to match, so call it $c_1 p$: $$ \begin{array}{l l} & \underline{~~\; c_0 + c_1 p \phantom{aaaaaaaa}} \\ a_0 + a_1 p + a_2 p^2 + \dots & \big) ~ 1 + 0p + 0p^2 + \dots \\ & \underline{~~\; 1 + (b_1 + a_1 c_0) p} \\ & ~~\;~~\; -(b_1 + a_1 c_0)p \\ & ~~\;~~\; a_0 c_1 p + a_1 c_1 p^2 \end{array} $$ We want the leading terms to cancel when we subtract (that's the point of the division algorithm!) so here the goal has to be $$ -(b_1 + a_1 c_0) \equiv a_0 c_1 \pmod{p}, $$ or in other words $a_0 c_1 + a_1 c_0 + b_1 \equiv 0 \pmod{p}$. This explain the second bullet in their argument.

Continue from there! You might find it instructive to carry the process out with some concrete numbers and see that there's nothing mysterious going on here, it just looks a bit of a mess because of the many variables.