0
$\begingroup$

Show that there's a solution to $x^2 \equiv -1 \pmod {p^2}$ where $p$ is a prime such that $p\equiv 1\pmod{4}$

Formalizing it using Jacobi symbol we want to show that $\left(\frac{-1}{p^2}\right) = 1$ and indeed:

$$ \left(\frac{-1}{p^2}\right) = \left(\frac{-1}{p}\right) \cdot \left(\frac{-1}{p}\right) = \left(\frac{-1}{p}\right)^2=1$$

I didn't use the fact that $p\equiv 1\pmod{4}$.

Is my proof correct?

$\endgroup$

3 Answers 3

3
$\begingroup$

The easiest solution is to note that $U(p^2)$ is a cyclic group of order $p(p-1)$, a multiple of $4$. Therefore, there is an element $u$ of order $4$. Then $u^2=-1$.

$\endgroup$
2
$\begingroup$

The Jacobi symbol doesn't tell us that the top number is or is not a quadratic residue. Your calculation is correct, but the fact that $\left(\frac{-1}{p^2}\right) = 1$ doesn't imply that $-1$ is a quadratic residue modulo $p^2.$ For example, take $p=7$. $-1$ is a QNR mod $7$, so $\left(\frac{-1}{7}\right) = -1.$ So the Jacobi symbol $\left(\frac{-1}{7^2}\right) = 1.$ But if $x^2 \equiv -1 \pmod{7^2}$ has a solution, then that solution would work modulo $7$ too.

Instead, note that $p^2$ must have a primitive root $r$ whose order is $p(p-1)$. Since $p\equiv 1 \pmod{4}$, then the order is a multiple of $4$, say $p(p-1)=4k$. Then, with a little work, you can show $(r^k)^2 \equiv -1 \pmod{p^2}$.

$\endgroup$
1
  • $\begingroup$ I see. I totally forgot that a result of $1$ tells us nothing $\endgroup$ Feb 7, 2018 at 13:29
1
$\begingroup$

No, your proof is incorrect because you're assuming that $\left(\dfrac{a}{n}\right)=1$ iff $a$ is a quadratic residue modulo $n$

This is true in case of the Legendre symbol when the denominator is an odd prime but not for the Jacobi symbol.

Quoting from Wikipedia:

But, unlike the Legendre symbol:

If (a/n) = 1 then a may or may not be a quadratic residue modulo n.

The correct way would be to show that $-1$ is a quadratic residue mod $p$ since $\left(\dfrac{-1}p\right)=(-1)^{(p-1)/2}=1$ since $p\equiv 1\pmod4$, thus $(p-1)/2$ is even.

Now, use Hensel's lifting lemma to show that $-1$ is a quadratic residue modulo $p^2$.

You can also generalize this to higher powers of $p$, i.e., $-1$ is a quadratic residue modulo $p^k~\forall~k\geq 2$ using Hensel's lemma (or induction, which mimics the proof of Hensel's lemma, see here)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .