Teorema di non-universalità degli pseudoprimi di Eulero

Per ogni numero composto dispari $ n $, esiste almeno un numero intero $ b < n $, coprimo con $ n $, per cui $ n $ non è pseudoprimo di Eulero.

Questa proprietà dimostra che non tutti i numeri dispari composti si comportano come pseudoprimi di Eulero per tutte le basi coprime.

Per ogni numero $ n $ composto, c'è sempre almeno una base $ b $ che mostra che $ n $ non è pseudoprimo di Eulero.

\[ b^{(n-1)/2} \not\equiv \left( \frac{b}{n} \right) \pmod{n} \]

In altre parole, non esistono numeri di Carmichael per il test di Eulero, cioè non esiste un numero composto che sia pseudoprimo di Eulero in tutte le basi coprime.

Cosa sono gli pseudoprimi di Eulero? Un numero composto e dispari $ n $ è detto pseudoprimo di Eulero se per tutte le basi, ossia per tutti i numeri coprimi con $ n $ nell'intervallo $ 1<b<n $, soddisfa il test di Eulero. \[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \] Dove $ \left( \frac{b}{n} \right) $ è il simbolo di Jacobi che può assumere solo i valori +1 e -1. \[ b^{(n-1)/2} \equiv \pm 1 \pmod{n} \]

Un esempio pratico
La dimostrazione

Un esempio pratico

Considero il numero $ n = 21 $, che è un numero dispari e non primo.

\[ 21 = 3 \times 7 \]

Ora, verifico se $ 21 $ è pseudoprimo di Eulero per diverse basi ossia per tutti i numeri interi coprimi con $ n=21 $ nell'intervallo $ 1<b<21 $.

Devo scegliere un numero coprimo con 21, quindi che non sia divisibile né per 3 né per 7.

I numeri coprimi con $ n = 21 $ sono $ \{ 1, 2, 4, 5, 7, 8, 10, 11, 13, 15, 16, 17, 19, 20 \} $

Scelgo tra i coprimi di 21 la base $ b = 2 $.

A questo punto verifico se soddisfa il test di Eulero.

\[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \]

\[ 2^{(21-1)/2} \equiv \left( \frac{2}{21} \right) \pmod{21} \]

\[ 2^{10} \equiv \left( \frac{2}{21} \right) \pmod{21} \]

Sapendo che $ 2^{10} = 1024 $

\[ 1024 \equiv \left( \frac{2}{21} \right) \pmod{21} \]

Il numero 1024 nel modulo 21 è 16.

\[ 16 \equiv \left( \frac{2}{21} \right) \pmod{21} \]

Già da questo risultato posso affermare che $ n = 21 $ non è uno pseudoprimo di Eulero in base $ b = 2 $, poiché il lato sinistro dell'equazione è 16, un valore diverso da $ \pm 1 $, gli unici possibili risultati del simbolo di Jacobi nel lato destro dell'equazione.

Nota. Per completezza calcolo anche il simbolo di Jacobi $ \left( \frac{2}{21} \right) $ nel lato destro dell'equazione. Il simbolo di Jacobi si calcola così, per prima cosa lo scompongo in fattori primi. \[ \left( \frac{2}{21} \right) = \left( \frac{2}{3} \right) \times \left( \frac{2}{7} \right) \] In questo modo ottengo il prodotto di due simboli di Legendre e posso calcolarli separatamente. Sapendo che$ \left( \frac{2}{3} \right) = -1 $ perché 2 non è un quadrato modulo 3 e $ \left( \frac{2}{7} \right) = 1 $ perché 2 è un quadrato modulo 7. \[ \left( \frac{2}{21} \right) = \left( \frac{2}{3} \right) \times \left( \frac{2}{7} \right) = (-1) \times (1) = -1 \] Quindi, il simbolo di Jacobi è -1 e il test di Eulero non è soddisfatto perché 16 non è uguale a -1 nel modulo 21. \[ 16 \equiv \left( \frac{2}{21} \right) \pmod{21} \] \[ 16 \not\equiv -1 \pmod{21} \] Quindi $ 21 $ non è pseudoprimo di Eulero in base $ 2 $.

Questo mostra che ogni numero dispari composto fallisce il test di Eulero per almeno una base $ b $, proprio come affermato nella proposizione iniziale.

La dimostrazione

Provo una dimostrazione per assurdo, considerando vera l'ipotesi contraria: il numero composto dispari $ n $ è pseudoprimo di Eulero in tutte le basi $ b < n $, coprime con $ n $.

Se così fosse, allora il numero dei falsi positivi (basi bugiarde) sarebbe esattamente uguale al numero delle basi coprime del numero $\phi(n)$.

Dove $ \phi(n) $ è la funzione di Eulero del numero $ n $.

Tuttavia, so già che le basi in cui $ n $ è uno pseudoprimo di Eulero sono "al massimo" la metà di tutte le sue basi coprime, quindi sono al più $ \frac{\phi(n)}{2} $.

Quindi, si verifica una contraddizione perché è impossibile che $ n $ sia uno pseudoprimo di Eulero con tutte le basi coprime.

\[ \frac{\phi(n)}{2} \lt \phi(n) \]

Pertanto, l'ipotesi assurda che un numero composto dispari $ n $ sia pseudoprimo di Eulero su tutte le basi coprime è falsa.

Di consequenza, è vero il contrario, ossia esiste almeno una base $ b $ tale che $ n $ non risulta pseudoprimo di Eulero in base $ b $.

E così via.