Chinese remainder theorem

The Chinese remainder theorem characterizes when simultaneous congruences have a solution and guarantees a unique solution modulo the least common multiple of their moduli.

Congruence relation: An equivalence relation on integers that groups numbers with the same remainder upon division by a fixed modulus. The theorem is stated entirely in terms of congruences.
Integer: A whole number, including positive numbers, negative numbers, and zero. The theorem applies to integer unknowns and integer moduli.
RSA cryptosystem: A public-key cryptosystem whose security rests on the difficulty of factoring a product of two large primes. Implementations use the theorem to speed up private-key exponentiation.
Sunzi Suanjing: An ancient Chinese mathematical text that includes a problem involving simultaneous congruences. Its remainder problem is the historical source associated with the theorem's name.
Bézout's lemma: A theorem stating that a greatest common divisor is an integer linear combination of its inputs. It is a constructive tool for the theorem, not the simultaneous-congruence result itself.
Modular arithmetic: Arithmetic in which numbers are identified when they differ by a multiple of a fixed integer. It supplies the arithmetic setting in which the theorem operates.
Divisibility: The relation in which one integer is an integer multiple of another. Compatibility of noncoprime congruences is expressed through divisibility.
Fast Fourier transform: An algorithm that computes a discrete Fourier transform using fewer arithmetic operations than direct evaluation. Number-theoretic transforms use modular arithmetic and sometimes recombine residues by this theorem.
Sunzi's theorem: A classical result for solving simultaneous congruences with pairwise coprime moduli. This named formulation is closely associated with the theorem's early Chinese presentation.
Fermat's little theorem: A theorem describing powers modulo a prime number. It concerns exponentiation modulo one prime rather than combining several congruences.

Linked from 30 pages