Overview. Euler's totient theorem is a central statement in number theory. It asserts that for any integer a and positive integer n with gcd(a,n)=1 (that is, a and n are coprime), the congruence

a^{φ(n)} ≡ 1 (mod n)

holds, where φ(n) denotes Euler's totient function, the count of integers between 1 and n that are coprime to n. This relation is often called the Fermat–Euler theorem because it generalizes Fermat's little theorem, and it played a key role in the development of modular arithmetic and modern cryptography.

Precise statement and key terms

Formally, if n≥1 and gcd(a,n)=1, then a^{φ(n)} ≡ 1 (mod n). The condition gcd(a,n)=1 is essential: when a and n share a common factor the congruence need not hold. The symbol ≡ indicates an equivalence relation modulo n, meaning the two integers differ by a multiple of n. The function φ(n) is the totient function, defined for each positive integer n.

Short history

The theorem extends an idea first observed by Pierre de Fermat in the 17th century for the special case when n is prime. About a century later, Leonhard Euler gave the more general result and a proof that uses properties of residues modulo n. Because Euler both generalized and provided a clear proof of the broader statement, the theorem commonly bears his name as well as Fermat's.

Idea of the proof

One standard proof interprets multiplication modulo n as an operation on the multiplicative group of units (the residues mod n that are invertible). This set has φ(n) elements. Multiplying each unit by a (which is invertible since gcd(a,n)=1) permutes that set. Taking the product of all units before and after multiplication by a shows that a^{φ(n)} times the original product is congruent to the original product, and cancelling the product yields a^{φ(n)} ≡ 1 (mod n). The argument uses only elementary properties of residues and invertibility modulo n.

Examples, uses and consequences

Simple examples illustrate the theorem: if n=7 (a prime), φ(7)=6 and for any a not divisible by 7, a^6 ≡ 1 (mod 7) — this is Fermat's little theorem. For n=8, φ(8)=4 and any odd a satisfies a^4 ≡ 1 (mod 8). The theorem is a foundation for many algorithms in computational number theory, notably public‑key cryptography such as RSA where exponentiation modulo a composite modulus relies on behavior described by φ(n).

Practical consequences include methods to reduce large exponents modulo φ(n) in some contexts, and tools to test or construct multiplicative inverses modulo n. However, for some fine-grained reductions one replaces φ(n) with the smaller Carmichael function; the latter gives the least exponent λ(n) for which a^{λ(n)} ≡ 1 (mod n) for all units a.

  • The totient function is multiplicative: if m and n are coprime then φ(mn)=φ(m)φ(n).
  • For a prime p and k≥1, φ(p^k)=p^k−p^{k−1}=p^k(1−1/p).
  • Euler's theorem requires gcd(a,n)=1; if this fails the congruence can fail dramatically (for example a multiple of n is 0 modulo n, not invertible).
  • Fermat's little theorem is the special case n prime, and many proofs of Euler's theorem generalize proofs of Fermat's result.

Further reading. For a deeper treatment of proofs, generalizations and computational aspects see references in elementary number theory texts and online resources. Foundational topics to explore next include the structure of the multiplicative group modulo n, the Carmichael function, and applications to cryptographic protocols.

Links: number theory overview, coprimality, modular equivalence, Euler's totient function, Fermat's little theorem, Pierre de Fermat, Leonhard Euler.