Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3).
 Topics Help • Register • News • History • How to • Sequences statistics • Template prototypes

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

• If at least one of $\displaystyle{ p }$ or $\displaystyle{ q }$ are congruent to 1 mod 4: $\displaystyle{ p }$ is a quadratic residue modulo $\displaystyle{ q }$ if and only if $\displaystyle{ q }$ is a quadratic residue modulo $\displaystyle{ p }$.
• If both of $\displaystyle{ p }$ or $\displaystyle{ q }$ are congruent to 3 mod 4: $\displaystyle{ p }$ is a quadratic residue modulo $\displaystyle{ q }$ if and only if $\displaystyle{ q }$ is a quadratic non-residue modulo $\displaystyle{ 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 $\displaystyle{ p }$.

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