Fermat's little theorem

For a prime p and an integer a not divisible by p, a raised to the power p−1 is congruent to 1 modulo p. It underlies modular arithmetic techniques in number theory and cryptography.

Multiplicative group modulo n: The group of invertible residue classes modulo n under multiplication. Nonzero residues modulo p form this group, whose order determines the exponent p−1.
Fermat primality test: A probabilistic primality test based on the congruence in Fermat's little theorem. It applies the theorem in reverse: a failed congruence proves a number composite.
Prime number: An integer greater than one whose only positive divisors are one and itself. Primality ensures every nonzero residue modulo p has a multiplicative inverse.
Pierre de Fermat: A seventeenth-century French lawyer and mathematician known for foundational contributions to number theory. The theorem bears his name, though its first published proof came after his death.
Lagrange's theorem: A theorem stating that a finite group's subgroup order divides the group's order. Applied to the multiplicative group modulo p, it forces each element's order to divide p−1.
RSA cryptosystem: A public-key cryptosystem whose security relies on the difficulty of factoring large integers. Fermat's theorem helps explain exponent identities used in RSA, though Euler's theorem is more general.
Congruence relation: An equivalence relation stating that two integers have the same remainder modulo a fixed modulus. The theorem's conclusion is equality of residue classes modulo p.
Leonhard Euler: An eighteenth-century Swiss mathematician whose work shaped number theory, analysis, and mechanics. Euler generalized Fermat's result to composite moduli using the totient function.
Euler's theorem: For coprime integers a and n, a raised to φ(n) is congruent to 1 modulo n. It generalizes Fermat's result from prime moduli to arbitrary moduli coprime to a.
Pseudoprime: A composite integer that satisfies a primality-test congruence for at least one base. Such numbers show why satisfying Fermat's congruence does not prove primality.

Linked from 28 pages