Solving quadratic congruences mod powers of a prime.

The problem statement is to prove that there are exactly two solutions in the 5-adic numbers to $x^2+1 =0$.

My investigation suggests that there should be solutions, one based on each solution to $x^2+1\equiv 0 \pmod 5$, which are 2 and 3 (the additive inverse of 2).

I found the solutions to the congruence for higher powers of 5 to be

7 and 18 $\pmod{25}$,

57 and 68 $\pmod{125}$ and

182 and 443 $\pmod{625}$.

The things that stands out to me are these: once I have one solution, its additive inverse is another (since $x^2 = (-x)^2$). Moreover, each of the solutions is congruent to only one of solutions to the previous equation modulo the previous power of 5. In light of this, my strategy is to prove this in three parts.

Firstly, prove (by induction on $k$) that there is a solution to $x^2+1 \equiv 0 \pmod{5^k}$ for all $k\geq 1$. Secondly, prove that I can choose my solutions to satisfy $x_{k+1} \equiv x_k \pmod{5^k}$, which may also require induction. Thirdly, prove that this property leads to two solutions, which are "generated by" the solutions $x_1 = 2$ and $x_1=3$.

Here is where I am struggling. The inductive step for part I assumes that I have a solution to $x^2 +1 \equiv 0 \pmod{5^k}$ for all $k\leq n$. How can I use this to construct a solution to $x^2+1 \equiv 0 \pmod{5^{k+1}}$?

The best attempt I have made thus far is to observe that $x_n^2+1 \equiv 0 \pmod{5^n}$ implies that $5(x_n^2 +1) \equiv 0 \pmod{5^{n+1}}$. Thus, this reduces to proving that $5x_n^2 +4$ is a square mod $5^{n+1}$. In the cases I have considered, this number turns out to be congruent to $-1$, so I need only prove that this always happens and that $-1$ is always a square.

Anyway, I am stuck, so some help would be appreciated.

Suppose $x^2\equiv -1 \bmod 5^k$, so that $x^2\equiv d\cdot5^k-1 \bmod 5^{k+1}$ for some $d \in \{0,1,2,3,4\}$. Now consider:

$x^2 \bmod 5^{k+1}$
$(x+5^k)^2 \bmod 5^{k+1}$
$(x+2\cdot5^k)^2 \bmod 5^{k+1}$
$(x+3\cdot5^k)^2 \bmod 5^{k+1}$
$(x+4\cdot5^k)^2 \bmod 5^{k+1}$

Multiplying these out, we get (mod $5^{k+1}$):

$d\cdot5^k-1$
$d\cdot5^k+2x\cdot5^k-1$
$d\cdot5^k+4x\cdot5^k-1$
$d\cdot5^k+x\cdot5^k-1$
$d\cdot5^k+3x\cdot5^k-1$

These are all different mod $5^{k+1}$, because $x$ and $5$ are coprime. But they are all equal to $-1$ mod $5^k$. So they must take all five values $-1, 5^k-1, 2\cdot5^k-1,3\cdot5^k-1,$ and $4\cdot5^k-1$ mod $5^{k+1}$. Hence one of them must equal $-1$ mod $5^{k+1}$.

• Is this a common technique with which I should familiarize myself? I only struggle to see the inspiration for it, though it clearly works. – Makenzie Jan 9 '17 at 20:02
• It's fairly straightforward, I would say, once you get used to it. It is a special case of Hensel's lifting lemma. – TonyK Jan 9 '17 at 20:10
• Oh, but that lemma (almost) trivializes the problem. There is nothing left to prove except that the function $x^2+1$ satisfies the conditions, but that is easy to see. – Makenzie Jan 9 '17 at 20:13