A generalization of Fermat's result: for integer n≥1 and integer a with gcd(a,n)=1, a^{φ(n)} ≡ 1 (mod n), where φ(n) is Euler's totient function counting units modulo n.

Principle

The multiplicative group of units modulo n has order φ(n); by Lagrange's theorem every unit raised to φ(n) gives the identity, producing the congruence a^{φ(n)} ≡ 1 (mod n).

Demonstration

With n=10, φ(10)=4; for a=3 (coprime to 10), 3^4=81 and 81 ≡ 1 (mod 10), demonstrating the theorem in a simple composite modulus case.

Misapplication

Applying the congruence when gcd(a,n)≠1 or assuming φ(n) is the minimal exponent for all units; in many rings the true exponent can be a proper divisor of φ(n) (Carmichael function phenomena).

Consequence

Enables modular exponent reductions for composite moduli, underlies RSA-like ideas (exponent arithmetic tied to φ(n)), and justifies computations of modular inverses via exponentiation when modulus and base are coprime.

Reversal

Replacing φ(n) by smaller universal exponents (Carmichael λ(n)) or seeking converses leads to limitations: a^{φ(n)} ≡ 1 does not imply n is prime; converses instead motivate stronger primality tests.

Boundary

Requires that a be a unit modulo n and that n be a positive integer; does not apply directly to nonunit residues or to moduli with additional algebraic structure without modification.

Semantic Tension

Tension between Euler's general statement and sharper exponents like the Carmichael function; also tension with practical algorithms that exploit smaller exponents for efficiency or with special structure (e.g., cyclic versus noncyclic unit groups).

Synthesis

Euler's theorem abstracts Fermat's observation to the full unit group modulo n: the group's finite order φ(n) yields exponentiation congruences that organize modular arithmetic and inform algorithmic number theory.