Euler's theorem

In number theory, Euler's theorem (also known as the Fermat-Euler theorem or Euler's totient theorem) states that if n is a positive integer and a is a positive integer coprime to n, then

a^{\varphi (n)}\equiv 1{\pmod {n}}

where φ(n) is Euler's totient function and "... ≡ ... (mod n)" denotes ... congruence ... modulo n.

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

The theorem may be used to easily reduce large powers modulo n. For example, consider finding the last decimal digit of 7²²², i.e. 7²²² (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 7⁴ ≡ 1 (mod 10), and we get 7²²² ≡ 7^{4x55 + 2} ≡ (7⁴)⁵⁵x7² ≡ 1⁵⁵x7² ≡ 49 ≡ 9 (mod 10).

In general, when reducing a power of a modulo n (where a and n are coprime), one needs to work modulo φ(n) in the exponent of a:

if x ≡ y (mod φ(n)), then a^x ≡ a^y (mod n).

Euler's theorem also forms the basis of the RSA encryption system: encryption and decryption in this system together amount to exponentiating the original text by φ(n), so Euler's theorem shows that the decrypted result is the same as the original.

Proofs

1. Leonhard Euler published a proof in 1736. Using modern terminology, one may prove the theorem as follows: the numbers a which are relatively prime to n form a group under multiplication mod n, the group G of (multiplicative) units of the ring Z/nZ. This group has φ(n) elements. The element a := a (mod n) is a member of the group G, and the order o(a) of a (the least k > 0 such that a^k = 1) must have a multiple equal to the size of G. (The order of a is the size of the subgroup of G generated by a, and Lagrange's theorem states that the size of any subgroup of G divides the size of G.)

Thus for some integer M > 0, M·o(a) = φ(n). Therefore a^φ(n) = a^o(a)·M =(a^o(a))^{^M} = 1^M = 1. This means that a^φ(n) = 1 (mod n).

2. Another direct proof: if a is coprime to n, then multiplication by a permutes the residue classes mod n that are coprime to n; in other words (writing R for the set consisting of the φ(n) different such classes) the sets { x : x in R } and { ax : x in R } are equal; therefore, their products are equal. Hence, P ≡ a^φ(n)P (mod n) where P is the first of those products. Since P is coprime to n, it follows that a^φ(n) ≡ 1 (mod n).

3. A more elaborate proof: Let {a₁, a₂, ..., a_k} be all the positive integers less than n coprime to n. Hence gcd(a_i,n)=1 where k=φ(n) and i ∈ {1, 2,..., k}. We have the obvious congruence a₁, a₂, ..., a_k ≡ a₁, a₂, ..., a_k (mod n). Since gcd(a_i,n)=1, the elements in the set {aa₁, aa₂,...,aa_k} are each congruent to one of the members in the set {a₁, a₂, ..., a_k} (mod n). Multiplying these congruences gives (aa₁)(aa₂)...(aa_k) ≡ (a₁)(a₂)...(a_k) (mod n). Rewriting this gives a^k(a₁)(a₂)...(a_k) ≡ (a₁)(a₂)...(a_k) (mod n). We can now divide each a_i on both sides of the congruence, which leaves a^k ≡ 1 (mod n). Since we defined k=φ(n) this gives exactly what we wanted to prove: a^φ(n) ≡ 1 (mod n).

The Mizar project has completely formalized and automatically checked a proof of Euler's theorem in the EULER_2 file.

External links