title: Test di Fermat
text: # 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:
  
      $3^{90}$ = $(3^{6})^{15}$ ≡ 1 (per Eulero) (mod 7)
      $3^{90}$ = $3^{12*7+6}$ ≡ $3^{6}$ (per Eulero)≡ 27*27 ≡ 1*1 =1 (mod 13)
  
  Quindi, $3^{90}$ ≡ 1 (mod 91). Questo non vale, però, con a=2. Infatti, vediamo che:
  
      $2^{90}$ = $2^{12*7+6}$ ≡ $2^{6}$ (per Eulero)≡ $2^{4+2}$ ≡ 16*4 ≡ 3*4 = -1 (mod 13).
  