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 ${\displaystyle n}$ è un intero positivo ed ${\displaystyle a}$ è coprimo rispetto ad ${\displaystyle n}$, allora:

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

dove ${\displaystyle \phi (n)}$ indica la funzione phi di Eulero e ${\displaystyle \equiv }$ la relazione di congruenza modulo ${\displaystyle 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 ${\displaystyle n}$) degli interi positivi minori o uguali ad ${\displaystyle n}$ e coprimi con ${\displaystyle n}$:

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

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

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

Ogni ${\displaystyle am_{i}}$ è ancora coprimo con ${\displaystyle n}$ perché è prodotto di due elementi coprimi con ${\displaystyle n}$: infatti ogni numero primo ${\displaystyle p}$ che divide ${\displaystyle am_{i}}$ divide o ${\displaystyle a}$ o ${\displaystyle m_{i}}$, e quindi se dividesse anche ${\displaystyle n}$ almeno uno tra ${\displaystyle a}$ ed ${\displaystyle m_{i}}$ non sarebbe coprimo con ${\displaystyle n}$.

Se ora ${\displaystyle i\neq j}$, allora ${\displaystyle am_{i}\not \equiv am_{j}{\bmod {n}}}$, perché altrimenti, moltiplicando per l'inverso ${\displaystyle b}$ di ${\displaystyle a}$ modulo ${\displaystyle n}$ (che esiste perché ${\displaystyle a}$ ed ${\displaystyle n}$ sono coprimi), si avrebbe ${\displaystyle bam_{i}\equiv bam_{j}{\bmod {n}}}$ e quindi ${\displaystyle m_{i}\equiv m_{j}{\bmod {n}}}$. Questi due fatti implicano che ${\displaystyle S_{2}}$ è un sottoinsieme di ${\displaystyle S_{1}}$ e ha la stessa cardinalità di ${\displaystyle S_{1}}$: di conseguenza, ${\displaystyle S_{1}}$ ed ${\displaystyle S_{2}}$ coincidono.

Pertanto il prodotto, di tutti gli elementi di ${\displaystyle S_{1}}$ è congruente al prodotto di tutti gli elementi di ${\displaystyle S_{2}}$:

${\displaystyle 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 ${\displaystyle m_{i}}$ è primo con ${\displaystyle n}$, possiamo moltiplicare ambo i membri per l'inversa di ${\displaystyle \prod _{i=1}^{\phi (n)}m_{i}}$ modulo ${\displaystyle n}$, ottenendo

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

Una dimostrazione meno diretta può essere ottenuta attraverso la teoria dei gruppi. L'insieme ${\displaystyle S_{1}}$ delle classi di resto modulo ${\displaystyle n}$, infatti, è un gruppo abeliano sotto l'operazione di moltiplicazione, ed ha ordine ${\displaystyle \phi (n)}$. Un qualsiasi elemento ${\displaystyle a\in S_{1}}$ genera un sottogruppo il cui ordine ${\displaystyle m}$, per il teorema di Lagrange, divide ${\displaystyle \phi (n)}$. Per definizione, ${\displaystyle a^{m}\equiv 1{\bmod {n}}}$, e, se ${\displaystyle \phi (n)=mr}$, allora quindi ${\displaystyle 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 ${\displaystyle a\in G}$ e l'ordine di ${\displaystyle G}$ è ${\displaystyle n}$, allora ${\displaystyle a^{n}=e}$ (dove ${\displaystyle 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 ${\displaystyle 7^{222}}$, vale a dire di ${\displaystyle 7^{222}{\bmod {1}}0}$. 7 e 10 sono coprimi, e ${\displaystyle \phi (10)=4}$. Dal teorema di Eulero segue che ${\displaystyle 7^{4}\equiv 1{\bmod {1}}0}$, e quindi ${\displaystyle 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 ${\displaystyle a}$ modulo ${\displaystyle n}$, ${\displaystyle a^{x}\equiv a^{y}{\bmod {n}}}$, dove ${\displaystyle 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.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
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

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