Home | Perchè la crittografia | Crittografia a chiave segreta | Crittografia a chiave pubblica | Numeri primi | Aritmetica modulare

Per ogni n ≥ 1 il numero di interi positivi minori di n e coprimi con n è indicato con φ (n) dove φ è la funzione di Eulero o funzione Toziente.

Esempi:

1)   φ (6)=2 :gli interi coprimi con 6  sono 1 e 5.

2)  φ (7)=6:gli interi coprimi con 7  sono 1 ,2,3,4,5 ,6.

Osservazione:

- i numeri minori di p e coprimi con p sono tutti quelli compresi tra 1 e p-1 e quindi φ(p)=p-1.

Teorema di Eulero-Fermat

Il Teorema di Eulero-Fermat stabilisce che se n è un intero positivo ed a è coprimo rispetto a n allora:

Questo teorema è una generalizzazione del Piccolo Teorema di Fermat.

Corollario

Per ogni n ≥ 2 e per ogni a  Î Zn invertibile, cioè MCD(a,n)=1, l'inverso di a è .

Osservazione:

1. il calcolo di φ(n) per numeri grandi non è realizzabile in tempi ragionevoli.
2. l'applicazione dell'inverso dell'algoritmo di Euclide consente di effettuare il calcolo dell'inverso di a con strumenti del tutto differenti e in tempi rapidi.

Applicazioni con Excel

Applicazioni con Derive

Home | Teorema di Eulero | Algoritmo di Euclide | Piccolo teorema di Fermat | Numeri Casuali