Esistenza di un non-residuo quadratico negli pseudoprimi di Eulero

Dato un numero dispari $ n > 1 $ che non sia un quadrato perfetto, esiste sempre un intero positivo $ b < n $, primo con $ n $, tale che la base $ b $ è un non-residuo quadratico modulo $ n $, ovvero il simbolo di Legendre è $ \left( \frac{b}{n} \right) = -1 $.

Dove per quadrato perfetto intendo un numero che is ottiene elevando un intero al quadrato.

Questa proprietà garantisce che nei numeri dispari non quadrati perfetti esiste sempre almeno un numero che non è un residuo quadratico.

Nota. Ha diverse applicazioni nei test di primalità probabilistici, in particolare nei test basati sulla congruenza di Eulero. Ad esempio, migliora l'affidabilità dei test di primalità, perché permette di identificare numeri composti che ingannano altri test più deboli (come Fermat). Inoltre, impedisce la selezione dei numeri di Carmichael per il test di Eulero, rendendo il test più affidabile. Infine, è un fondamento teorico di molti test probabilistici avanzati, come Miller-Rabin e Solovay-Strassen.

Un esempio pratico
La dimostrazione

Un esempio pratico

Considero il numero $ n = 15 $, che è un numero dispari e non è un quadrato perfetto.

Voglio trovare un numero $ b < 15 $, coprimo con 15, tale che il simbolo di Legendre $ \left( \frac{b}{15} \right) = -1 $ ovvero non residuo quadratico nel modulo $ n $.

Scompongo $ n $ in fattori primi:

\[ n = 15 = 3^1 \cdot 5^1. \]

I fattori primi del numero $ n=15 $ sono $ p = 3 $ e $ m = 5 $.

Analizzo i residui quadratici nel modulo 3.

$ 0^2 = 0 \equiv 0 \pmod{3} $
$ 1^2 = 1 \equiv 1 \pmod{3} $
$ 2^2 = 4 \equiv 2 \pmod{3} $

Tra i residui quadratici nel modulo 3 c'è la base $ \{1\} $ mentre tra i non residui quadratici $ \{2\} $.

Scelgo il numero $ t = 2 $, che non è un quadrato modulo 3.

Nota. Un quadrato modulo $ n $ è un numero intero $ a $ tale che esiste un altro numero intero $ x $ che soddisfa la congruenza: \[ x^2 \equiv a \pmod{n} \] In altre parole, la base $ a $ è un residuo quadratico modulo $ n $ se esiste un numero $ x $ il cui quadrato è congruo a $ a $ modulo $ n $. Se invece non esiste tale $ x $, allora $ a $ è un non residuo quadratico modulo $ n $.

Ora costruisco un sistema per trovare un intero $ b $ tale che è un residuo quadrato nel modulo 5 e un non residuo quadratico nel modulo 3.

$$ \begin{cases} b \equiv 1 \pmod{5} \\ \\ b \equiv 2 \pmod{3} \end{cases} $$

La prima equazione cerca una base che sia un quadrato modulo 5.

La seconda equazione, invece, mi garantisce che $ b = 2 \mod 3 $ sia un non quadrato modulo 3, poiché già so che 2 è un residuo quadrato in questo modulo.

Risolvo il sistema e trovo il valore $ b=11 $ che soddisfa entrambe le equazioni modulari del sistema.

$$ \begin{cases} 11 \equiv 1 \pmod{5} \\ \\ 11 \equiv 2 \pmod{3} \end{cases} $$

A questo punto, prendo $ b = 11 $ e calcolo il simbolo di Legendre $ \left( \frac{b}{n} \right) $:

\[ \left( \frac{11}{15} \right) = \left( \frac{11}{3} \right) \cdot \left( \frac{11}{5} \right). \]

Poiché $ 11 \equiv 2 \pmod{3} $ e $ 2 $ non è un quadrato modulo 3, allora $\left( \frac{11}{3} \right) = -1 $

\[ \left( \frac{11}{15} \right) = \left( -1 \right) \cdot \left( \frac{11}{5} \right). \]

Poiché $ 11 \equiv 1 \pmod{5} $, e $ 1 $ è un quadrato modulo 5, ho $ \left( \frac{11}{5} \right) = 1 $

\[ \left( \frac{11}{15} \right) = (-1) \cdot 1 = -1 \]

Ho trovato che $ b = 11 $ soddisfa la condizione iniziale: è coprimo con $ 15 $, ed è un non residuo quadratico modulo $ 15 $.

Verifica. Per verificare il risultato calcolo tutti i residui quadratici del modulo $ n=15 $. I residui quadratici modulo $ 15 $ sono $ 0, 1, 4, 6, 9, 10 $. Tutti gli altri sono non residui quadratici modulo $ 15 $ e sono $ 2,3,5,7,8,11 $. Tra i non residui c'è anche 11.

$0^2 = 0 \equiv 0 \pmod{15}$
$1^2 = 1 \equiv 1 \pmod{15}$
$2^2 = 4 \equiv 4 \pmod{15}$
$3^2 = 9 \equiv 9 \pmod{15}$
$4^2 = 16 \equiv 1 \pmod{15}$
$5^2 = 25 \equiv 10 \pmod{15}$
$6^2 = 36 \equiv 6 \pmod{15}$
$7^2 = 49 \equiv 4 \pmod{15}$
$8^2 = 64 \equiv 4 \pmod{15}$
$9^2 = 81 \equiv 6 \pmod{15}$
$10^2 = 100 \equiv 10 \pmod{15}$
$11^2 = 121 \equiv 1 \pmod{15}$
$12^2 = 144 \equiv 9 \pmod{15}$
$13^2 = 169 \equiv 4 \pmod{15}$
$14^2 = 196 \equiv 1 \pmod{15}$

La dimostrazione

Per dimostrare questa proprietà considero due casi: nel primo $ n $ è primo, nel secondo $ n $ è composto.

1] Caso in cui n è primo

Se $ n $ è un numero primo, so già che esistono numeri che non sono quadrati modulo $ n $, cioè numeri $ b $ tali che $ \left( \frac{b}{n} \right) = -1 $.

Per un numero primo $ n $ la metà dei numeri di $ \mathbb{Z}_p^\times $ sono residui quadratici e l'altra metà sono non residui quadratici.

In altre parole, il numero totale di residui quadratici che è esattamente $ \frac{p-1}{2} $, e il numero totale di non residui quadratici è anch'esso $ \frac{p-1}{2} $.

Quindi, la presenza di un elemento non quadrato è garantita.

Per esempio, se $ n = 7 $, i residui quadratici modulo 7 sono {1, 2, 4}, mentre i non residui quadratici modulo 7 sono {3,5,6}. Un numero come $ b = 3 $ non è un quadrato modulo 7 perché non esiste nessun valore tale che $ x^2 \equiv 3 \pmod{7} $ $$ \begin{aligned} 0^2 &\equiv 0 \pmod{7} \\ 1^2 &\equiv 1 \pmod{7} \\ 2^2 &\equiv 4 \pmod{7} \\ 3^2 &\equiv 9 \equiv 2 \pmod{7} \\ 4^2 &\equiv 16 \equiv 2 \pmod{7} \\ 5^2 &\equiv 25 \equiv 4 \pmod{7} \\ 6^2 &\equiv 36 \equiv 1 \pmod{7} \end{aligned} $$

2] Caso in cui n è primo

Se $ n $ è composto, prendo un suo fattore primo $ p $ che compare con un esponente dispari nella fattorizzazione di $ n $.

Scrivo $ n = p^e m $ con $ e $ dispari.

Scelgo $ t $ come un numero che non è un residuo quadratico modulo $ p $.

Per il Teorema cinese dei resti, posso trovare un numero $ b $ che soddisfi due condizioni simultaneamente:

\[ \begin{cases} b \equiv t \pmod{p} \\ \\ b \equiv 1 \pmod{m} \end{cases} \]

Questo significa che $ b $ è costruito appositamente in modo che sia congruo a $ t $ modulo $ p $ quindi non è un quadrato modulo $ p $.

Inoltre è congruo anche a 1 modulo $ m $ ed è un quadrato modulo $ m $.

Calcolo il simbolo di Legendre

Dato che $ n = p^e m $, il simbolo di Legendre si calcola come segue:

\[ \left( \frac{b}{n} \right) = \left( \frac{b}{p} \right)^e \left( \frac{b}{m} \right) \]

Sapendo che $ b \equiv t \pmod{p} $ non è un quadrato, deduco che $ \left( \frac{b}{p} \right) = -1 $.

Inoltre, poiché $ b \equiv 1 \pmod{m} $, ho che $ \left( \frac{b}{m} \right) = 1 $.

\[ \left( \frac{b}{n} \right) = \left( -1 \right)^e \cdot 1 \]

Poiché $ e $ è dispari e la base è $ -1 $, sono sicuro che il risultato finale è sempre -1

\[ \left( \frac{b}{n} \right) = (-1)^e \cdot 1 = -1 \]

Questo dimostra che, in entrambi i casi, esiste almeno una base $ b $ che non è residuo quadratico modulo $ n $.

E così via.