Apri il menu principale

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.

DimostrazioneModifica

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  .

GeneralizzazioniModifica

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 utilizzoModifica

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  .

BibliografiaModifica

Voci correlateModifica

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