Pseudoprimo di Eulero-Jacobi

In matematica, un numero n è chiamato pseudoprimo di Eulero-Jacobi in base a, con MCD(a,n)=1, se è dispari, composto e si ha che

$a^{\frac {n-1}{2}}\equiv \left({\frac {a}{n}}\right)\mod n$

dove $\equiv$ è l'operazione modulo e (a/n) è il simbolo di Jacobi.

Tali numeri sono chiamati pseudoprimi perché tutti i numeri primi p soddisfano questa proprietà per tutti gli a coprimi con p.

Poiché la condizione che definisce questi numeri può essere verificata abbastanza rapidamente, questi pseudoprimi possono essere usati per costruire dei test di primalità probabilistici abbastanza efficienti.

Ogni pseudoprimo di Eulero-Jacobi è anche uno pseudoprimo di Eulero e, quindi, uno pseudoprimo di Fermat. Tuttavia, a differenza di queste altre classi, non esiste nessun numero che sia uno pseudoprimo di Eulero-Jacobi in ogni base a coprima con n: Solovay e Strassen hanno dimostrato che, per ogni numero composto n, esistono almeno n/2 basi in cui n non è uno pseudoprimo di Eulero-Jacobi.