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 and a are coprime positive integers, then

where φ(n) is Euler's totient function. (The notation is explained in the article Modular arithmetic.) It was first stated and proved by Leonhard Euler in 1736.

There is a converse of Euler's theorem: if the above congruence is true then a and n must be coprime.

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 ones place decimal digit of 7222, i.e. 7222 (mod 10). Note that 7 and 10 are coprime, and φ(10) = 4. So Euler's theorem yields 74 ≡ 1 (mod 10), and we get 7222 ≡ 74×55 + 2 ≡ (74)55×72 ≡ 155×72 ≡ 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 ax ≡ ay (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 kφ(n)+1 for some positive integer k, so Euler's theorem shows that the decrypted result is the same as the original.