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^{\phi (n)}\equiv 1{\bmod {n}}$

dove $\phi (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}=\left\{[m_{1}],[m_{2}],\dots ,[m_{\phi (n)}]\right\}$

Se moltiplichiamo ogni elemento di $S_{1}$ per $a$ otterremo un secondo insieme,

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

Ogni $am_{i}$ è ancora coprimo con $n$ perché è prodotto di due elementi coprimi con $n$: infatti ogni numero primo $p$ che divide $am_{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\neq j$, allora $am_{i}\not \equiv am_{j}{\bmod {n}}$, perché altrimenti, moltiplicando per l'inverso $b$ di $a$ modulo $n$ (che esiste perché $a$ ed $n$ sono coprimi), si avrebbe $bam_{i}\equiv bam_{j}{\bmod {n}}$ e quindi $m_{i}\equiv m_{j}{\bmod {n}}$. 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_{\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}}$.

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

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

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 $\phi (n)$. Un qualsiasi elemento $a\in S_{1}$ genera un sottogruppo il cui ordine $m$, per il teorema di Lagrange, divide $\phi (n)$. Per definizione, $a^{m}\equiv 1{\bmod {n}}$, e, se $\phi (n)=mr$, allora quindi $a^{\phi (n)}=(a^{m})^{r}\equiv 1^{r}{\bmod {n}}\equiv 1{\bmod {n}}$.

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}{\bmod {1}}0$. 7 e 10 sono coprimi, e $\phi (10)=4$. Dal teorema di Eulero segue che $7^{4}\equiv 1{\bmod {1}}0$, 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 9{\bmod {1}}0$.

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

Bibliografia

• Harold Davenport, Aritmetica superiore, Bologna, Zanichelli, 1994, ISBN 88-08-09154-6.

Voci correlate

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

Collegamenti esterni

• (EN) Eric W. Weisstein, Teorema di Eulero, su MathWorld, Wolfram Research.