Proprietà di non-pseudoprimalità di Eulero dei numeri composti

Sia \( n \) un numero intero composto, positivo e dispari, il numero delle basi \( b < n \), coprime con \( n \), per cui \( n \) risulta uno pseudoprimo di Eulero, è al massimo la metà di tutte le basi \( b \) tali che \( \text{MCD}(b, n) = 1 \).

In altre parole, un numero composto \( n \) può comportarsi da "falso primo" (pseudoprimo di Eulero) solo per una minoranza delle basi \( b \) ossia dei numeri coprimi $ MCD(b,n)=1 $ con \( n \) nell'intervallo \( 1 < b < n \). 

Questo limita i casi in cui \( n \) può ingannare il test di Eulero.

Questo significa che gli pseudoprimi di Eulero hanno meno falsi positivi degli pseudoprimi di Fermat e sono più affidabili nei test di primalità.

Nota. Gli pseudoprimi di Eulero sono più affidabili degli pseudoprimi di Fermat per identificare i numeri primi, poiché il test elimina una maggiore quantità di numeri non primi che potrebbero sembrare primi. Negli pseudoprimi di Eulero "al massimo la metà" delle basi coprime è un falso positivo, mentre negli pseudoprimi di Fermat possono essere "almeno la metà", quindi molte di più. In casi particolari, come nei numeri di Carmichael, addirittura tutte le basi coprime di un numero composto sono falsi positivi.

Un esempio pratico

Considero il numero \( n = 15 \), che è dispari, positivo e non primo (composto). I fattori primi del numero sono \( 3 \) e \( 5 \).

$$ n = 15 = 3 \cdot 5 $$

Per prima cosa elenco i numero coprimi con \( n \), ossia quei numeri interi \( b \) tali che \( \text{MCD}(b, 15) = 1 \).

I numeri \( b \) minori di \( n = 15 \) sono:

$$ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 $$

Ora elimino quelli che non sono coprimi con \( n \) cioè quelli divisibili per i fattori primi di \( 15 \), ovvero \( 3 \) e \( 5 \):

Quelli divisibili per 3 sono \( 3, 6, 9, 12 \) mentre quelli divisibili per 5 sono \( 5, 10 \).

Quindi, i numeri coprimi \( b \) con \( 15 \) sono:

$$ 1, 2, 4, 7, 8, 11, 13, 14 $$

In totale ci sono \( \phi(15) = 8 \) numeri coprimi con \( 15 \), dove \( \phi \) è la funzione di Eulero.

Quali di questi numeri sono pseudoprimi di Eulero con 15?

A questo punto verifico per quali basi \( b \) il numero \( 15 \) è uno pseudoprimo di Eulero.

La condizione per essere pseudoprimo di Eulero in base \( b \) è:  $ b^{(n-1)/2} \equiv \pm 1 \pmod{n} $

base	Condizione di Eulero	Base in cui 15 è Pseudoprimo
\( b = 1 \)	\( 1^7 \equiv 1 \pmod{15} \)	✅ si (falso positivo)
\( b = 2 \)	\( 2^7 \equiv 8 \pmod{15} \)	❌ no
\( b = 4 \)	\( 4^7 \equiv 4 \pmod{15} \)	❌ no
\( b = 7 \)	\( 7^7 \equiv 7 \pmod{15} \)	❌ no
\( b = 8 \)	\( 8^7 \equiv 8 \pmod{15} \)	❌ no
\( b = 11 \)	\( 11^7 \equiv 11 \pmod{15} \)	❌ no
\( b = 13 \)	\( 13^7 \equiv 13 \pmod{15} \)	❌ no
\( b = 14 \)	\( 14^7 \equiv 14 \pmod{15} \)	❌ no

Tra gli 8 numeri \( b \) coprimi con \( 15 \), solo 1 (cioè \( b = 1 \)) soddisfa la condizione per cui \( 15 \) è uno pseudoprimo di Eulero.

In altre parole, ho trovato solo un falso positivo, un falso numero primo che inganna il test di primalità.

Questo è molto meno della metà degli 8 numeri considerati, quindi conferma la proposizione iniziale.

E così via.