Given $a,m \in\mathbb{N}$ with $gcd(a,m)=1$, let $x_1\in\mathbb{N}$ be a solution to the congruence $ax\equiv1\pmod m$. For each integer $k\ge1$, number is defined as $x_k:=\frac{1}{a}(1-(1-ax_1)^k]$.
Prove that $x_k$ is a solution to the congruence $ax\equiv1\pmod {m^k}$
I tried induction, for base case $k=1$
$\frac{1}{a}[(1-(1-ax)]=x$
And $ax\equiv1\pmod m$ is true indeed
How should I do this?
Note that $x_k:=\frac{1}{a}(1-(1-ax_1)^k] \iff ax_k :=1 - (1 - ax_1)^k$. (Just multiply both sides of the equation by $a$)
So to show that $ax_k \equiv 1 \pmod {m^k}$, we can prove any of the following equivalent statements $$ax_k \equiv 1 \pmod {m^k}\iff 1 - (1 - ax_1)^k \equiv 1 \pmod {m^k} $$ $$\iff -(1 - ax_1)^k \equiv 0 \pmod {m^k}\iff m^k\mid (ax_1 - 1)^k .$$
We know that $\;m\mid (ax_1 - 1)^k$, because $ax_1 \equiv 1 \pmod m \iff m \mid (ax_1 - 1)$
so it follows immediately that $m^k\mid (1 - ax_1)^k$.
We want to show that $ax_k$ is congruent to $1$ modulo $m^k$. By the definition of $x_k$, we want to show that $1+(1-ax_1)^k$ is congruent to $1$ modulo $m^k$.
Equivalently, we want to show that $(1-ax_1)^k$ is congruent to $0$ modulo $m^k$. So we want to show that $m^k$ divides $(1-ax_1)^k$. This is obvious, since $m$ divides $1-ax_1$.
Remark: The fact that if $m$ divides $b$, then $m^k$ divides $b^k$ really should not require proof. But if we want to tie down all the details, suppose that $m$ divides $b$. Then $b=qm$ for some integer $q$. But then $b^k=(qm)^k=q^km^k$, so $m^k$ divides $b^k$.
