In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that if n and a are coprime positive integers, then

The theorem is a generalization of Fermat's little theorem, and is further generalized by Carmichael's theorem.

1. Euler's theorem can be proven using concepts from the theory of groups:^[3] The residue classes modulo n that are coprime to n form a group under multiplication (see the article Multiplicative group of integers modulo n for details). The order of that group is φ(n) where φ denotes Euler's totient function. Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group, in this case φ(n). If a is any number coprime to n then a is in one of these residue classes, and its powers a, a2, ... , a**k are a subgroup modulo n, with a**k ≡ 1 (mod n). Lagrange's theorem says k must divide φ(n), i.e. there is an integer M such that kM = φ(n). But then,

2. There is also a direct proof:^[4][5] Let R = {x1, x2, ... , x**φ(n)} be a reduced residue system (mod n) and let a be any integer coprime to n. The proof hinges on the fundamental fact that multiplication by a permutes the xi: in other words if axj ≡ axk (mod n) then j = k. (This law of cancellation is proved in the article multiplicative group of integers modulo n.^[6]) That is, the sets R and aR = {ax1, ax2, ... , ax**φ(n)}, considered as sets of congruence classes (mod n), are identical (as sets—they may be listed in different orders), so the product of all the numbers in R is congruent (mod n) to the product of all the numbers in aR:

The Euler quotient of an integer a with respect to n is defined as:

The special case of an Euler quotient when n is prime is called a Fermat quotient.

The least base b > 1 which n is a Wieferich number are