Cosa devi sapere sui numeri primi

Il piccolo teorema di Fermat

Pierre de Fermat un magistrato francese vissuto tra il 1601 e il 1665 aveva una forte passione per la matematica e scoprí importanti proprietà sulla teoria dei numeri senza però darne una effettiva dimostrazione e quindi rimasero per molti anni sottoforma di congettura. Nel 1640 Fermat comunicò a Frenicle de Bessy la congettura:

se p è un numero primo ed a un qualunque intero non divisibile per p allora il resto della divisione a^p-1:p è uguale a 1.

Espressa in formula:

a^p-1 ≡ 1 (mod p)

Questa proprietà fu dimostrata quasi cento anni più tardi nel 1736 da Eulero ed è conosciuta col nome il piccolo teorema di Fermat. Ad esempio, ponendo a = 2 e p = 7 si ha:

2^7-1 ≡ 1 (mod 7)

Controesempio consideriamo un numero naturale non primo n=9 e una base a = 2 coprima con n e applichiamo il piccolo teorema:

2^9-1 ≡ 4 (mod 9)

e come si vede il teorema non è soddisfatto. Il piccolo teorema di Fermat viene utilizzato come test di non primalità di un numero naturale. Infatti, se n è un numero naturale ed esiste un intero a coprimo con n che non soddisfa la condizione

a^n-1 ≡ 1 (mod n)

allora n è composto. Purtroppo il piccolo teorema non è invertibile infatti, se n è un intero maggiore di 1 tale che

a^n-1 ≡ 1 (mod n)

con a e n coprimi allora n non è necessariamente primo. Infatti, se consideriamo n=341 e a=2, e applicando il piccolo teorema si ha:

2^341-1 ≡ 1 (mod 341)

Ma 341 non è un numero primo infatti, 341=11⋅31. Esistono quindi dei numeri detti pseudoprimi che pur non essendo primi soddisfano l'enunciato del teorema. Nel nostro esempio 341 è un pseudoprimo rispetto alla base 2 ma non è un pseudoprimo se la base è 3:

3^341-1 ≡ 56 (mod 341)

Esistono dei pseudoprimi detti numeri di Carmichael tali che

a^n-1 ≡ 1 (mod n)

per ogni intero a coprimo con n. Il più piccolo numero di Carmichael è 561 ed è stato dimostrato che questi numeri sono infiniti.

Nel 1760 Eulero formulò in una forma piò generale il piccolo teorema di Fermat:

per ogni modulo n ed ogni intero a coprimo rispetto ad a si ha

dove φ(n) è la funzione di Eulero. E' una generalizzazione perchè se n è un numero primo allora φ(n)=n-1.