Teorema lui Euler (aritmetica modulară)

În matematică și în special în teoria numerelor , teorema lui Euler (numită și teorema Fermat-Euler ) afirmă că dacă $n$ ${\ displaystyle n}$ $n$ este un număr întreg pozitiv și $la$ ${\ displaystyle a}$ $la$ este coprimo cu privire la $n$ ${\ displaystyle n}$ $n$ , asa de:

a^{\phi (n)}\equiv 1{\bmod {n}}

{\ displaystyle a ^ {\ phi (n)} \ equiv 1 {\ bmod {n}}}

{\ displaystyle a ^ {\ phi (n)} \ equiv 1 {\ bmod {n}}}

unde este $\phi (n)$ ${\ displaystyle \ phi (n)}$ $\ phi (n)$ denotă funcția lui Euler phi e $\equiv$ ${\ displaystyle \ equiv}$ $\ equiv$ relația de congruență modulo $n$ ${\ displaystyle n}$ $n$ .

Această teoremă este o generalizare a teoremei lui Fermat și este generalizată în continuare de teorema lui Carmichael .

Demonstrație

Să luăm în considerare setul de clase de rest (modulo $n$ ${\ displaystyle n}$ $n$ ) de numere întregi pozitive mai mici sau egale cu $n$ ${\ displaystyle n}$ $n$ și acoperă-mă cu $n$ ${\ displaystyle n}$ $n$ :

S_{1}=\left\{[m_{1}],[m_{2}],\dots ,[m_{\phi (n)}]\right\}

{\ displaystyle S_ {1} = \ left \ {[m_ {1}], [m_ {2}], \ dots, [m _ {\ phi (n)}] \ right \}}

{\ displaystyle S_ {1} = \ left \ {[m_ {1}], [m_ {2}], \ dots, [m _ {\ phi (n)}] \ right \}}

Dacă înmulțim fiecare element al $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ pentru $la$ ${\ displaystyle a}$ $la$ vom primi o secundă împreună,

S_{2}=\left\{[am_{1}],[am_{2}],\dots ,[am_{\phi (n)}]\right\}

{\ displaystyle S_ {2} = \ left \ {[am_ {1}], [am_ {2}], \ dots, [am _ {\ phi (n)}] \ right \}}

{\ displaystyle S_ {2} = \ left \ {[am_ {1}], [am_ {2}], \ dots, [am _ {\ phi (n)}] \ right \}}

.

Fiecare $am_{i}$ ${\ displaystyle am_ {i}}$ ${\ displaystyle am_ {i}}$ este încă coprimo con $n$ ${\ displaystyle n}$ $n$ pentru că este produs din două elemente cu care mă acoper $n$ ${\ displaystyle n}$ $n$ : de fapt fiecare număr prim $p$ ${\ displaystyle p}$ $p$ care împarte $am_{i}$ ${\ displaystyle am_ {i}}$ ${\ displaystyle am_ {i}}$ împarte sau $la$ ${\ displaystyle a}$ $la$ sau $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine$ și, prin urmare, dacă s-a împărțit și $n$ ${\ displaystyle n}$ $n$ cel puțin unul dintre $la$ ${\ displaystyle a}$ $la$ și $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine$ nu ar fi acoperit cu $n$ ${\ displaystyle n}$ $n$ .

Dacă acum $i\neq j$ ${\ displaystyle i \ neq j}$ $i \ neq j$ , asa de $am_{i}\not \equiv am_{j}{\bmod {n}}$ ${\ displaystyle am_ {i} \ not \ equiv am_ {j} {\ bmod {n}}}$ ${\ displaystyle am_ {i} \ not \ equiv am_ {j} {\ bmod {n}}}$ , pentru că altfel, înmulțindu-se cu inversul $b$ ${\ displaystyle b}$ $b$ din $la$ ${\ displaystyle a}$ $la$ modul $n$ ${\ displaystyle n}$ $n$ (care există pentru că $la$ ${\ displaystyle a}$ $la$ și $n$ ${\ displaystyle n}$ $n$ sunt coprimă), ai avea $bam_{i}\equiv bam_{j}{\bmod {n}}$ ${\ displaystyle bam_ {i} \ equiv bam_ {j} {\ bmod {n}}}$ ${\ displaystyle bam_ {i} \ equiv bam_ {j} {\ bmod {n}}}$ prin urmare $m_{i}\equiv m_{j}{\bmod {n}}$ ${\ displaystyle m_ {i} \ equiv m_ {j} {\ bmod {n}}}$ ${\ displaystyle m_ {i} \ equiv m_ {j} {\ bmod {n}}}$ . Aceste două fapte implică faptul că $S_{2}$ ${\ displaystyle S_ {2}}$ $S_2$ este un subset de $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ și are aceeași cardinalitate ca $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ : în consecință, $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ și $S_{2}$ ${\ displaystyle S_ {2}}$ $S_2$ coincide.

Prin urmare produsul, din toate elementele $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ este congruent cu produsul tuturor elementelor din $S_{2}$ ${\ displaystyle S_ {2}}$ $S_2$ :

m_{1}m_{2}\cdot \dots \cdot m_{\phi (n)}\equiv am_{1}\cdot am_{2}\cdot \dots \cdot am_{\phi (n)}\equiv a^{\phi (n)}m_{1}\cdot m_{2}\cdot \dots \cdot m_{\phi (n)}{\bmod {n}}

{\ displaystyle m_ {1} m_ {2} \ cdot \ dots \ cdot m _ {\ phi (n)} \ equiv am_ {1} \ cdot am_ {2} \ cdot \ dots \ cdot am _ {\ phi ( n)} \ equiv a ^ {\ phi (n)} m_ {1} \ cdot m_ {2} \ cdot \ dots \ cdot m _ {\ phi (n)} {\ bmod {n}}}

{\ displaystyle m_ {1} m_ {2} \ cdot \ dots \ cdot m _ {\ phi (n)} \ equiv am_ {1} \ cdot am_ {2} \ cdot \ dots \ cdot am _ {\ phi ( n)} \ equiv a ^ {\ phi (n)} m_ {1} \ cdot m_ {2} \ cdot \ dots \ cdot m _ {\ phi (n)} {\ bmod {n}}}

.

Din moment ce fiecare $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine$ este primul cu $n$ ${\ displaystyle n}$ $n$ , putem înmulți ambele părți cu inversul lui $\prod _{i=1}^{\phi (n)}m_{i}$ ${\ displaystyle \ prod _ {i = 1} ^ {\ phi (n)} m_ {i}}$ ${\ displaystyle \ prod _ {i = 1} ^ {\ phi (n)} m_ {i}}$ modul $n$ ${\ displaystyle n}$ $n$ , primind

a^{\phi (n)}\equiv 1{\bmod {n}}

{\ displaystyle a ^ {\ phi (n)} \ equiv 1 {\ bmod {n}}}

{\ displaystyle a ^ {\ phi (n)} \ equiv 1 {\ bmod {n}}}

.

O dovadă mai puțin directă poate fi obținută prin teoria grupurilor. Întregul $S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$ din restul claselor modulo $n$ ${\ displaystyle n}$ $n$ , de fapt, este un grup abelian aflat sub operația de multiplicare și are ordine $\phi (n)$ ${\ displaystyle \ phi (n)}$ $\ phi (n)$ . Orice element $a\in S_{1}$ ${\ displaystyle a \ în S_ {1}}$ ${\ displaystyle a \ în S_ {1}}$ generează un subgrup a cărui ordine $m$ ${\ displaystyle m}$ $m$ , prin teorema lui Lagrange , împarte $\phi (n)$ ${\ displaystyle \ phi (n)}$ $\ phi (n)$ . Pentru definiție, $a^{m}\equiv 1{\bmod {n}}$ ${\ displaystyle a ^ {m} \ equiv 1 {\ bmod {n}}}$ ${\ displaystyle a ^ {m} \ equiv 1 {\ bmod {n}}}$ , si daca $\phi (n)=mr$ ${\ displaystyle \ phi (n) = mr}$ ${\ displaystyle \ phi (n) = mr}$ , apoi atunci $a^{\phi (n)}=(a^{m})^{r}\equiv 1^{r}{\bmod {n}}\equiv 1{\bmod {n}}$ ${\ displaystyle a ^ {\ phi (n)} = (a ^ {m}) ^ {r} \ equiv 1 ^ {r} {\ bmod {n}} \ equiv 1 {\ bmod {n}}}$ ${\ displaystyle a ^ {\ phi (n)} = (a ^ {m}) ^ {r} \ equiv 1 ^ {r} {\ bmod {n}} \ equiv 1 {\ bmod {n}}}$ .

Generalizări

Dovada „aritmetică” a teoremei lui Euler poate fi aplicată, mai general, tuturor grupurilor abeliene finite, fără a invoca teorema lui Lagrange. În acest context, teorema afirmă că, dacă $a\in G$ ${\ displaystyle a \ în G}$ ${\ displaystyle a \ în G}$ și ordinea $G.$ ${\ displaystyle G}$ $G.$ Și $n$ ${\ displaystyle n}$ $n$ , asa de $a^{n}=e$ ${\ displaystyle a ^ {n} = e}$ $a ^ {n} = e$ (unde este $Și$ ${\ displaystyle e}$ $Și$ este elementul neutru al grupului).

Exemple de utilizare

Teorema poate fi utilizată pentru a reduce cu ușurință puterile mari la modulul n . De exemplu, să luăm în considerare căutarea ultimei cifre a $7^{222}$ ${\ displaystyle 7 ^ {222}}$ ${\ displaystyle 7 ^ {222}}$ , și anume de $7^{222}{\bmod {1}}0$ ${\ displaystyle 7 ^ {222} {\ bmod {1}} 0}$ ${\ displaystyle 7 ^ {222} {\ bmod {1}} 0}$ . 7 și 10 sunt coprimă și $\phi (10)=4$ ${\ displaystyle \ phi (10) = 4}$ ${\ displaystyle \ phi (10) = 4}$ . Din teorema lui Euler rezultă că $7^{4}\equiv 1{\bmod {1}}0$ ${\ displaystyle 7 ^ {4} \ equiv 1 {\ bmod {1}} 0}$ ${\ displaystyle 7 ^ {4} \ equiv 1 {\ bmod {1}} 0}$ , și apoi $7^{222}\equiv 7^{4\cdot 55+2}\equiv (7^{4})^{55}\cdot 7^{2}\equiv 1^{55}\cdot 7^{2}\equiv 49\equiv 9{\bmod {1}}0$ ${\ displaystyle 7 ^ {222} \ equiv 7 ^ {4 \ cdot 55 + 2} \ equiv (7 ^ {4}) ^ {55} \ cdot 7 ^ {2} \ equiv 1 ^ {55} \ cdot 7 ^ {2} \ equiv 49 \ equiv 9 {\ bmod {1}} 0}$ ${\ displaystyle 7 ^ {222} \ equiv 7 ^ {4 \ cdot 55 + 2} \ equiv (7 ^ {4}) ^ {55} \ cdot 7 ^ {2} \ equiv 1 ^ {55} \ cdot 7 ^ {2} \ equiv 49 \ equiv 9 {\ bmod {1}} 0}$ .

În general, în reducerea unei puteri de $la$ ${\ displaystyle a}$ $la$ modul $n$ ${\ displaystyle n}$ $n$ , $a^{x}\equiv a^{y}{\bmod {n}}$ ${\ displaystyle a ^ {x} \ este egal cu ^ {y} {\ bmod {n}}}$ ${\ displaystyle a ^ {x} \ este egal cu ^ {y} {\ bmod {n}}}$ , unde este $y\equiv x{\bmod {\phi }}(n)$ ${\ displaystyle y \ equiv x {\ bmod {\ phi}} (n)}$ ${\ displaystyle y \ equiv x {\ bmod {\ phi}} (n)}$ .

Bibliografie

Harold Davenport , Arithmetic Superior , Bologna, Zanichelli, 1994, ISBN 88-08-09154-6 .

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică