Legendre symbol

The Legendre symbol a/p records whether an integer a is zero, a nonzero square, or a nonsquare modulo an odd prime p, with values 0, 1, or −1.

Quadratic residue: A residue class modulo an integer that is congruent to a square. The symbol classifies whether its numerator represents a square modulo its prime denominator.
Congruence relation: An equivalence relation on integers stating that their difference is divisible by a fixed modulus. The symbol tests whether congruence classes modulo p contain square roots.
Quadratic congruence: A congruence involving a polynomial of degree two, solved in residue classes modulo an integer. The symbol decides whether x² ≡ a (mod p) has a solution.
Adrien-Marie Legendre: A French mathematician whose work included number theory, analysis, and the method of least squares. He introduced the notation and developed the reciprocity law now bearing his name.
Euler's criterion: For an odd prime p and p not dividing a, a^((p−1)/2) is congruent to 1 or −1 modulo p according as a is or is not a square. It computes the symbol by modular exponentiation.
Modular arithmetic: Arithmetic on integers viewed through their remainders modulo a fixed positive integer. Its residue classes are the setting in which the symbol distinguishes squares from nonsquares.
Quadratic Gauss sum: A finite exponential sum whose terms are indexed by residue classes and weighted by a quadratic character. The symbol supplies the character weights in the basic quadratic Gauss sum.
Carl Friedrich Gauss: A German mathematician whose work shaped number theory, geometry, astronomy, and many other fields. His systematic treatment of quadratic residues established reciprocity as a central theorem.
Multiplicativity of the Legendre symbol: The identity (ab/p) = (a/p)(b/p), expressing multiplicativity in the numerator. It lets a composite numerator be factored into simpler symbol evaluations.
Prime number: An integer greater than one whose only positive divisors are one and itself. The denominator must be an odd prime for the Legendre symbol's standard definition.

Linked from 12 pages