Test di Fermat
![Niente fonti!](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Question_book-4.svg/45px-Question_book-4.svg.png)
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 , tale che non valga , 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 passa il test per ogni base: ad esempio, preso p=7
- = (per il teorema di Eulero) ≡ 2 (mod 7),
oppure, equivalentemente, = (per Eulero) ≡ 1 (mod 7)-
- = (per Eulero) ≡ 3 (mod 7),
- = (per Eulero) ≡ 4 (mod 7),
- = (per Eulero) ≡ 5 (mod 7),
- = (per Eulero) ≡ 6 (mod 7).
Esempio 2
Se non è un numero primo, allora esisteranno molte basi (almeno metà) in cui il test dà esito positivo: diciamo che è uno pseudoprimo in base . Ad esempio, per n=91 abbiamo che 91=13*7 (cioè non è primo). Con a=3, però, vale che:
- = ≡ 1 (per Eulero) (mod 7)
- = ≡ (per Eulero)≡ 27*27 ≡ 1*1 =1 (mod 13)
Quindi, ≡ 1 (mod 91). Questo non vale, però, con a=2. Infatti, vediamo che:
- = ≡ (per Eulero)≡ ≡ 16*4 ≡ 3*4 = -1 (mod 13).
Voci correlate
- Piccolo teorema di Fermat
- Numero primo
- Pseudoprimo
- Test di Wilson
- Test di Lucas-Lehmer
- Test di Miller-Rabin
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)