Computation of the inverse of a $p$-adic integer in $\mathbb{Z}_p^{*}$

Question

Let $c \in \mathbb{Z}_p^{*}$, i.e. $\left| c \right| = 1$ and define a sequence $(x_i)_{i \geq 0}$ by

$x_0 = a\quad$ and $\quad x_{i+1} = 2x_i - cx_i^{2},\quad i = 0,1,2,....$

, where $a$ is any $p$-adic number whose last digit is the inverse modulo $p$ of the last digit of $c$. In fact, this is an application of Newton iteration to compute the inverse of $c$. I don't see how to prove that the sequence $(x_i)_{i \geq 1}$ converges to $\frac{1}{c} \in \mathbb{Z}_p$ and that $\left| cx_i - 1 \right| \leq p^{-2i}$ for all $i$. Can someone help ?

Many thanks !

Answer 1

Here is a strategy, it might remind a method applied when considering dinamical systems over $\mathbb R$.

1. Prove by induction that $x_i\equiv x_0 \pmod p$. In particular $x_i\in \mathbb Z_p^\times, \forall i$.

2. $\mathbb Z_p^\times$ is closed in $\mathbb Z_p$. In particular, if you can prove that $\{x_i\}_i$ has limit $\alpha$ as sequence in $\mathbb Z_p$ then $\alpha\in \mathbb Z_p^\times$.

3. If $\alpha$ exists then $ \alpha =\lim x_{i+1} = \lim 2 x_ i - c x_i^2 = 2\alpha-c\alpha^2. $ In particular $\alpha = c\alpha^2 $.

4. $\mathbb Z_p$ is a domain, thus either $c\alpha = 1$ or $\alpha=0$.

5. Since $0\notin \mathbb Z_p^\times$ you are almost done.

It remains to prove that $\{x_i\}$ converges. The equality $$ c x_{i+1} -1 = -(c x_i -1) ^2. $$ helps.

Edit: Actually last property is enough. One has that $x_0$ is an aproximation of $c^{-1}\pmod p$, hence $cx_0\equiv 1 \pmod p$ (or equivalently $|x_0 c-1|\leq1/p$). Thus $$|x_i c -1 | = |x_{i-1} c -1 |^2 = \cdots = |x_0 c -1|^{2^i}\leq 1/p^{2^i},$$ in particular $\lim_{i\rightarrow +\infty} x_i c -1 = 0$