I test di primalitÃ
Cosa sono i test di primalità
I test di primalità sono test che permettono di capire se un numero intero è un numero primo oppure no.
Eccone alcuni
Il piccolo teorema di Fermat
Secondo il piccolo teorema di Fermat se p è un numero primo è sempre soddisfatta la congruenza $$ k^p \equiv k \mod p $$ per qualsiasi numero intero k.
Esempio 1
Devo verificare se p=7 è un numero primo.
$$ k^7 \equiv k \mod 7 $$
Se p è un numero primo, allora qualsiasi numero intero k soddisfa la congruenza.
$$ 2^7 \equiv 2 \mod 7 \\ 128 \equiv 2 \mod 7 \\ 2 \equiv 2 \mod 7 $$
$$ 3^7 \equiv 3 \mod 7 \\ 2187 \equiv 3 \mod 7 \\ 3 \equiv 3 \mod 7 \\ \\ \vdots $$
Per qualsiasi intero k, la congruenza è soddisfatta. Pertanto p=7 è un numero primo.
Esempio 2
Ora verifico se p=9 è un numero primo
$$ k^9 \equiv k \mod 9 $$
Provo con k=2
$$ 2^9 \equiv 2 \mod 9 \\ 512 \equiv 2 \mod 9 \\ 8 \equiv 2 \mod 9 $$
In questo caso la congruenza non è soddisfatta per k=2. E' inutile procedere con altri tentativi.
Pertanto, l'intero p=9 non è un numero primo.
Teorema di Wilson
Un numero n è un numero primo se e solo se $$ (n-1)! \equiv -1 \mod n $$
Questo metodo ha però uno svantaggio, qualsiasi funzione fattoriale cresce più che esponenzialmente.
E' quindi difficoltoso da applicare per numeri molto grandi.
Esempio
Verifico se n=7 è un numero primo
$$ (n-1)! \equiv -1 \mod n $$
$$ (7-1)! \equiv -1 \mod 7 $$
$$ 6! \equiv -1 \mod 7 $$
$$ 6·5·4·3·2·1 \equiv -1 \mod 7 $$
$$ 720 \equiv -1 \mod 7 $$
$$ 6 \equiv -1 \mod 7 $$
Il numero 6 è congruente con -1 modulo 7.
Pertanto n=7 è un numero primo.
Nota. Dire $$ 6 \equiv -1 \mod 7 $$ equivale a $$ 6 + 1 \equiv 0 \mod 7 $$
E così via.
