If $p$ is congruent to 1 mod 4 where $p$ is an odd prime, then $x^2$ congruent to -1 mod $p$ has 2 solutions.

Question

If $p = 5$, then the values of $x$ that will satisfy the congruence $$x^2 \equiv -1 \bmod p $$ are $2, 3$

If $p = 13$, then the values of $x$ that will satisfy the above congruence are $5, 8$. And so on...

How can i prove that for all $p$ s.t. $(p \equiv 1\bmod 4)$, then $x^2\equiv -1\bmod p$ has only $2$ solutions? And by observation, I think it will also hold on $p^k$? How can I prove it though?

Thank you!

Answer 1

Induction on $k$ in $p^k.$ For $k \geq 2,$ we have two roots of $-1 \pmod {p^{k-1}}.$ Take one of them, call it $r,$ and pick a representative $R$ for $r \pmod {p^k}.$ We know that $R^2 \equiv -1 + W p^{k-1} \pmod {p^k}$ where $W$ is a value mod $p,$ if you wish, you may demand $0 \leq W < p.$

This $R$ then solve, for integer $t,$ $$ \left( R + t p^{k-1} \right)^2 \equiv -1 \pmod {p^k} \; ? $$ $$ R^2 + 2Rt p^{k-1} + t^2 p^{2k-2} \equiv -1 \pmod {p^k} \; ? $$ Since $k \geq 2,$ we have $2k-2 \geq k.$ $$ R^2 + 2Rt p^{k-1} \equiv -1 \pmod {p^k} \; ? $$ $$ -1 + W p^{k-1} + 2Rt p^{k-1} \equiv -1 \pmod {p^k} \; ? $$ $$ W p^{k-1} + 2Rt p^{k-1} \equiv 0 \pmod {p^k} \; ? $$ $$ W + 2Rt \equiv 0 \pmod p \; ? $$ Now, $2R$ is invertible $\pmod p,$ so there is one and only one solution $\pmod p$ to $$ 2Rt \equiv -W \pmod p \; ? $$

That's it, you get exactly one root on top of each root you have, in the process of going up one power of $p$

This is the finite calculation that leads to Hensel's Lemma. I see that Robert calls it Hensel Lifting, I was not sure about the name.

Answer 2

As mentioned, the case of prime $p$ is quadratic reciprocity. For $p^k$ you can use Hensel lifting. The point is this. Suppose $x \in [1,2, \ldots, p^j-1]$ is a solution of $x^2 \equiv -1 \mod p^j$, where $p$ is an odd prime and $j \ge 1$. Thus $x^2 = -1 + z p^j$ for some integer $z$. Consider $x + p^j y$ where $y \in [0,1,\ldots, p-1]$. We have $$(x + p^j y)^2 = x^2 + 2 p^j x y + p^{2j} y^2 \equiv -1 + (z + 2x y) p^j \bmod p^{j+1}$$ so $x + p^j y$ will be a solution mod $p^{j+1}$ iff $y \equiv -z/(2 x) \bmod p$. Thus every solution mod $p^j$ lifts to a unique solution mod $p^{j+1}$.