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

Contents

• Proofs
• Euler quotient
• References

where φ ( n ) is Euler's totient function. (The notation is explained in the article modular arithmetic.) In 1736, Leonhard Euler published his proof of Fermat's little theorem, which Fermat had presented without proof. Subsequently, Euler presented other proofs of the theorem, culminating with "Euler's theorem" in his paper of 1763, in which he attempted to find the smallest exponent for which Fermat's little theorem was always true.

The converse of Euler's theorem is also true: 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 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^{4 × 55 + 2} ≡ (7⁴)⁵⁵ × 7² ≡ 1⁵⁵ × 7² ≡ 49 ≡ 9 (mod 10).

Note that if a φ ( n ) ≡ 1 ( mod n ) , then also ( a φ ( n ) ) k ≡ 1 ( mod n ) for any positive k, because of

( a φ ( n ) ) k ≡ ( a φ ( n ) mod n ⋅ ( a φ ( n ) ) k − 1 mod n ) ≡ ( a φ ( n ) ) k − 1 ( mod n ) and so on.

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:

Euler's theorem also forms the basis of the RSA encryption system, where the net result of first encrypting a plaintext message, then later decrypting it, amounts to exponentiating a large input number by kφ(n) + 1, for some positive integer k. Euler's theorem then guarantees that the decrypted output number is equal to the original input number, giving back the plaintext.