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

Il piccolo teorema di Fermat afferma
 n è primo,se e solo se,  per ogni a Î Z_n non nullo e  coprimo rispetto a n , risulta

Corollario.
Se n è primo, allora l' inverso di a in Z_n è                                                                   .
Osservazioni:

• il teorema fornisce un criterio per verificare se un intero non è primo:

      n non è primo se :    e .

• se     e         non è detto che n sia primo;

     ad esempio se n =91  e   a=3 ,     allora risulta     ma 91 non è primo

91=7*13

 Osservazioni

• il teorema di Fermat risolve il problema del calcolo dell' inverso di a in Z _n  quando n è primo, rimane aperto il problema nel caso n non sia primo.
• per verificare la primalità di un intero occorrerà imporre delle condizioni più restrittive, come dimostrò Eulero più di un secolo dopo.

Applicazioni con Excel

Applicazioni con Derive

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