Quadratic reciprocity

Quadratic reciprocity relates whether each of two distinct odd primes is a square modulo the other. Their Legendre symbols agree unless both primes are congruent to 3 modulo 4, when they have opposite signs.

Legendre symbol: A notation that records whether an integer is a quadratic residue modulo an odd prime, with signs for residue and nonresidue. It expresses the two residue tests that quadratic reciprocity compares.
Congruence: A relation stating that two integers have the same remainder upon division by a specified modulus. Residues and squares in the theorem are defined through congruence.
Leonhard Euler: An eighteenth-century mathematician whose work ranged across analysis, mechanics, and number theory. Euler formulated an early version of the reciprocity pattern.
Primality test: An algorithm or procedure for determining whether an integer is prime. Residue computations using reciprocity can simplify some primality-testing calculations.
Cubic reciprocity: A reciprocity law relating whether integers are cubes modulo one another in suitable number systems. It replaces square-residue questions with cube-residue questions.
Supplementary laws of quadratic reciprocity: Formulas determining the Legendre symbols of −1 and 2 modulo an odd prime. They complete the sign rule by handling the special residues −1 and 2.
Modular arithmetic: Arithmetic in which integers are identified when their difference is divisible by a fixed modulus. The theorem compares square classes in two different modular systems.
Adrien-Marie Legendre: A French mathematician whose work included number theory, geometry, and mathematical physics. Legendre stated the law and developed a proof before Gauss.
Integer factorization: The decomposition of an integer into a product of prime factors. Residue tests related to reciprocity help guide some factorization methods.
Quartic reciprocity: A reciprocity law governing fourth-power residues, formulated in suitable rings of integers. It extends reciprocity beyond the quadratic sign relation.

Linked from 18 pages