1
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for this! $\endgroup$ – fatima Mar 2 at 4:42
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.