Residui

Residui, in the context of number theory and modular arithmetic, refer to the remainders or representatives of equivalence classes of integers modulo a positive modulus. For a given positive integer n, every integer a has a residue r, which is the remainder when a is divided by n, most commonly chosen as the least nonnegative remainder satisfying 0 ≤ r < n and a ≡ r (mod n). The collection of all such residues modulo n forms the residue system modulo n, and each residue represents a distinct congruence class.

A residue can also be viewed as part of a residue class, an element of the quotient set Z/nZ, where two integers are considered equivalent if they differ by a multiple of n. A reduced residue system modulo n is a set of φ(n) integers, each coprime to n, that contains exactly one representative from every unit modulo n. The size φ(n), Euler’s totient function, counts these units.

Special kinds of residues arise in various contexts. Quadratic residues modulo n are numbers x for which there exists a y with y^2 ≡ x (mod n). For a prime p, the number of quadratic residues modulo p, including 0, is (p+1)/2. More generally, residues modulo n play a central role in algorithms and theories across mathematics and computer science, including cryptography, primality testing, and arithmetic computations.

Example: the residue of 37 modulo 10 is 7, since 37 ≡ 7 (mod 10). Hence 7 is the least nonnegative residue of 37 mod 10.