Exercise 4.25

Proof. We suppose that $a$ is odd and $e\ge 3$.

From Theorem 2’, we know that $\{{(-1)}^a{5}^b|0\le a\le 1,0\le b\le 2^{e-2}\}$ constitutes a reduced residue system modulo $2^e$, so we can write

For all $x\in \mathbb{Z}$,

Then ${(-1)}^{\mathit{ny}}\equiv {(-1)}^s(\mathit{mod}4),\mathit{ny}\equiv s(mod2),{(-1)}^{\mathit{ny}}={(-1)}^s$, thus $5^{\mathit{nz}}\equiv 5^t(\mathit{mod}{2}^e)$.

Conversely, if $\mathit{ny}\equiv s(\mathit{mod}2)$ and $5^{\mathit{nz}}\equiv 5^t(\mathit{mod}{2}^e)$, then $x^n\equiv a(\mathit{mod}{2}^e)$, so

since the order of 5 modulo $2^e$ is $2^{e-2}$.

$\text{∙}$ Suppose that $n$ is an odd integer. Then

where $n^{\prime }$ is an inverse of $n$ modulo $2^{e-2}$ : $n{n}^{\prime }\equiv 1(\mathit{mod}{2}^{e-2})$.

So $x^n\equiv a(\mathit{mod}{2}^e)$ has an unique solution modulo $2^e$.

$\text{∙}$ Suppose that $n$ is an even integer.

Then $\{\begin{array}{ccc}\hfill \mathit{ny}\hfill & \hfill \equiv \hfill & s(\mathit{mod}2)\hfill \\ \hfill \mathit{nz}\hfill & \hfill \equiv \hfill & t(\mathit{mod}{2}^{e-2})\hfill \end{array}$ implies $s\equiv 0(\mathit{mod}2)$ and $d=n\wedge 2^{e-2}\mid t$.

Then $a\equiv {(-1)}^s{5}^t\equiv 5^t(\mathit{mod}{2}^e)$, so $a\equiv 1(\mathit{mod}4)$.

Hence $a^{\frac{2^{e-2}}{d}}\equiv {\left(5^{2^{e-2}}\right)}^{\frac{t}{d}}\equiv 1(\mathit{mod}{2}^e)$, since $5$ has order $2^{e-2}$, and $d\mid t$.

So, if $n$ is even, and, with $d=n\wedge 2^{e-2}$,

Conversely, suppose that $\{\begin{array}{ccc}\hfill a\hfill & \hfill \equiv \hfill & 1(\mathit{mod}4),\hfill \\ \hfill a^{\frac{2^{e-2}}{d}}\hfill & \hfill \equiv \hfill & 1(\mathit{mod}{2}^e).\hfill \end{array}$

Then $a\equiv {(-1)}^s{5}^t(\mathit{mod}{2}^e)$ implies $a\equiv {(-1)}^s(\mathit{mod}4)$, so $s$ is even, and $a\equiv 5^t(\mathit{mod}{2}^e)$.

Therefore $5^{t\frac{2^{e-2}}{d}}\equiv 1(\mathit{mod}{2}^e)$, which implies $2^{e-2}\mid t\frac{2^{e-2}}{d}$, so $d\mid t$.

As $\frac{2^{e-2}}{d}\wedge \frac{n}{d}=1$, there exists a solution $(q,z_0)$ of this last equation, where $0\le z_0<\frac{2^{e-2}}{d}$, and so $x_0=5^{z_0}$ is a particular solution of $x^n\equiv a(\mathit{mod}{2}^e)$, therefore

If there exists a particular solution $x_0\equiv {(-1)}^{y_0}{5}^{z_0}$, then

As the order of $5$ modulo $2^e$ is $2^{e-2}$, the solutions of $x^n\equiv a(\mathit{mod}{2}^e)$ are

so there are exactly $2d$ solutions modulo $2^e$. □

Proof. We suppose that $a$ is odd, and that $x^n\equiv a(\mathit{mod}{2}^{2l+1})$ is solvable. $l$ is such that $n=2^l{n}^{\prime }$, where $n^{\prime }$ is an odd integer.

Let the induction hypothesis be, for a fixed integer $m\ge 2l+1$,

Let $x_1=x_0+b{2}^{m-l}$. We show that for an appropriate choice of $b\in \{0,1\}$, $x_1^n\equiv a(\mathit{mod}{2}^{m+1})$.

$x_1^n=x_0^n+\mathit{nb}{2}^{m-l}{x}_0^{n-1}+2^{2m-2l}A,A\in \mathbb{Z}$.

Since $m\ge 2l+1,2m-2l\ge m+1$, so

As $a$ is odd, and $x_0^n\equiv a(\mathit{mod}{2}^m),m\ge 1$, $x_0$ is odd, and $n^{\prime }$ is odd, so there exists an unique $b\in \{0,1\}$ such that $\frac{x_0^n-a}{2^m}+n^{\prime }b{x}_0^{n-1}\equiv 0(\mathit{mod}2)$. Hence there exists $x_1\in \mathbb{Z}$ such that $x_1^n\equiv a(\mathit{mod}{2}^{m+1})$, and the induction is done. Therefore, $x^n\equiv a(\mathit{mod}{2}^e)$ is solvable for all $e\ge 2l+1$, and consequently for all $e\ge 1$.

From the Proposition 4.2.2., with the hypothesis $e\ge 3$, we know that the number of solutions of the solvable equation $x^n\equiv a(\mathit{mod}{2}^e),e\ge 2l+1$, is $1$ if $n$ is odd, $2(n\wedge 2^{e-2})$ if $n$ is even.

If $n$ is even, $l\ge 1$, $e\ge 2l+1\ge 3$. Since $e\ge 2l+1$, and $n=2^l{n}^{\prime }$ for an odd $n^{\prime }$, $l\le \frac{e-1}{2}\le e-2$, so $n\wedge 2^{e-2}=n^{\prime }{2}^l\wedge 2^{e-2}=2^l$, and the number of solutions is $2^{l+1}$, independent of $e\ge 2l+1$.

Conclusion: Under the hypothesis $x^n\equiv a(\mathit{mod}{2}^{2l+1})$, where $l={\mathrm{ord}}_2(n)$, then $x^n\equiv a(\mathit{mod}{2}^e)$ is solvable for all $e\ge 1$, and all these congruences have the same number of solutions for $e\ge 2l+1,e\ge 3$. □