Английская Википедия:Euler's theorem

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description Шаблон:About In number theory, Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem) states that, if Шаблон:Math and Шаблон:Math are coprime positive integers, then <math>a^{\varphi(n)}</math> is congruent to <math>1</math> modulo Шаблон:Math, where <math>\varphi</math> denotes Euler's totient function; that is

<math>a^{\varphi (n)} \equiv 1 \pmod{n}.</math>

In 1736, Leonhard Euler published a proof of Fermat's little theorem (stated by Fermat without proof), which is the restriction of Euler's theorem to the case where Шаблон:Mvar is a prime number. Subsequently, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where Шаблон:Mvar is not prime.

The converse of Euler's theorem is also true: if the above congruence is true, then <math>a</math> and <math>n</math> must be coprime.

The theorem is further generalized by some Carmichael's theorems.

The theorem may be used to easily reduce large powers modulo <math>n</math>. For example, consider finding the ones place decimal digit of <math>7^{222}</math>, i.e. <math>7^{222} \pmod{10}</math>. The integers 7 and 10 are coprime, and <math>\varphi(10) = 4</math>. So Euler's theorem yields <math>7^4 \equiv 1 \pmod{10}</math>, and we get <math>7^{222} \equiv 7^{4 \times 55 + 2} \equiv (7^4)^{55} \times 7^2 \equiv 1^{55} \times 7^2 \equiv 49 \equiv 9 \pmod{10}</math>.

In general, when reducing a power of <math>a</math> modulo <math>n</math> (where <math>a</math> and <math>n</math> are coprime), one needs to work modulo <math>\varphi(n)</math> in the exponent of <math>a</math>:

if <math>x \equiv y \pmod{\varphi(n)}</math>, then <math>a^x \equiv a^y \pmod{n}</math>.

Euler's theorem underlies the RSA cryptosystem, which is widely used in Internet communications. In this cryptosystem, Euler's theorem is used with Шаблон:Mvar being a product of two large prime numbers, and the security of the system is based on the difficulty of factoring such an integer.

Proofs

1. Euler's theorem can be proven using concepts from the theory of groups: The residue classes modulo Шаблон:Mvar that are coprime to Шаблон:Mvar form a group under multiplication (see the article Multiplicative group of integers modulo n for details). The order of that group is Шаблон:Math. Lagrange's theorem states that the order of any subgroup of a finite group divides the order of the entire group, in this case Шаблон:Math. If Шаблон:Mvar is any number coprime to Шаблон:Mvar then Шаблон:Mvar is in one of these residue classes, and its powers Шаблон:Math modulo Шаблон:Mvar form a subgroup of the group of residue classes, with Шаблон:Math. Lagrange's theorem says Шаблон:Mvar must divide Шаблон:Math, i.e. there is an integer Шаблон:Mvar such that Шаблон:Math. This then implies,

<math>a^{\varphi(n)} = a^{kM} = (a^{k})^M \equiv 1^M =1 \pmod{n}.</math>

2. There is also a direct proof: Let Шаблон:Math be a reduced residue system (Шаблон:Math) and let Шаблон:Mvar be any integer coprime to Шаблон:Mvar. The proof hinges on the fundamental fact that multiplication by Шаблон:Mvar permutes the Шаблон:Mvar: in other words if Шаблон:Math then Шаблон:Math. (This law of cancellation is proved in the article Multiplicative group of integers modulo n.) That is, the sets Шаблон:Mvar and Шаблон:Math, considered as sets of congruence classes (Шаблон:Math), are identical (as sets—they may be listed in different orders), so the product of all the numbers in Шаблон:Mvar is congruent (Шаблон:Math) to the product of all the numbers in Шаблон:Mvar:

<math>

\prod_{i=1}^{\varphi(n)} x_i \equiv \prod_{i=1}^{\varphi(n)} ax_i = a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n}, </math> and using the cancellation law to cancel each Шаблон:Mvar gives Euler's theorem:

<math>

a^{\varphi(n)}\equiv 1 \pmod{n}. </math>

See also

• Carmichael function
• Euler's criterion
• Fermat's little theorem
• 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.

• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation
• Шаблон:Citation

External links

• Шаблон:Mathworld
• Euler-Fermat Theorem at PlanetMath