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 è 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
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
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
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 .
Bibliografia modifica
- Harold Davenport, Aritmetica superiore, Bologna, Zanichelli, 1994, ISBN 88-08-09154-6.
Voci correlate modifica
Collegamenti esterni modifica
- (EN) Eric W. Weisstein, Teorema di Eulero, su MathWorld, Wolfram Research.