Teorema lui Euler (teoria numerelor)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 6 mai 2022; verificarea necesită 1 editare .

Teorema lui Euler în teoria numerelor spune:

Dacă și sunt între prime , atunci unde este funcția Euler . $A$ $m$ $a^{\varphi(m)} \equiv 1 \pmod m$ $\varphi(m)$

O consecință importantă a teoremei lui Euler pentru cazul unui modul prim este mica teoremă a lui Fermat :

Dacă nu este divizibil cu un număr prim , atunci . $A$ $p$ $a^{{p-1}}\equiv 1{\pmod p}$

La rândul său, teorema lui Euler este o consecință a teoremei algebrice generale Lagrange , aplicată sistemului redus de reziduuri modulo . $m$

Dovezi

Folosind teoria numerelor

Fie toate numerele naturale distincte mai mici și relativ prime. $x_1, \dots, x_{\varphi(m)}$ $m$

Luați în considerare toate produsele posibile pentru toți de la până la . $x_i a$ $i$ $unu$ $\varphi(m)$

Deoarece este coprim cu , și coprim cu , atunci este , de asemenea, coprim cu , adică pentru unii . $A$ $m$ $x_{i}$ $m$ $x_i a$ $m$ $x_i a \equiv x_j\pmod m$ $j$

Rețineți că toate resturile atunci când sunt împărțite la sunt distincte. Într-adevăr, chiar dacă nu este așa, atunci există așa că $x_i a$ $m$ $i_1\neq i_2$

x_{i_1} a \equiv x_{i_2} a\pmod m

(x_{i_1} - x_{i_2}) a \equiv 0\pmod m.

Deoarece coprim cu , ultima egalitate este echivalentă cu faptul că $A$ $m$

x_{i_1} - x_{i_2} \equiv 0\pmod m

sau .

x_{i_1} \equiv x_{i_2}\pmod m

Acest lucru contrazice faptul că numerele sunt module distincte pe perechi . $x_1, \dots, x_{\varphi(m)}$ $m$

Înmulțim toate comparațiile din forma . Primim: $x_i a \equiv x_j\pmod m$

x_1 \cdots x_{\varphi(m)} a^{\varphi(m)} \equiv x_1 \cdots x_{\varphi(m)}\pmod m

x_1 \cdots x_{\varphi(m)} (a^{\varphi(m)}-1) \equiv 0\pmod m

Deoarece numărul este copprim cu , ultima comparație este echivalentă cu faptul că $x_1 \cdots x_{\varphi(m)}$ $m$

a^{\varphi(m)}-1 \equiv 0\pmod m

a^{\varphi(m)} \equiv 1\pmod m.

■

Cu ajutorul teoriei grupurilor

Se consideră grupul multiplicativ al elementelor inversabile ale $\mathbb Z_n^*$ inelului de reziduuri . Ordinea sa este egală conform definiției funcției Euler . Deoarece numărul este coprim cu , elementul corespunzător din este inversabil și aparține lui . Elementul generează un subgrup ciclic a cărui ordine, conform teoremei lui Lagrange , împarte , deci . ■ $\mathbb Z_n$ $\varphi (n)$ $A$ $n$ $\overline a$ $\mathbb Z_n$ $\mathbb Z_n^*$ $\overline{a}\in \mathbb Z_n^*$ $\varphi (n)$ $\overline a^{{\varphi (n)}}=\overline 1$

Vezi și

Lista obiectelor numite după Leonhard Euler

Literatură

Irlanda K., Rosen M. O introducere clasică în teoria numerelor moderne. — M .: Mir, 1987.

Link -uri

Subiecte: teorema lui Euler, teorema chineză a restului, Amir Kamil, CS70, toamna 2003. UC Berkeley
RSA și teorema chineză a restului / Matematică discretă pentru CS Lectura 12, Wagner, CS70, toamna 2003. UC Berkeley