Teorema di Eulero (aritmetica modulare)

teorema matematica

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

Voci correlate modifica

Collegamenti esterni modifica

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