Teorema di Eulero (aritmetica modulare)

In matematica, e in particolare in teoria dei numeri, il teorema di Eulero (detto anche teorema di Fermat-Eulero) afferma che se $n$ è un intero positivo ed $a$ è coprimo rispetto ad $n$, allora:

$a^{\varphi (n)}\equiv 1modn$

dove $\varphi (n)$ indica la funzione phi di Eulero e $\equiv$ la relazione di congruenza modulo $n$.

Questo teorema è una generalizzazione del piccolo teorema di Fermat, ed è ulteriormente generalizzato dal teorema di Carmichael.

Dimostrazione

Consideriamo l'insieme delle classi di resto (modulo $n$) degli interi positivi minori o uguali ad $n$ e coprimi con $n$:

$S_1=\{[m_1],[m_2],\dots ,[m_{\varphi (n)}]\}$

Se moltiplichiamo ogni elemento di $S_1$ per $a$ otterremo un secondo insieme,

$S_2=\{[a{m}_1],[a{m}_2],\dots ,[a{m}_{\varphi (n)}]\}$.

Ogni $a{m}_i$ è ancora coprimo con $n$ perché è prodotto di due elementi coprimi con $n$: infatti ogni numero primo $p$ che divide $a{m}_i$ divide o $a$ o $m_i$, e quindi se dividesse anche $n$ almeno uno tra $a$ ed $m_i$ non sarebbe coprimo con $n$.

Se ora $i\ne j$, allora $a{m}_i\equiv ̸a{m}_{j}modn$, perché altrimenti, moltiplicando per l'inverso $b$ di $a$ modulo $n$ (che esiste perché $a$ ed $n$ sono coprimi), si avrebbe $ba{m}_i\equiv ba{m}_{j}modn$ e quindi $m_i\equiv m_{j}modn$. Questi due fatti implicano che $S_2$ è un sottoinsieme di $S_1$ e ha la stessa cardinalità di $S_1$: di conseguenza, $S_1$ ed $S_2$ coincidono.

Pertanto il prodotto, di tutti gli elementi di $S_1$ è congruente al prodotto di tutti gli elementi di $S_2$:

$m_1{m}_2\cdot \dots \cdot m_{\varphi (n)}\equiv a{m}_1\cdot a{m}_2\cdot \dots \cdot a{m}_{\varphi (n)}\equiv a^{\varphi (n)}{m}_1\cdot m_2\cdot \dots \cdot m_{\varphi (n)}modn$.

Poiché ogni $m_i$ è primo con $n$, possiamo moltiplicare ambo i membri per l'inversa di $\prod _{i=1}^{\varphi (n)}{m}_i$ modulo $n$, ottenendo

$a^{\varphi (n)}\equiv 1modn$.

Una dimostrazione meno diretta può essere ottenuta attraverso la teoria dei gruppi. L'insieme $S_1$ delle classi di resto modulo $n$, infatti, è un gruppo abeliano sotto l'operazione di moltiplicazione, ed ha ordine $\varphi (n)$. Un qualsiasi elemento $a\in S_1$ genera un sottogruppo il cui ordine $m$, per il teorema di Lagrange, divide $\varphi (n)$. Per definizione, $a^m\equiv 1modn$, e, se $\varphi (n)=mr$, allora quindi $a^{\varphi (n)}=(a^m{)}^r\equiv 1^{r}modn\equiv 1modn$.

Generalizzazioni

La dimostrazione "aritmetica" del teorema di Eulero può essere applicata, più in generale, a tutti i gruppi abeliani finiti, senza invocare il teorema di Lagrange. In questo contesto, il teorema afferma che, se $a\in G$ e l'ordine di $G$ è $n$, allora $a^n=e$ (dove $e$ è l'elemento neutro del gruppo).

Esempi di utilizzo

Il teorema può essere usato per ridurre facilmente grandi potenze in modulo n. Ad esempio, prendiamo in considerazione la ricerca dell'ultima cifra di $7^{222}$, vale a dire di $7^{222}mod10$. 7 e 10 sono coprimi, e $\varphi (10)=4$. Dal teorema di Eulero segue che $7^4\equiv 1mod10$, e quindi $7^{222}\equiv 7^{4\cdot 55+2}\equiv (7^4{)}^{55}\cdot 7^2\equiv 1^{55}\cdot 7^2\equiv 49\equiv 9mod10$.

In generale, nella riduzione di una potenza di $a$ modulo $n$, $a^x\equiv a^{y}modn$, dove $y\equiv xmod\varphi (n)$.

Bibliografia

• Template:Cita libro

Voci correlate

• Eulero
• Funzione φ di Eulero
• Piccolo teorema di Fermat
• Funzione di Carmichael

Collegamenti esterni

• Template:Collegamenti esterni