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

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?

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

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

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

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)