Vai al contenuto

Teorema di Eulero (aritmetica modulare)

Da Wikipedia, l'enciclopedia libera.

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

dove indica la funzione phi di Eulero e la relazione di congruenza modulo .

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

Dimostrazione

[modifica | modifica wikitesto]

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

Se moltiplichiamo ogni elemento di per otterremo un secondo insieme,

.

Ogni è ancora coprimo con perché è prodotto di due elementi coprimi con : infatti ogni numero primo che divide divide o o , e quindi se dividesse anche almeno uno tra ed non sarebbe coprimo con .

Se ora , allora , perché altrimenti, moltiplicando per l'inverso di modulo (che esiste perché ed sono coprimi), si avrebbe e quindi . Questi due fatti implicano che è un sottoinsieme di e ha la stessa cardinalità di : di conseguenza, ed coincidono.

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

.

Poiché ogni è primo con , possiamo moltiplicare ambo i membri per l'inversa di modulo , ottenendo

.

Una dimostrazione meno diretta può essere ottenuta attraverso la teoria dei gruppi. L'insieme delle classi di resto modulo , infatti, è un gruppo abeliano sotto l'operazione di moltiplicazione, ed ha ordine . Un qualsiasi elemento genera un sottogruppo il cui ordine , per il teorema di Lagrange, divide . Per definizione, , e, se , allora quindi .

Generalizzazioni

[modifica | modifica wikitesto]

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 e l'ordine di è , allora (dove è l'elemento neutro del gruppo).

Esempi di utilizzo

[modifica | modifica wikitesto]

Il teorema può essere usato per ridurre facilmente grandi potenze in modulo n. Ad esempio, prendiamo in considerazione la ricerca dell'ultima cifra di , vale a dire di . 7 e 10 sono coprimi, e . Dal teorema di Eulero segue che , e quindi .

In generale, nella riduzione di una potenza di modulo , , dove .

Voci correlate

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica