Euler’s theorem is a fundamental result in number theory describing powers of integers in modular arithmetic. It states that if is an integer and is an integer coprime to , then
where is Euler’s totient function, the number of integers from to that are coprime to . Named after Leonhard Euler, the theorem generalizes Fermat’s little theorem and provides a basis for reducing large exponents, calculating modular inverses, and understanding the algebra behind RSA cryptography.
Statement and terminology
Two integers are coprime when their greatest common divisor is . Thus the hypothesis of Euler’s theorem is
The conclusion means that divides . Equivalently, leaves remainder upon division by .
The totient function is defined by
If the distinct prime divisors of are , then
In particular, for a prime and an integer ,
For example, the integers between and coprime to are , so . Since is coprime to , Euler’s theorem gives
The restriction to coprime integers is essential. If , a prime dividing both and divides every positive power of , so no such power can be congruent to modulo .
Elementary proof
A reduced residue system modulo consists of one representative of each congruence class coprime to . Write such a system as
If , multiplication by rearranges these classes. Indeed, each remains coprime to , and
implies
because a factor coprime to the modulus can be cancelled. Thus multiplication by induces a permutation of the reduced residue classes.
Consequently, their products satisfy
Factoring out the powers of yields
The product is coprime to , so it too can be cancelled. The result is
Cancellation here depends on coprimality, not merely on the cancelled factor being nonzero. This distinction is crucial for composite moduli.
Group-theoretic interpretation
In group theory, the invertible residue classes modulo form a group under multiplication, denoted
It is the group of units of the ring , and it has exactly elements.
Lagrange’s theorem implies that the order of an element of a finite group divides the number of elements in the group. Therefore, raising any element of to the power gives the identity element. This is precisely Euler’s theorem.
More specifically, the multiplicative order of modulo , written , is the smallest positive integer such that
For ,
Euler’s theorem therefore supplies a universal exponent for all invertible classes, but not necessarily the smallest exponent for a particular class.
Relationship to Fermat’s little theorem
For a prime modulus , every nonzero residue class is invertible and . Euler’s theorem becomes
which is Fermat’s little theorem.
The equivalent prime-modulus statement
holds for every integer , including multiples of .
Euler’s contribution extended the prime-modulus result to arbitrary positive moduli by replacing with and requiring coprimality. The theorem belongs to Euler’s eighteenth-century development of number theory; its modern group-theoretic formulation places it within a more general theory of finite groups.
Applications
Reducing large exponents
If , write a nonnegative exponent as
Then
For example, and . Since
it follows that
Reducing exponents modulo in this way is not generally valid for bases that are not coprime to .
Computing modular inverses
A modular multiplicative inverse of modulo is an integer satisfying
Such an inverse exists exactly when . Euler’s theorem gives
For instance, because ,
This formula is useful theoretically and when the totient is known. The extended Euclidean algorithm also computes modular inverses and does not require knowing .
RSA cryptography
Euler’s theorem is central to the mathematical explanation of RSA. For distinct primes and , let
If positive integers and satisfy
then, for every message representative coprime to ,
RSA correctness also holds for message representatives not coprime to , but Euler’s theorem alone does not establish that case. Applying Fermat’s little theorem separately modulo and modulo , then using the Chinese remainder theorem, establishes the result for every residue class modulo .
This algebraic correctness is distinct from cryptographic security; a secure encryption scheme requires additional constructions beyond raw modular exponentiation.
Sharper exponents and limitations
The Carmichael function is the smallest positive integer such that
for every integer coprime to . It satisfies
Thus it can provide a smaller universal exponent than Euler’s totient.
For example,
Every odd integer satisfies , so the exponent supplied by Euler’s theorem is valid but not minimal. For a particular base, the multiplicative order can be smaller still.
Euler’s theorem is also not a primality criterion: its conclusion holds for every modulus when its hypotheses are satisfied and the correct totient is used. By contrast, the congruence , used in Fermat-style primality testing, may hold even when is composite.
Finally, the theorem does not itself supply an efficient way to calculate for an arbitrary large integer. The product formula is straightforward when the prime factorization is known, but obtaining that factorization may be computationally difficult. For an RSA modulus , knowledge of reveals
so and can be recovered as the roots of