Exercise 2.6.8 (Solve $1000 x \equiv 1 \pmod{101^3}$)

Proof. First solution. The Bézout’s algorithm applied to $1000,101^3$ gives

Therefore the solution of $1000x\equiv 1(\mathit{mod}101^3)$ is

Second solution. If we apply the section 2.6, we search first a solution $a_1$ of $f(x)=1000x-1\equiv 0(\mathit{mod}101)$, which is equivalent to $91x\equiv 1(\mathit{mod}101)$. Since $10\times 91-9\times 101=1$, we obtain $a_1=10$.

Here $f^{\prime }(x)=1000\equiv 91(\mathit{mod}101)$, thus $a=a_1$ is a nonsingular root, and $f^{\prime }(a)\equiv 91,\overline{f^{\prime }(a)}=10$.

We obtain the solutions $a_2$ of $f(x)\equiv 0(\mathit{mod}101^2)$, and $a_3$ of $f(x)\equiv 0(\mathit{mod}101^3)$ with

Therefore the solution of $1000x\equiv 1(\mathit{mod}101^3)$ is

□