1
$\begingroup$

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?

$\endgroup$
7
  • 2
    $\begingroup$ This might be easier with Euler's criterion. For example, is $4n$ a quadratic residue? $\endgroup$ Commented Jan 11, 2021 at 16:37
  • $\begingroup$ Yes, then we can invoke multiplicativity-that's elegant. $\endgroup$
    – IMOPUTFIE
    Commented Jan 11, 2021 at 16:38
  • $\begingroup$ Quadratic reciprocity only holds for primes $p$ and $q$. You should probably try another approach altogether. $\endgroup$
    – mxian
    Commented Jan 11, 2021 at 16:38
  • 1
    $\begingroup$ The Jacobi symbol $\left(\frac n{4n+1}\right)$ matches the Legendre symbol here because $4n+1$ is prime, if I'm not mistaken. So I think your computation is a proof. $\endgroup$ Commented Jan 11, 2021 at 16:42
  • 1
    $\begingroup$ @IMOPUTFIE The Jacobi symbol and the Legendre symbol are equal when the "denominators" are prime, by definition of the Jacobi symbol. $\endgroup$ Commented Jan 11, 2021 at 18:02

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

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