Numeri pseudoprimi
Un numero \( n \) composto (cioè non primo) si dice pseudoprimo in base \( a \) se soddisfa la relazione: $$ a^{n-1} \equiv 1 \pmod{n} $$ Dove \( a \) è un intero relativamente primo con \( n \), ossia \( \text{MCD}(a, n) = 1 \).
In altre parole, sono numeri pseudoprimi quei numeri che "sembrano" primi secondo il teorema di Fermat ... ma non lo sono.
Per questa ragione sono anche noti come pseudoprimi di Fermat.
Secondo il piccolo teorema di Fermat un numero è probabilmente primo se
$$ a^n \equiv a \pmod n $$
Tuttavia, se la base \( a \) è un numero relativamente primo con \( n \), ovvero se \( a \) e \( n \) non hanno divisori comuni diversi da 1, il numero $ n $ è composto anziché primo.
In questo caso, posso dividere entrambi i membri dell'equazione per $ a $
$$ \frac{a^n}{a} = a^{n-1} $$
$$ \frac{a}{a} = 1 $$
Quindi, l'equivalenza diventa:
$$ a^{n-1} \equiv 1 \pmod n $$
La relazione \( a^{n-1} \equiv 1 \pmod{n} \) è una proprietà che i numeri primi soddisfano per tutte le basi \( a \).
Un numero pseudoprimo, invece, è composto e soddisfa questa proprietà solo per alcune basi \( a \).
Nota. Un numero pseudoprimo può essere tale solo rispetto a certe basi. Ad esempio, \( n = 341 \) è un numero composto \( 341 = 11 \cdot 31 \) ed è un numero pseudoprimo in base 2 ma non in base 3.
In generale, i numeri pseudoprimi sono numeri dispari. Tuttavia esistono anche pseudoprimi pari (es. 4) ma sono rari.
Un esempio pratico
Considero il numero composto
$$ n = 91 $$
Si tratta di un numero composto da due numeri coprimi $ n = 91 = 7 \cdot 13 $. Quindi, non è primo.
Tuttavia, il numero $ n = 91 $ soddisfa il teorema di Fermat.
$$ a^{n-1} \equiv 1 \pmod{n} $$
$$ a^{91-1} \equiv 1 \pmod{91} $$
$$ a^{90} \equiv 1 \pmod{91} $$
Considero la base $ a=3 $
$$ 3^{90} \equiv 1 \pmod{91} $$
A questo punto calcolo la congruenza per verificare l'equivalenza
$$ 3^{90} \mod 91 $$
Per risolverla uso l'esponenziazione modulare
$$ 3^1 \mod 91 = 3 $$
$$ 3^2 \mod 91 = 9 $$
$$ 3^4 \mod 91 = 81 $$
$$ 3^8 \mod 91 = 3^4 \cdot 3^4 \mod 91 = 81 \cdot 81 \mod 91 = 9 $$
$$ 3^{16} \mod 91 = 3^8 \cdot 3^8 \mod 91 = 9 \cdot 9 \mod 91 = 81 $$
$$ 3^{32} \mod 91 = 3^{16} \cdot 3^{16} \mod 91 = 81 \cdot 81 \mod 91 = 9 $$
$$ 3^{64} \mod 91 = 3^{32} \cdot 3^{32} \mod 91 = 9 \cdot 9 \mod 91 = 81 $$
A questo punto sapendo che $ 3^{90} = 3^{64} \cdot 3^{16} \cdot 3^{8} \cdot 3^2 $
$$ 3^{90} \mod 91 = 3^{64} \cdot 3^{16} \cdot 3^{8} \cdot 3^2 \mod 91 $$
$$ 3^{90} \mod 91 = 81 \cdot 81 \cdot 9 \cdot 9 \mod 91 $$
Poiché $ 81 \cdot 9 \mod 91 = 1 $
$$ 3^{90} \mod 91 = ( 81 \cdot 9 ) \cdot ( 81 \cdot 9 ) \mod 91 $$
$$ 3^{90} \mod 91 = 1 \cdot 1 \mod 91 $$
$$ 3^{90} \mod 91 = 1 \mod 91 = 1 $$
Quindi, l'equivalenza è confermata
$$ 3^{90} \equiv 1 \pmod{91} $$
Il numero composto $ n=91 $ è un numero pseudoprimo per la base $ a=3 $.
Nota. Lo stesso numero $ n=91 $ potrebbe non esere pseudoprimo per altre basi. Ad esempio, $ n=91 $ non è pseudoprimo per la base $ a = 2 $ $$ 2^{90} \not \equiv 1 \pmod{91} $$
Note aggiuntive
Alcune note e osservazioni a margine sui numeri pseudoprimi
- Proprietà moltiplicativa dei numeri pseudoprimi
Se \( n \) è un numero composto e dispari, pseudoprimo in due basi \( b_1 \) e \( b_2 \) allora lo è anche nel prodotto delle basi \( b_1 b_2 \) e \( b_1 b_2^{-1} \) dove \( b_2^{-1} \) è l'inverso moltiplicativo di \( b_2 \) modulo \( n \).Nota. Questa proprietà dimostra che gli pseudoprimi godono di una struttura moltiplicativa che permette di generare nuovi pseudoprimi a partire da quelli noti.
- Proprietà di non-pseudoprimalità dei numeri composti
Dato un numero composto e dispari \( n > 1 \) e un intero \( a \) tale che \( 1 < a < n \) e \( \operatorname{MCD}(n, a) = 1 \) (ossia \( a \) è coprimo con \( n \)), se \( n \) non è pseudoprimo in base \( a \), allora non sarà pseudoprimo in almeno metà degli interi \( b \) tali che \( 1 < b < n \) e \( \operatorname{MCD}(n, b) = 1 \) (ossia \( b \) è coprimo con \( n \)).Nota. Questa proprietà riflette il fatto che un numero composto \( n \) che fallisce la condizione di pseudoprimalità in una base \( a \) coprima con \( n \) tende a fallire anche in almeno metà delle altre basi coprime con \( n \).
E così via.
