Law of quadratic reciprocity

From Prime-Wiki
Revision as of 10:40, 6 February 2019 by Karbon (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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

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 [math]p[/math].

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

External links