Orders and quadratic residues · Definition

Law of quadratic reciprocity

elementary number theoryorders and quadratic residues

Before you start you need to know

This law lets you compute Legendre symbols without listing explicit residues. It is one of the central results on quadratic congruences.

Definition

The law of quadratic reciprocity relates the Legendre symbols \(\left(\frac{p}{q}\right)\) and \(\left(\frac{q}{p}\right)\) for distinct odd primes \(p\) and \(q\).

\[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\]

The law states that, if \(p\) and \(q\) are distinct odd primes, the product \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)\) equals \(-1\) exactly when \(p\equiv q\equiv 3 \pmod 4\), and equals \(1\) otherwise. The supplements \(\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}\) and \(\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}\) complete the computation of any symbol.

For example, to decide whether \(3\) is a quadratic residue modulo \(7\), since \(3\equiv 7\equiv 3\pmod 4\) the product \(\left(\frac{3}{7}\right)\left(\frac{7}{3}\right)\) equals \(-1\). Since \(\left(\frac{7}{3}\right)=\left(\frac{1}{3}\right)=1\), we get \(\left(\frac{3}{7}\right)=-1\), so \(3\) is not a quadratic residue modulo \(7\).

A typical mistake is forgetting that the formula requires distinct odd primes, or applying the sign \((-1)\) without checking the congruences modulo 4. Another frequent error is treating \(\left(\frac{p}{q}\right)\) and \(\left(\frac{q}{p}\right)\) as equal instead of considering their product.

Think about it

What is \(\left(\frac{3}{7}\right)\left(\frac{7}{3}\right)\)?

\(-1\), because \(3\equiv 7\equiv 3\pmod 4\).

Exercises 10

  1. State the law of quadratic reciprocity for distinct odd primes \(p\) and \(q\).
  2. According to the law, when is \(\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=-1\)?
  3. Compute \(\left(\frac{3}{5}\right)\left(\frac{5}{3}\right)\).
  4. What is the supplement formula for \(\left(\frac{-1}{p}\right)\) when \(p\) is an odd prime?
  5. Compute \(\left(\frac{2}{7}\right)\).
  6. Compute \(\left(\frac{-1}{7}\right)\).
  7. Compute \(\left(\frac{5}{11}\right)\).
  8. Does the congruence \(x^2\equiv 3\pmod{11}\) have a solution?
  9. By definition, when is \(\left(\frac{a}{p}\right)=0\)?
  10. Compute \(\left(\frac{11}{13}\right)\left(\frac{13}{11}\right)\).

References

  • David M. Burton, Elementary Number Theory, 7th edition, McGraw-Hill, 2011. cap. 9
  • Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. cap. 3