I'm trying to prove the following statement:
If $4n+1$ is a prime $p$, then $n$ is a quadratic residue $\bmod p$.
For this, I thought I could evoke the quadratic reciprocity law and deduce:
$$\genfrac(){}{0}{n}{4n+1}\genfrac(){}{0}{4n+1}{n}
=(-1)^{(n-1)\frac{4n+1-1}{4}}=(-1)^{(n-1)n}=1
\\\iff\genfrac(){}{0}{n}{4n+1}=(\genfrac(){}{0}{4n+1}{n})^{-1}
=(\genfrac(){}{0}{1}{n})^{-1}=1$$
with Legendre Symbols, but then it occured to me that $n$ need not be prime.
Looking for a workaround, I found I can deduce that the Jacobi-Symbol must be $1$, but If I
I can deduce that the Jacobi-Symbol must be $1$ but this does not necessarily imply that $n$ is a quadratic residue. How do I work around this?
Best Answer
HINT: $n$ is a quadratic residue if and only if $-1$ is a quadratic residue.
Indeed, if $-1=a^2 \pmod p$, then $$(2^{-1} a)^2 = 4^{-1}a^2 = (4^{-1})(-1) = (4^{-1})(4n) = n \pmod p$$