Law of quadratic reciprocity

The law of quadratic reciprocity predicts whether an odd prime number $p$ is a quadratic residue or non-residue modulo another odd prime number $q$ if we know whether $q$ is a quadratic residue or non-residue modulo $p$.

• If at least one of $p$ or $q$ are congruent to 1 mod 4: $p$ is a quadratic residue modulo $q$ if and only if $q$ is a quadratic residue modulo $p$.
• If both of $p$ or $q$ are congruent to 3 mod 4: $p$ is a quadratic residue modulo $q$ if and only if $q$ is a quadratic non-residue modulo $p$.

This theorem was first proved by Carl Friedrich Gauss in 1801.

This does not cover the cases where we want to know whether -1 or 2 are quadratic residues or non-residues modulo $p$.

• 2 is a quadratic residue modulo $p$ if and only if $p$ is congruent to 1 or 7 (mod 8).
• -1 is a quadratic residue modulo $p$ if and only if $p$ is congruent to 1 (mod 4).

External links

• Wikipedia