Teorema di Eulero (aritmetica modulare)

Da Wikipedia, l'enciclopedia libera.

Nella 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

La dimostrazione "aritmetica" del teorema di Eulero può essere applicata, più in generale, a tutti i gruppo abeliano 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[modifica | modifica sorgente]

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 10. 7 e 10 sono coprimi, e \phi(10)=4. Dal teorema di Eulero segue che 7^4\equiv 1\bmod 10, e quindi 7^{222}\equiv 7^{4\cdot 55+2}\equiv (7^4)^{55}\cdot7^2\equiv 1^{55}\cdot 7^2\equiv 49\equiv 9\bmod 10.

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[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica