Exercise 2.2.12* (Solution of $ax \equiv 1 \pmod{m^s}$, second part)

Proof.

• If $a=\pm 1$, then $a^2=1$. If $x\equiv a(\mathit{mod}{m}^s)$, then $\mathit{ax}\equiv a^2\equiv 1(\mathit{mod}{m}^s)$, so $a$ is the solution of $\mathit{ax}\equiv m^s$ when $a=\pm 1$.

• If $a=\pm 2$, then $a^2=4$, and $m\wedge 2=1$, so $m$ is odd. Therefore $x_s=\frac{1-m^s}{2}\frac{a}{2}$ is an integer, and

  $$a\left[\frac{1-m^s}{2}\frac{a}{2}\right]=1-m^s\equiv 1(\mathit{mod}{m}^s),$$

  so $x_s=\frac{1-m^s}{2}\frac{a}{2}$ is the solution of $\mathit{ax}\equiv m^s$ when $a=\pm 2$.

• Suppose now that $|a|\ge 3$, where $a\wedge m=1$. By Exercise 11, $a{x}_s\equiv 1(\mathit{mod}{m}^s)$, where

  $$x_s=\frac{1-{(1-a{x}_1)}^s}{a}=k\in \mathbb{Z}.$$

  Write $y_s=-\frac{{(1-a{x}_1)}^s}{a}$. Then

  $$|k-y_s|=\frac{1}{|a|}\le \frac{1}{3}.$$

  This shows that $k=x_s$ is the nearest integer to $y_s=-\frac{{(1-a{x}_1)}^s}{a}$.

  As a conclusion, the solution of $\mathit{ax}\equiv 1(\mathit{mod}{m}^s)$ is $x\equiv k(\mathit{mod}{m}^s)$ where $k$ is the nearest integer to $-(1∕a){(1-a{x}_1)}^s$.