Euler totient theorem

Euler totient theorem
Name	Euler totient theorem
Field	Number theory
Introduced	18th century
Author	Leonhard Euler

Euler totient theorem is a fundamental result in Number theory relating the Euler's totient function to modular arithmetic and the multiplicative order of integers modulo n. It generalizes Fermat's little theorem and underpins many developments in cryptography, algebraic number theory, and computational number theory. The theorem connects to work of Pierre de Fermat, Leonhard Euler, and later contributors such as Joseph-Louis Lagrange and Carl Friedrich Gauss.

Statement

Let n be a positive integer and let a be an integer with gcd(a,n)=1. Then a^{phi(n)} ≡ 1 (mod n), where phi(n) denotes Euler's totient function. This statement refines Fermat's little theorem (which is the special case n a prime number) and is often presented alongside the structure of the multiplicative group (Z/nZ)^× described in group theory and ring theory.

Proofs

Classic proofs use group-theoretic and elementary counting arguments. One proof views the invertible residue classes modulo n as a finite abelian group isomorphic to (Z/nZ)^× and invokes Lagrange's theorem to deduce that the order of a divides phi(n), hence a^{phi(n)} = 1 in the group. An alternative elementary proof multiplies the set of reduced residue representatives r_1,...,r_{phi(n)} by a modulo n to obtain a permutation of the same set and compares the products r_1...r_{phi(n)} and a^{phi(n)} r_1...r_{phi(n)}, yielding the congruence. These approaches trace through developments by Leonhard Euler, with antecedents in Pierre de Fermat and expositions by Carl Friedrich Gauss in Disquisitiones Arithmeticae.

Consequences and corollaries

The theorem implies Fermat's little theorem for prime p and yields criteria for testing units in Z/nZ. It leads to Euler's criterion for quadratic residues and to the existence of multiplicative inverses via exponentiation, which interacts with the Chinese remainder theorem and the classification of finite abelian groups such as via the Fundamental theorem of finitely generated abelian groups. Combined with Carmichael function lambda(n), one refines the exponent of (Z/nZ)^×; the Carmichael function gives the minimal universal exponent dividing phi(n). Connections extend to the RSA algorithm, where Euler's theorem governs key relations, and to primitive roots as studied by Adrien-Marie Legendre and Gauss.

Applications

Euler's theorem is instrumental in public-key cryptography, especially in RSA and related schemes for establishing trapdoor functions. It informs fast modular exponentiation used in algorithms like exponentiation by squaring and in primality tests such as the Fermat primality test and improvements leading to the Miller–Rabin primality test described by Gary L. Miller and Michael O. Rabin. In computational number theory it assists in computing multiplicative inverses, powering in (Z/nZ)^×, and in algorithms for factoring integers that exploit group structure, which are studied by researchers at institutions such as Bell Labs and universities including Princeton University and Massachusetts Institute of Technology.

Generalizations

Generalizations include replacing Z/nZ by rings of integers in number fields yielding results in algebraic number theory such as the behavior of units in rings of integers studied by Richard Dedekind and David Hilbert. The theorem extends to the concept of the exponent of a finite group and to statements about the structure of (Z/nZ)^× via the Carmichael function and via splitting by the Chinese remainder theorem. Further abstractions appear in group cohomology contexts and the theory of Dirichlet characters and L-functions where multiplicative properties of residues modulo n enter analytic results pioneered by Peter Gustav Lejeune Dirichlet and Ernst Kummer.

Examples and computations

For n=7 (a prime number), phi(7)=6 and for any a not divisible by 7, a^6 ≡ 1 (mod 7), recovering Fermat's little theorem. For n=8, phi(8)=4 so odd a satisfy a^4 ≡ 1 (mod 8); for instance 3^4=81≡1 (mod 8). For n=15, phi(15)=8 and units modulo 15 (1,2,4,7,8,11,13,14) satisfy a^8 ≡ 1 (mod 15); for example 2^8=256≡1 (mod 15). Computing phi(n) uses the multiplicative formula phi(n)=n∏_{p|n}(1-1/p) where the product runs over distinct prime divisors p of n, a formula related to factorization methods developed by Sophie Germain, Édouard Lucas, and modern computational projects at institutions like University of California, Berkeley and INRIA.

Category:Number theory