Teorema lui Euler (aritmetica)
În matematică , teorema lui Euler sau Euler-Fermat în aritmetică modulară , publicată în 1761 de matematicianul elvețian Leonhard Euler , citește:
Pentru orice număr întreg n > 0 și orice număr întreg un prim cu n (cu alte cuvinte: mod inversabil n ),
laφ(nu)≡1(modnu){\ displaystyle a ^ {\ varphi (n)} \ equiv 1 {\ pmod {n}}}
unde φ este funcția indicator a lui Euler și mod denotă congruență față de numere întregi .
Această teoremă este o generalizare a teoremei lui Fermat, care se referă doar la cazul în care n este un număr prim .
Înseamnă că exponentul λ ( n ) (numit indicatorul Carmichael al lui n ) al grupului (ℤ / n ℤ) × al inversibilelor inelului ℤ / n ℤ este un divizor al ordinului φ ( n ) al acestui grup (această proprietate, comună tuturor grupurilor finite , este dedusă din teorema Lagrange asupra grupurilor ).
Permite reducerea puterii modulo n . De exemplu, dacă vrem să găsim cifra unităților de 7 222 , adică să aflăm la ce număr între 0 și 9 este congruent 7 222 modulo 10, este suficient să vedem că 7 și 10 sunt prime între ele și că φ (10) = 4 . Teorema lui Euler ne spune deci că
74≡1(mod10).{\ displaystyle 7 ^ {4} \ equiv 1 {\ pmod {10}}.}
Deducem asta
7222≡74×55+2≡(74)55×72≡155×72≡49≡9(mod10).{\ displaystyle 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}}.}
Prin urmare, numărul căutat este de 9.
O altă demonstrație
Există multe dovezi ale acestei teoreme. Am furnizat deja mai sus ceea ce generalizează dovada micii teoreme a lui Fermat prin teorema lui Lagrange . De asemenea, putem generaliza dovada aritmetică elementară :
Fie n > 0 și a un număr întreg întreg cu n . Rețineți , în special, clasa modulo a unui întreg .
la¯{\ displaystyle {\ overline {a}}}nu{\ displaystyle n}la{\ displaystyle a}la¯∈(Z/nuZ)×{\ displaystyle {\ overline {a}} \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}}
Bijecția vă permite să rescrieți produsul :
(Z/nuZ)×→(Z/nuZ)×,X↦la¯X{\ displaystyle \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times} \ to \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times }, \; x \ mapsto {\ overline {a}} x}P: =∏X∈(Z/nuZ)×X{\ displaystyle P: = \ prod _ {x \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}} x}
P=∏X∈(Z/nuZ)×(la¯X)=la¯Card((Z/nuZ)×)P=la¯φ(nu)P{\ displaystyle P \; = \ prod _ {x \ in \ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times}} \ left ({\ overline {a}} x \ dreapta) = \; {\ overline {a}} ^ {\ operatorname {Card} \ left (\ left (\ mathbb {Z} / n \ mathbb {Z} \ right) ^ {\ times} \ right)} P \; = {\ overline {a}} ^ {\ varphi (n)} P}.
Încheiem prin simplificarea prin inversabil :
P{\ displaystyle P}
1¯=la¯φ(nu)=laφ(nu)¯{\ displaystyle {\ overline {1}} = {\ overline {a}} ^ {\ varphi (n)} = {\ overline {a ^ {\ varphi (n)}}}}.
Referinţă
-
(La) L. Euler, " Theoremata arithmetica nova methodo demonstrata " , Novi Comment. Acad. Știință. Imp. Petrop. , vol. 8,1763, p. 74-104 ( citiți online )( E271 , scris în 1758 și prezentat în 1760 ).
Articol asociat
Ordinea multiplicativă
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">