Test di Fermat

Niente fonti!
Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

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 ∃   a ∈ Z {\displaystyle \exists ~a\in \mathbb {Z} } , tale che non valga a n ≡ a mod n {\displaystyle 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 {\displaystyle p} passa il test per ogni base: ad esempio, preso p=7

2 7 {\displaystyle 2^{7}} = 2 1 {\displaystyle 2^{1}} (per il teorema di Eulero) ≡ 2 (mod 7),

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

3 7 {\displaystyle 3^{7}} = 3 1 {\displaystyle 3^{1}} (per Eulero) ≡ 3 (mod 7),
4 7 {\displaystyle 4^{7}} = 4 1 {\displaystyle 4^{1}} (per Eulero) ≡ 4 (mod 7),
5 7 {\displaystyle 5^{7}} = 5 1 {\displaystyle 5^{1}} (per Eulero) ≡ 5 (mod 7),
6 7 {\displaystyle 6^{7}} = 6 1 {\displaystyle 6^{1}} (per Eulero) ≡ 6 (mod 7).

Esempio 2

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

3 90 {\displaystyle 3^{90}} = ( 3 6 ) 15 {\displaystyle (3^{6})^{15}} ≡ 1 (per Eulero) (mod 7)
3 90 {\displaystyle 3^{90}} = 3 12 ∗ 7 + 6 {\displaystyle 3^{12*7+6}} ≡ 3 6 {\displaystyle 3^{6}} (per Eulero)≡ 27*27 ≡ 1*1 =1 (mod 13)

Quindi, 3 90 {\displaystyle 3^{90}} ≡ 1 (mod 91). Questo non vale, però, con a=2. Infatti, vediamo che:

2 90 {\displaystyle 2^{90}} = 2 12 ∗ 7 + 6 {\displaystyle 2^{12*7+6}} ≡ 2 6 {\displaystyle 2^{6}} (per Eulero)≡ 2 4 + 2 {\displaystyle 2^{4+2}} ≡ 16*4 ≡ 3*4 = -1 (mod 13).

Voci correlate

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica