Théorème d'Euler

Euler's theorem This article is about Euler's theorem in number theory. Pour d'autres usages, see List of things named after Leonhard Euler § Theorems.

In number theory, Théorème d'Euler (also known as the Fermat–Euler theorem or Euler's totient theorem) stipule que, if n and a are coprime positive integers, et {style d'affichage varphi (n)} is Euler's totient function, then a raised to the power {style d'affichage varphi (n)} est conforme à 1 modulo n; C'est {style d'affichage a^{varphi (n)}équiv 1{pmod {n}}.} Dans 1736, Leonhard Euler published a proof of Fermat's little theorem[1] (stated by Fermat without proof), which is the restriction of Euler's theorem to the case where n is a prime number. Ensuite, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where n is not prime.[2] The converse of Euler's theorem is also true: if the above congruence is true, alors {style d'affichage a} et {displaystyle n} must be coprime.

The theorem is further generalized by Carmichael's theorem.

The theorem may be used to easily reduce large powers modulo {displaystyle n} . Par exemple, consider finding the ones place decimal digit of {displaystyle 7^{222}} , c'est à dire. {displaystyle 7^{222}{pmod {10}}} . The integers 7 et 10 are coprime, et {style d'affichage varphi (10)=4} . So Euler's theorem yields {displaystyle 7^{4}équiv 1{pmod {10}}} , and we get {displaystyle 7^{222}equiv 7^{4fois 55+2}équiv (7^{4})^{55}times 7^{2}equiv 1^{55}times 7^{2}equiv 49equiv 9{pmod {10}}} .

En général, when reducing a power of {style d'affichage a} modulo {displaystyle n} (où {style d'affichage a} et {displaystyle n} are coprime), one needs to work modulo {style d'affichage varphi (n)} in the exponent of {style d'affichage a} : si {displaystyle xequiv y{pmod {varphi (n)}}} , alors {style d'affichage a^{X}equiv a^{y}{pmod {n}}} .

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

Contenu 1 Preuves 2 Voir également 3 Remarques 4 Références 5 External links Proofs 1. Euler's theorem can be proven using concepts from the theory of groups:[3] The residue classes modulo 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 modulo n form a subgroup of the group of residue classes, with ak ≡ 1 (mod n). Lagrange's theorem says k must divide φ(n), c'est à dire. there is an integer M such that kM = φ(n). This then implies, {style d'affichage a^{varphi (n)}=un^{kM}=(un ^{k})^{M}equiv 1^{M}=1equiv 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]) C'est-à-dire, 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: {displaystyle prod _{je=1}^{varphi (n)}X_{je}equiv prod _{je=1}^{varphi (n)}ax_{je}=un^{varphi (n)}produit _{je=1}^{varphi (n)}X_{je}{pmod {n}},} and using the cancellation law to cancel each xi gives Euler's theorem: {style d'affichage a^{varphi (n)}équiv 1{pmod {n}}.} See also Carmichael function Euler's criterion Fermat's little theorem Wilson's theorem Notes ^ See: Léonhard Euler (presented: Août 2, 1736; publié: 1741) "Theorematum quorundam ad numeros primos spectantium demonstratio" (A proof of certain theorems regarding prime numbers), Commentarii academiae scientiarum Petropolitanae, 8 : 141–146. For further details on this paper, including an English translation, voir: The Euler Archive. ^ See: L. Euler (publié: 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 "Théorème 11" sur la page 102. This paper was first presented to the Berlin Academy on June 8, 1758 and to the St. Académie de Saint-Pétersbourg en octobre 15, 1759. In this paper, Euler's totient function, {style d'affichage varphi (n)} , is not named but referred to as "numerus partium ad N primarum" (the number of parts prime to N; C'est, the number of natural numbers that are smaller than N and relatively prime to N). For further details on this paper, voir: The Euler Archive. For a review of Euler's work over the years leading to Euler's theorem, voir: Ed Sandifer (2005) "Euler's proof of Fermat's little theorem" Archivé 2006-08-28 at the Wayback Machine ^ Ireland & Rosen, corr. 1 to prop 3.3.2 ^ Hardy & Wright, thm. 72 ^ Landau, thm. 75 ^ 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.

Gauss, Carl Friedrich; Clarke, Arthur A. (translated into English) (1986), Disquisitiones Arithemeticae (Deuxième, corrected edition), New York: Springer, ISBN 0-387-96254-9 Gauss, Carl Friedrich; Maser, H. (translated 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: Presse universitaire d'Oxford, ISBN 978-0-19-853171-5 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". MathWorld. Euler-Fermat Theorem at PlanetMath hide vte Leonhard Euler Euler–Lagrange equationEuler–Lotka equationEuler–Maclaurin formulaEuler–Maruyama methodEuler–Mascheroni constantEuler–Poisson–Darboux equationEuler–Rodrigues formulaEuler–Tricomi equationEuler's continued fraction formulaEuler's critical loadEuler's formulaEuler's four-square identityEuler's identityEuler's pump and turbine equationEuler's rotation theoremEuler's sum of powers conjectureEuler's theoremEuler equations (dynamique des fluides)Fonction d'EulerMéthode d'EulerNombre d'EulerNombre d'Euler (la physique)Euler–Bernoulli beam theoryNamesakes Category Portal: Mathematics Categories: Modular arithmeticTheorems in number theoryLeonhard Euler