Teorema di Eulero

Euler's theorem This article is about Euler's theorem in number theory. Per altri usi, see List of things named after Leonhard Euler § Theorems.

In number theory, Teorema di Eulero (also known as the Fermat–Euler theorem or Euler's totient theorem) afferma che, if n and a are coprime positive integers, e {stile di visualizzazione varphi (n)} is Euler's totient function, then a raised to the power {stile di visualizzazione varphi (n)} è congruente a 1 modulo n; questo è {stile di visualizzazione a^{varfi (n)}equivalente 1{pmod {n}}.} In 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. Successivamente, 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, poi {stile di visualizzazione a} e {stile di visualizzazione n} must be coprime.

The theorem is further generalized by Carmichael's theorem.

The theorem may be used to easily reduce large powers modulo {stile di visualizzazione n} . Per esempio, consider finding the ones place decimal digit of {displaystyle 7^{222}} , cioè. {displaystyle 7^{222}{pmod {10}}} . The integers 7 e 10 are coprime, e {stile di visualizzazione varphi (10)=4} . So Euler's theorem yields {displaystyle 7^{4}equivalente 1{pmod {10}}} , and we get {displaystyle 7^{222}equiv 7^{4volte 55+2}equivalente (7^{4})^{55}times 7^{2}equiv 1^{55}times 7^{2}equiv 49equiv 9{pmod {10}}} .

In generale, when reducing a power of {stile di visualizzazione a} modulo {stile di visualizzazione n} (dove {stile di visualizzazione a} e {stile di visualizzazione n} are coprime), one needs to work modulo {stile di visualizzazione varphi (n)} in the exponent of {stile di visualizzazione a} : Se {displaystyle xequiv y{pmod {varfi (n)}}} , poi {stile di visualizzazione 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.

Contenuti 1 Prove 2 Guarda anche 3 Appunti 4 Riferimenti 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), cioè. there is an integer M such that kM = φ(n). This then implies, {stile di visualizzazione a^{varfi (n)}=a^{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]) Questo è, 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: {stile di visualizzazione prod_{io=1}^{varfi (n)}X_{io}equiv prod _{io=1}^{varfi (n)}ax_{io}=a^{varfi (n)}pungolo _{io=1}^{varfi (n)}X_{io}{pmod {n}},} and using the cancellation law to cancel each xi gives Euler's theorem: {stile di visualizzazione a^{varfi (n)}equivalente 1{pmod {n}}.} See also Carmichael function Euler's criterion Fermat's little theorem Wilson's theorem Notes ^ See: Leonhard Euler (presented: agosto 2, 1736; pubblicato: 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, vedere: The Euler Archive. ^ Vedi: l. Euler (pubblicato: 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" alla pagina 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, {stile di visualizzazione varphi (n)} , is not named but referred to as "numerus partium ad N primarum" (the number of parts prime to N; questo è, the number of natural numbers that are smaller than N and relatively prime to N). For further details on this paper, vedere: The Euler Archive. For a review of Euler's work over the years leading to Euler's theorem, vedere: Ed Sandifer (2005) "Euler's proof of Fermat's little theorem" Archiviato 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 (Secondo, 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), Un'introduzione alla teoria dei numeri (Fifth edition), Oxford: la stampa dell'università di 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, Edmondo (1966), Elementary Number Theory, New York: Chelsea External links Weisstein, Eric W. "Euler's Totient Theorem". Math World. 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 (fluid dynamics)Euler functionEuler methodEuler numbersEuler number (fisica)Euler–Bernoulli beam theoryNamesakes Category Portal: Mathematics Categories: Modular arithmeticTheorems in number theoryLeonhard Euler