aprimalita
aprimalita
aprimalità proprietà di un numero che consiste nel suo non essere primo. Un test di aprimalità è stato definito da P. de Fermat: dato un numero intero, il test permette (ma non sempre) di stabilire se esso non è primo. Il test si basa sul piccolo teorema di → Fermat, secondo il quale, se p è un numero primo e se a è un qualsiasi numero intero, allora vale la congruenza ap ≡ a (modp); equivalentemente, se un numero n soddisfa la condizione an ≢ a modn per qualche intero a, allora esso non è primo. Il test di Fermat consiste nel ripetere tale operazione al variare di a, finché non si determina (se esiste) un intero a che soddisfi la suddetta condizione. Se un tale numero esiste, allora n non è un numero primo; d’altra parte, se n è un numero primo, allora il procedimento non ha termine. Se il procedimento non ha termine, non necessariamente n è un numero primo. Un numero n che supera il test di Fermat con base a (vale a dire tale che an ≡ a (modn)) è detto uno pseudoprimo di Fermat in base a; un numero non primo che sia uno pseudoprimo di Fermat in qualsiasi base è detto un numero di Carmichael: è il caso, per esempio, di 561 e 41041. I numeri di Carmichael sono dunque i numeri non primi per i quali il test di Fermat non ha termine; essi sono infiniti e la loro esistenza impedisce che il test di Fermat venga usato per dimostrare la primalità di un numero.