Residuo quadratico
Un numero intero \( a \) è un residuo quadratico modulo \( p \) se esiste un intero \( x \) tale che: \[x^2 \equiv a \pmod{p}\]Se non esiste tale \( x \), allora \( a \) non è un residuo quadratico modulo \( p \).
In altre parole, se il quadrato di un intero \( x \) equivale ad \( a \) nel modulo \( p \), l'intero \( a \) è un residuo quadratico in questo modulo. Viceversa, se non esiste, non lo è.
Pertanto, un residuo quadratico è un numero che ammette una radice quadrata nel modulo \( p \).
Nota. Per verificare se un numero \( a \) è un residuo quadratico modulo \( n \), indipendentemente dal fatto che \( n \) sia primo o composto, posso semplicemente calcolare tutti i quadrati modulo \( n \) e vedere se \( a \) compare nella lista.
Un esempio pratico
Calcolo i quadrati dei numeri modulo \( p = 7 \) per ogni \( x \) da 0 a 6:
- \( 0^2 = 0 \equiv 0 \pmod{7} \)
- \( 1^2 = 1 \equiv 1 \pmod{7} \)
- \( 2^2 = 4 \equiv 4 \pmod{7} \)
- \( 3^2 = 9 \equiv 2 \pmod{7} \)
- \( 4^2 = 16 \equiv 2 \pmod{7} \)
- \( 5^2 = 25 \equiv 4 \pmod{7} \)
- \( 6^2 = 36 \equiv 1 \pmod{7} \)
I residui quadratici modulo \( 7 \) sono: \{0, 1, 2, 4\)
I numeri 3, 5 e 6 non appaiono nella lista, quindi non sono residui quadratici modulo 7.
Come verificare se un numero è un residuo quadratico modulo p
Per verificare se \( a \) è un residuo quadratico modulo \( n \), seguo questi passi:
- Calcolo tutti i quadrati \( x^2 \mod n \) per \( x = 0, 1, 2, \dots, n-1 \).
- Osserva i risultati:
- Se \( a \) compare nella lista, allora \( a \) è un residuo quadratico modulo \( n \).
- Se \( a \) non compare, allora \( a \) non è un residuo quadratico modulo \( n \).
Questo metodo è pratico per \( n \) piccoli, mentre per \( n \) grandi è preferibile usare strumenti come il metodo di Legendre o il metodo di Jacobi.
Esempio
Devo verificare se \( 2 \) è un residuo quadratico modulo \( 15 \)
Calcolo i quadrati \( x^2 \mod 15 \) per \( x = 0, 1, \dots, 14 \) e controllo se \( a \) è presente.
- \(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}\)
I residui quadratici modulo \( 15 \) sono \( 0, 1, 4, 6, 9, 10 \)
Poiché 2 non è nella lista, significa che \( 2 \) non è un residuo quadratico modulo \( 15 \).
Nota. Questo metodo ha il vantaggio di funzionare con qualsiasi modulo (sia primo che composto) ed è facile da implementare quando \( n \) è piccolo. Tuttavia, se \( n \) è molto grande, calcolare tutti i quadrati può essere inefficiente. In questi casi è preferibile usare altri metodi, come il simbolo di Legendre se \( p \) è primo o il simbolo di Jacobi se è composto.
Un metodo più rapido
Quando il modulo è composto (come \( n = 15 \)), il metodo migliore è usare il simbolo di Jacobi.
Per prima cosa fattorizzo il modulo.
\[ 15 = 3 \times 5 \]
Poi calcolo il prodotto dei simboli di Legendre per ciascun fattore primo.
\[ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \times \left(\frac{2}{5}\right) \]
Infine, calcolo i simboli di Legendre separatamente usando il criterio di Eulero, poiché ora i moduli sono tutti numeri primi.
\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]
Nel caso particolare in cui il numeratore è 2, come in questo caso, posso usare una formula specifica che semplifica ulteriormente i calcoli.
\[ \left(\frac{2}{p}\right) = (-1)^{\frac{p^2 - 1}{8}} \]
Modulo 3
\[ \left(\frac{2}{3}\right) = (-1)^{\frac{3^2 - 1}{8}} = (-1)^1 = -1 \]
Verifica. I residui quadratici nel modulo 3 sono 0 e 1. Il numero $ a=2 $ non è un residuo quadratico modulo 3.
- \(0^2 = 0 \equiv 0 \pmod{3}\)
- \(1^2 = 1 \equiv 1 \pmod{3}\)
- \(2^2 = 4 \equiv 1 \pmod{3}\)
Modulo 5
\[ \left(\frac{2}{5}\right) = (-1)^{\frac{5^2 - 1}{8}} = (-1)^3 = -1 \]
Verifica. I residui quadratici nel modulo 5 sono 0, 1, 4. Il numero $ a=2 $ non compare nella lista, quindi non è un residuo quadratico 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}\)
Sostituisco i valori appena trovati nel simbolo di Jacobi.
\[ \left(\frac{2}{15}\right) = \left(\frac{2}{3}\right) \times \left(\frac{2}{5}\right) \]
\[\left(\frac{2}{15}\right) = (-1) \times (-1) = 1 \]
In questo caso il risultato è 1 che NON garantisce che sia un residuo quadratico modulo 15. Significa solo che potrebbe esserlo.
Tuttavia, poiché già che conosco che \( a=2 \) non è un residuo quadratico né modulo 3 né modulo 5, posso affermare che 2 non è un residuo quadratico modulo 15 perché i suoi residui quadratici sarebbero solo quelli comuni ai fattori primi.
Nota. Se il modulo $ n=p_1 \cdot p_2 $ dove $ p_1 $ e $ p_2 $ sono fattori primi distinti, allora un intero $ a $ è un residuo quadratico modulo n se e solo se è un residuo quadratico nel modulo di entrambi i fattori primi. In caso contrario, non è un residuo quadratico modulo n.
In questo modo, invece di perdere tempo a calcolare tutti i quadrati modulo 15, giungo rapidamente al risultato finale.
E così via.
