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
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
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
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
- Harold Davenport, Aritmetica superiore, Bologna, Zanichelli, 1994, ISBN 88-08-09154-6.
Voci correlate
Collegamenti esterni
- (EN) Eric W. Weisstein, Teorema di Eulero, su MathWorld, Wolfram Research.
V · D · M | ||
---|---|---|
Numeri più usati | Naturali · Interi · Pari e dispari | |
Principi generali | Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza | |
Successioni di interi | Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse | |
Caratteristiche dei numeri primi | Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi | |
Funzioni aritmetiche | Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens | |
Aritmetica modulare | Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica | |
Congetture | Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann | |
Altro | Problema di Waring | |
Principali teorici | Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet | |
Discipline connesse | Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri |