Simbolo di Jacobi

Sia \(n\) un intero positivo dispari e composto, con la sua fattorizzazione in fattori primi \[n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\] dove \(p_1, p_2, \ldots, p_k\) sono numeri primi distinti e \(e_1, e_2, \ldots, e_k\) sono i relativi esponenti, il simbolo di Jacobi \(\left(\frac{a}{n}\right)\) è definito come: \[ \left(\frac{a}{n}\right) = \prod_{i=1}^k \left(\frac{a}{p_i}\right)^{e_i}\] dove \(\left(\frac{a}{p_i}\right)\) è il simbolo di Legendre di ogni fattore primo \(p_i\) di \(n\).

Si tratta di una generalizzazione del simbolo di Legendre.

Mentre il simbolo di Legendre si applica solo quando il modulo \(n\) è un numero primo, il simbolo di Jacobi è definito anche per numeri composti \(n\).

A cosa serve?

Il simbolo di Jacobi è utilizzato per capire se un numero intero \(a\) è un residuo quadratico modulo n, quando \( n \) è un numero composto \(n\).

Nota.  Il simbolo di Jacobi è utilizzato nei test di primalità e nella crittografia, come nel test di Solovay-Strassen per verificare se un numero è probabilmente primo. E' utilizzato anche per verificare i numeri pseudoprimi di Eulero.

Va detto che il simbolo di Jacobi \(\left(\frac{a}{n}\right)\) non garantisce che \( a \) sia un residuo quadratico modulo \( n \).

• Se \( \left(\frac{a}{n}\right) = -1 \), allora sicuramente \( a \) non è un residuo quadratico modulo \( n \).
• Se \( \left(\frac{a}{n}\right) = 1 \), non posso concludere nulla: \( a \) può essere un residuo quadratico modulo \( n \), ma potrebbe anche non esserlo.
  

  Nota. Per saperlo devo verificare la congruenza \( x^2 \equiv a \pmod{n} \) su tutti i quadrati da 0 a n-1.  In alternativa, un metodo più rapido per verificare la congruenza, senza dover elencare i quadrati, è analizzare i risultati dei simboli di Legendre dei singoli fattori. Se almeno uno restituisce -1, posso dedurre che il numero intero non è un residuo quadratico.

Viceversa, il simbolo di Legendre fornisce una risposta certa su \( a \) ma si applica solo quando \( n \) è primo.

Un esempio pratico

Considero \(\left(\frac{2}{15}\right)\), con \(n = 15 = 3 \cdot 5\).

Per ciascun fattore primo calcolo il simbolo di Legendre e li moltiplico tra loro.

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

Ora analizzo ogni singolo simbolo di Legendre e lo sostituisco con 1, -1 oppure 0 a seconda se il numeratore è un residuo quadratico del denominatore.

1] Primo fattore

Nel simbolo \(\left(\frac{2}{3}\right)\) il numero \(2\) non è un residuo quadratico modulo \(3\) perché non esiste \( x \) tale che \(x^2 \equiv 2 \pmod{3}\). 

I residui quadratici modulo 3 sono i quadrati di \( x \in \{0,1,2\} \) calcolati modulo 3:

• \(0^2 = 0 \equiv 0 \pmod{3}\)
• \(1^2 = 1 \equiv 1 \pmod{3}\)
• \(2^2 = 4 \equiv 1 \pmod{3}\)

Poiché 2 non è nella lista, significa che 2 non è un residuo quadratico modulo 3.

Quindi, \(\left(\frac{2}{3}\right) = -1\).

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

Nota. Già da questo risultato posso dedurre che 2 non è un residuo quadratico di 15, indipendentemente dal risultato finale del simbolo di Jacobi, perché se 2 non è residuo quadratico per il modulo di uno dei fattori primi (modulo 3) allora non può esserlo nemmeno per il modulo 15. In ogni caso, per completezza continuo l'esercizio fino in fondo.

2] Secondo fattore

Nel simbolo \(\left(\frac{2}{5}\right)\), il numero \( 2 \) non è un residuo quadratico modulo \(5 \) perché non esiste \( x \) tale che \(x^2 \equiv 2 \pmod{5}\). 

I residui quadratici modulo 5 sono i quadrati di \( x \in \{0,1,2,3,4\} \) calcolati modulo 5:

• \(0^2 = 0 \equiv 0 \pmod{5}\)
• \(1^2 = 1 \equiv 1 \pmod{5}\)
• \(2^2 = 4 \equiv 4 \pmod{5}\)
• \(3^2 = 9 \equiv 4 \pmod{5}\)
• \(4^2 = 16 \equiv 1 \pmod{5}\)

Dato che 2 non compare nell'elenco, posso concludere che non è un residuo quadratico modulo 5.

Quindi, \(\left(\frac{2}{5}\right) = -1\).

Sostituisco i valori che ho trovato nel simbolo di Jacobi.

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

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

\[ \left(\frac{2}{15}\right) =  1 \]

Questo vuol dire che posso sostituire il simbolo di Jacobi \(\left(\frac{2}{15}\right)\) con \( 1 \).

Come devo interpretare questo risultato?

Il risultato \( 1 \) non mi permette di affermare o meno che \( 2 \) sia un residuo quadratico di 15.

Tuttavia, analizzando i simboli di Legendre dei singoli posso giungere comunque al risultato.

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

Poiché almeno uno dei due ha restituito $ -1 $, ad esempio $ \left(\frac{2}{3}\right) = -1 $, deduco che 2 non è residuo quadratico di 15.

Spiegazione. Se 2 non è un residuo quadratico nel modulo di almeno un fattore primo di 15, allora non può esserlo neanche in modulo 15, indipendentemente dal valore finale del simbolo di Jacobi.

Verifica

Per verificare il risultato calcolo tutti i quadrati da 0 a 14 modulo 15 e controllo se tra questi c'è anche $ a=2 $.

• \(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}\)

Nessuno di questi valori quadrati è congruo a $ 2 \pmod{15} $, quindi l'equazione $ x^2 \equiv 2 \pmod{15} $ non ha soluzioni.

La verifica ha confermato che 2 non è un residuo quadratico modulo 15.

Caso generale e proprietà fondamentali

Il simbolo di Jacobi \( \left( \frac{a}{n} \right) \)è definito solo quando il denominatore \( n \) è dispari positivo. Tuttavia, il numeratore \( a \) può essere qualsiasi intero.

Possono esserci due situazioni:

• Se \( a \) è pari, posso usare una regola speciale per \( \left( \frac{2}{n} \right) \) 
• Se \( a \) è dispari, posso applicare direttamente la reciprocità quadratica

Nel caso particolare in cui $ a=2 $ si usa la seguente formula \[ \left( \frac{2}{n} \right) = (-1)^{\frac{n^2 - 1}{8}} \]

1] Caso in cui \( a \) è pari

Se \( a \) è pari posso scomporlo come \( a = 2^k \cdot m \) con \( m \) dispari.

\[ \left( \frac{a}{n} \right) = \left( \frac{2^k \cdot m}{n} \right) = \left( \frac{2^k}{n} \right) \cdot \left( \frac{m}{n} \right) \]

Poi calcolo il simbolo di Jacobi con $ 2^k $ tramite la regola applicabile solo quando $ a=2 $, eventualmente ripetendo il processo più volte se \( k > 1 \).

\[ \left( \frac{2}{n} \right) = (-1)^{\frac{n^2 - 1}{8}} \]

L'altro simbolo di Jacobi è tra due numeri dispari e posso risolverlo normalmente, ad esempio usando la legge di reciprocità.

Esempio

Devo calcolare

\[ \left( \frac{22}{91} \right) \]

Poiché \( a \) è pari, posso riscrivere il simbolo di Jacobi in questa forma equivalente.

\[ \left( \frac{22}{91} \right)  = \left( \frac{2 \cdot 11}{91} \right) = \left( \frac{2}{91} \right) \cdot \left( \frac{11}{91} \right) \]

Questo mi permette di suddividere i calcoli. Per prima cosa, calcolo il simbolo \( \frac{2}{91} \)  con la formula speciale valida quando $ a=2 $

\[ \left( \frac{2}{91} \right) = (-1)^{\frac{91^2 - 1}{8}}  = (-1)^{\frac{8280}{8}} = (-1)^{1035} = -1 \]

Sostituisco $  \left( \frac{2}{91} \right)=-1 $

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

Per calcolare il simbolo $  \left( \frac{11}{91} \right) $ posso usare la formula della reciprocità perché $ a=11 $ è dispari.

\[  \left( \frac{11}{91} \right) = (-1)^{\frac{(11-1)(91-1)}{4}} \left( \frac{91}{11} \right) \]

\[  \left( \frac{11}{91} \right) = (-1)^{\frac{(10)(90)}{4}} \left( \frac{91}{11} \right) \]

\[  \left( \frac{11}{91} \right) = (-1)^{\frac{900}{4}} \left( \frac{91}{11} \right) \]

\[  \left( \frac{11}{91} \right) = (-1)^{225} \left( \frac{91}{11} \right) \]

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

Sapendo che $ 91 \equiv 3 \pmod{11} $

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

Il simbolo $ \left( \frac{3}{11} \right) $ è composto da numeri primi, quindi posso risolverla con la formula di Eulero \( \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \)

$$ \left(\frac{3}{11}\right) \equiv 3^{\frac{11-1}{2}} \pmod{11}  $$

$$ \left(\frac{3}{11}\right) \equiv 3^5 \pmod{11}  $$

$$ \left(\frac{3}{11}\right) \equiv 1 \pmod{11}  $$

Sostituisco $  \left( \frac{3}{11} \right)=1 $ in $ \left( \frac{11}{91} \right) $

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

Ora posso sostituire il valore corretto di \( \left( \frac{11}{91} \right) = -1 \) nel calcolo iniziale:

\[ \left( \frac{22}{91} \right) = \left( \frac{2}{91} \right) \cdot \left( \frac{11}{91} \right) = (-1) \cdot (-1) = 1 \]

Quindi, il valore corretto è:

\[ \left( \frac{22}{91} \right) = 1 \]

2] Caso in cui \( a \) è dispari: reciprocità quadratica

Se \( a \) è dispari, posso usare la reciprocità quadratica:

\[ \left( \frac{a}{n} \right) = (-1)^{\frac{(a-1)(n-1)}{4}} \left( \frac{n}{a} \right) \]

Questa regola permette di scambiare il numeratore e il denominatore, semplificando il calcolo.

Esempio

Devo calcolare

\[ \left( \frac{3}{11} \right) \]

Applico la reciprocità quadratica:

\[ \left( \frac{3}{11} \right) = (-1)^{\frac{(3-1)(11-1)}{4}} \left( \frac{11}{3} \right) \]

\[ \left( \frac{3}{11} \right) = (-1)^{\frac{2 \cdot 10}{4}} \left( \frac{11}{3} \right) \]

\[ \left( \frac{3}{11} \right) = (-1)^{5} \left( \frac{11}{3} \right) \]

Poiché 5 è dispari, il segno cambia:

\[ \left( \frac{3}{11} \right) = - \left( \frac{11}{3} \right) \]

Sapendo che \( 11 \equiv 2 \mod 3 \)

\[ \left( \frac{3}{11} \right) = - \left( \frac{2}{3} \right) \]

Uso la regola per \( \left( \frac{2}{3} \right) \):

\[ \left( \frac{2}{3} \right) = (-1)^{\frac{3^2 - 1}{8}} = (-1)^1 = -1 \]

Quindi:

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

Il simbolo di Jacobi è 1.

Altre proprietà del simbolo di Jacobi

Il simbolo di Jacobi conserva molte proprietà del simbolo di Legendre, ma ha alcune differenze significative:

• Proprietà moltiplicativa
  Ecco le due regole principali per la moltiplicatività del simbolo di Jacobi:
  • Moltiplicatività rispetto al numeratore (vale sempre): \[ \left(\frac{a_1 \cdot a_2}{n}\right) = \left(\frac{a_1}{n}\right) \cdot \left(\frac{a_2}{n}\right) \] per qualsiasi \( a_1, a_2 \) e per un \( n \) dispari e positivo.
  • Moltiplicatività rispetto al denominatore (vale solo se \( n \) è scomposto in fattori primi): 
    Se \( n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \), allora: \[ \left(\frac{a}{n}\right) = \left(\frac{a}{p_1^{e_1}}\right) \cdot \left(\frac{a}{p_2^{e_2}}\right) \cdots \left(\frac{a}{p_k^{e_k}}\right) \] e inoltre  \( \left(\frac{a}{p^e}\right) = \left(\frac{a}{p}\right)^e \) per ogni primo \( p \).
• Simmetria quadratica (legge di reciprocità)
  Se \(a\) e \(n\) sono dispari: \[ \left(\frac{a}{n}\right) = (-1)^{\frac{(a-1)(n-1)}{4}} \cdot \left(\frac{n}{a}\right) \]
• Valori notevoli del simbolo di Jacobi
  Il simbolo di Jacobi può assumere i valori \(-1\), \(0\) o \(1\): $$ \left(\frac{a}{n}\right) = 0 \ \ se \ \ \text{MCD}(a, n) \neq 1 $$ $$ \left( \frac{a}{2} \right) = \begin{cases} 0 \ \ \ \text{se a=pari} \\ \\ 1 \ \ \ \text{se a=dispari} \end{cases} $$ $$ \left( \frac{a}{1} \right) = 1  $$
• Non implica l'esistenza di una soluzione quadratica
  A differenza del simbolo di Legendre, \(\left(\frac{a}{n}\right) = 1\) non garantisce che esista un numero \(x\) tale che \(x^2 \equiv a \pmod{n}\), se \(n\) è composto.

E così via.