Euler's theorem

This article is about Euler's theorem in number theory. For other meanings, see List of topics named after Leonhard Euler.

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

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

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 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).

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 kφ(n)+1 for some positive integer k, so Euler's theorem shows that the decrypted result is the same as the original.

Proofs

1. Euler's theorem can be proven using concepts from the theory of groups: The residue classes (mod n) that are coprime to n form a group under multiplication (see the article Multiplicative group of integers modulo n for details.) 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, a², ..., a^k ≡ 1 (mod n) are a subgroup. Lagrange's theorem says k must divide φ(n), i.e. there is an integer M such that kM = φ(n). But then,

$a^{\varphi(n)} = a^{kM} = (a^{k})^M \equiv 1^M = 1 \pmod{n}.$

2. There is also a direct proof: Let R = {x₁, x₂, ..., 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 x_i: in other words if ax_j ≡ ax_k (mod n) then j = k. (This law of cancellation is proved in the article Multiplicative group of integers modulo n.) That is, the sets R and aR = {ax₁, ax₂, ..., 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:

$\prod_{i=1}^{\varphi(n)} x_i \equiv \prod_{i=1}^{\varphi(n)} ax_i \equiv a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n},$ and using the cancellation law to cancel the x_is gives Euler's theorem:

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

See also

• Euler's criterion
• Wilson's theorem

References

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549 

• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 

• Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715 

• Ireland, Kenneth; Rosen, Michael (1990), A Classical Introduction to Modern Number Theory (Second edition), New York: Springer, ISBN 0-387-97329-X 

• Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea 

External links

• Weisstein, Eric W., "Euler's Totient Theorem" from MathWorld.
• Euler's Theorem at PlanetMath