Test di Fermat

Il test di Fermat è un test di primalità basato sul piccolo teorema di Fermat. Esso è uno dei primi test di primalità trovati e, come gli altri test usati normalmente, si propone di verificare non se un numero intero positivo è primo, ma se un numero dato non è primo. Infatti, dal teorema sappiamo che

se

\exists ~a\in \mathbb {Z}

, tale che non valga

a^{n}\equiv a\mod n

, allora n non è primo.

Nulla si può dire, però, nel caso in cui tale proprietà sia verificata per qualche a, e perfino se è verificata da ogni a: n può comunque non essere primo. I numeri che, in base a, passano il test di Fermat sono detti pseudoprimi di Fermat, mentre quelli che lo passano per ogni a sono detti numeri di Carmichael: il più piccolo di questi è 561.

Esempi

Esempio 1

Un primo $p$ passa il test per ogni base: ad esempio, preso p=7

2^{7}

=

2^{1}

(per il teorema di Eulero) ≡ 2 (mod 7),

oppure, equivalentemente, $2^{6}$ = $2^{0}$ (per Eulero) ≡ 1 (mod 7)-

3^{7}

=

3^{1}

(per Eulero) ≡ 3 (mod 7),

4^{7}

=

4^{1}

(per Eulero) ≡ 4 (mod 7),

5^{7}

=

5^{1}

(per Eulero) ≡ 5 (mod 7),

6^{7}

=

6^{1}

(per Eulero) ≡ 6 (mod 7).

Esempio 2

Se $n$ non è un numero primo, allora esisteranno molte basi (almeno metà) in cui il test dà esito positivo: diciamo che $n$ è uno pseudoprimo in base $a$ . Ad esempio, per n=91 abbiamo che 91=13*7 (cioè $n$ non è primo). Con a=3, però, vale che: