Quadratic residue

An integer is a quadratic residue modulo a positive integer if it is congruent to the square of some integer modulo that modulus.

Modular arithmetic: Arithmetic in which integers are identified when they differ by a multiple of a fixed modulus. Quadratic residues are defined by equality of squares within this arithmetic.
Modular squaring: The operation of squaring an integer and reducing the result modulo a fixed integer. Its outputs are precisely the quadratic residues for that modulus.
Quadratic reciprocity: A theorem relating whether one odd prime is a quadratic residue modulo another to the reverse question. It lets residue questions between primes answer one another.
Quadratic nonresidue: An integer that is not congruent to any square modulo a specified modulus. It is the complementary case to a quadratic residue.
Congruence relation: A relation stating that two integers differ by a multiple of a specified modulus. It expresses the condition that an integer and a square represent the same residue.
Multiplicative group of integers modulo n: The group of invertible residue classes modulo a positive integer n, under multiplication. For prime moduli, nonzero quadratic residues form a subgroup of this group.
Tonelli–Shanks algorithm: An algorithm for finding square roots modulo an odd prime when a root exists. It computes roots after quadratic-residue status has been established.
Cubic residue: An integer congruent to a cube modulo a specified modulus. It replaces squaring with cubing, producing a different residue problem.
Modulus: A positive integer that determines the period of a modular arithmetic system. Changing the modulus changes which integers count as quadratic residues.
Euler's criterion: A test for whether a nonzero residue modulo an odd prime is a square, using exponentiation. It determines quadratic-residue status without listing every square.

Linked from 12 pages