# Congruence Problem

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?

-
add comment

## 3 Answers

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$.

-
Nicely done! +1 –  Amzoti Apr 21 '13 at 0:50
add comment

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$.

-
add comment

Hint $\rm\,\ 1\!-\!ax_1 = mn\:\Rightarrow\: 1-ax_k := (1\!-\!ax_1)^k\! = (mn)^k$

-
add comment