Exercise 2.2.11 (Solutions for $a x \equiv 1 \pmod {m^s}$)

Question

Suppose $(a,m) = 1$, and let $x_1$ denote a solution of $ax \equiv 1 \pmod m$. For $s = 1,2,\ldots$, let $x_s = 1/a - (1/a)(1-ax_1)^s$. Prove that $x_s$ is an integer and that it is a solution of $ax\equiv 1 \pmod {m^s}$.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

\begin{proof} First
\begin{align*}
x_s &= \frac{1 - (1-ax_1)^s}{a}\
&=x_1  \frac{1 - (1-ax_1)^s}{ 1 - (1 -ax_1)}\
&= x_1 \sum_{i=0}^{s-1} (1-ax_1)^i \in \Z.
\end{align*}
(One can also use the binomial formula.)

Since $ax_1 \equiv 1 \pmod p$, there is an integer $q$ such that
$$1 -ax_1 = qp.$$

Then
\begin{align*}
ax_s &= 1 - (1 -ax_1)^s\
&=1 - q^sm^s\
&\equiv 1 \pmod{m^s}.
\end{align*}

\end{proof}

Exercise 2.2.11 (Solutions for $a x \equiv 1 \pmod {m^s}$)

Answers

Comments

Exercise 2.2.11 (Solutions for $a x \equiv 1 \pmod {m^s}$)

Answers

Comments

Add answer