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.) In 1736, Leonhard Euler published his proof of Fermat's little theorem,[1] 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.[2]

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

Note that if a^{\varphi (n)} \equiv 1 \pmod{n}, then also (a^{\varphi (n)})^k \equiv 1 \pmod{n} for any positive k, because of

(a^{\varphi (n)})^k  \equiv  (a^{\varphi (n)}\,\bmod\,n  \cdot\,(a^{\varphi (n)})^{k-1}\,\bmod\,n ) \equiv (a^{\varphi (n)})^{k-1}\pmod{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:

if xy (mod φ(n)), then axay (mod n).

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.

Proofs

1. Euler's theorem can be proven using concepts from the theory of groups:[3] 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.) The order of that group is φ(n). 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, ..., ak 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 = 
1^M =
1 \equiv 
1 \pmod{n}.

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:


\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 xis gives Euler's theorem:

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

See also

Notes

  1. See:
  2. See:
    • L. Euler (published: 1763) "Theoremata arithmetica nova methodo demonstrata" (Proof of a new method in the theory of arithmetic), Novi Commentarii academiae scientiarum Petropolitanae, 8 : 74–104. Euler's theorem appears as "Theorema 11" on page 102. This paper was first presented to the Berlin Academy on June 8, 1758 and to the St. Petersburg Academy on October 15, 1759. In this paper, Euler's totient function, φ(n), is not named but referred to as "numerus partium ad N primarum" (the number of parts prime to N; that is, the number of natural numbers that are smaller than N and relatively prime to N).
    • For further details on this paper, see: The Euler Archive.
    • For a review of Euler's work over the years leading to Euler's theorem, see: Ed Sandifer (2005) "Euler's proof of Fermat's little theorem"
  3. Ireland & Rosen, corr. 1 to prop 3.3.2
  4. Hardy & Wright, thm. 72
  5. Landau, thm. 75
  6. See Bézout's lemma

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.

External links

This article is issued from Wikipedia - version of the Thursday, May 05, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.