0
$\begingroup$

Let p be an odd prime number and let $a$ be a quadratic residue mod p. Prove that -a is also a quadratic residue mod p iff $p \equiv 1 \pmod 4$

I think that (${-1} \over p$)=1 if $p \equiv 1 \pmod 4$ is part of the proof, but I'm not sure how to bring it in. Any help?

$\endgroup$
1
$\begingroup$

I assume $a \neq 0$, otherwise the statement is not true.

Now, using the multiplicativity of the Legendre symbol, we get that $-a$ is a quadratic residue iff $1=(\frac{-a}{p})=(\frac{a}{p})(\frac{-1}{p})=(\frac{-1}{p})$ which is true iff $p \equiv 1 \pmod{4}$, as desired.

$\endgroup$
  • $\begingroup$ So simple, so brilliant $\endgroup$ – DERPYPENGUIN Nov 9 '16 at 5:24
0
$\begingroup$

If ${a\choose \overline p}={b\choose \overline p}=1$ it means we can find integers $u, v$ such that $a=u^2\pmod p$ and $b=v^2\pmod p$; then for their product we have $ab=(uv)^2\pmod p$. So we get ${ab\choose \overline{\ p\ }}=1\pmod p$.

For a prime $p$ that is 1 mod 4, we have $-1$ is a square modulo $p$, which can be seen as below: the multiplicative group is of order $p-1$, a multiple of 4. This group is cyclic, say generated by $g$. Its $(p-1)$th power is 1, not smaller powers. So $g^{(p-1)/2}=-1\pmod p$; now we see $-1=g^{(p-1)/2}={\big(g^{(p-1)/4} \big)}^2$is a square indeed.

Taking $b$ as $-1$ we see that $-a$ is also a square if $a$ is.

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