Il criterio di Eulero
Sia \( p \) un numero primo dispari e sia \( a \) un intero non divisibile per \( p \), cioè coprimo \( MCD(a, p) = 1 \), il criterio di Eulero afferma che: \[ \left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p} \] Dove \( \left( \frac{a}{p} \right) \) è il simbolo di Legendre.
Il calcolo di \( a^{\frac{p-1}{2}} \pmod{p} \) mi permette di determinare se l'intero \( a \) è un residuo quadratico.
- Se $ \left( \frac{a}{p} \right) = + 1 $ allora $ a $ è un residuo quadratico modulo $ p $
- Se $ \left( \frac{a}{p} \right) = - 1 $ allora $ a $ NON è un residuo quadratico modulo $ p $
La generalizzazione per gli interi a=2
Se il numero intero da verificare è \( a = 2 \), il criterio di Eulero ha anche una forma semplificata:
\[ \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 - 1}{8}} \]
Quest'ultima determina se \( 2 \) è un residuo quadratico modulo un primo dispari \( p \).
A cosa serve il criterio di Eulero? E' utilizzato in numerosi campi della matematica, tra cui la teoria dei numeri, la crittografia e nei test di primalità. Ad esempio, è utilizzato nel Test di primalità (Solovay-Strassen).
Un esempio pratico
Devo verificare se l'intero \( a=4 \) è un residuo quadratico modulo \( p=7 \).
Per farlo utilizzo il criterio di Eulero.
\[ \left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]
\[ \left( \frac{4}{7} \right) \equiv 4^{\frac{7-1}{2}} \pmod{7} \]
\[ \left( \frac{4}{7} \right) \equiv 4^{\frac{6}{2}} \pmod{7} \]
\[ \left( \frac{4}{7} \right) \equiv 4^3 \pmod{7} \]
\[ \left( \frac{4}{7} \right) \equiv 64 \pmod{7} \]
\[ \left( \frac{4}{7} \right) \equiv 1 \pmod{7} \]
Poiché il risultato è \( 1 \), posso concludere che \( 4 \) è un residuo quadratico modulo \( 7 \). Infatti, esiste \( x = 2 \) tale che:
\[ 2^2 \equiv 4 \pmod{7} \]
Verifica. Per verificare questo risultato calcolo tutti i residui quadratici del modulo \( p = 7 \) e controllo se 4 è uno di questi.
- \( 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 del modulo \( p=7 \) sono 0, 1, 2, 4. Questo conferma che 4 è un residuo quadratico modulo 7.
Esempio 2
In questo esercizio devo verificare se \( a=3 \) è un residuo quadratico modulo \( p=7 \)
Utilizzo il criterio di Eulero.
\[ \left( \frac{3}{7} \right) \equiv 3^{\frac{7-1}{2}} \pmod{7} \]
\[ \left( \frac{3}{7} \right) \equiv 3^3 \pmod{7} \]
\[ \left( \frac{3}{7} \right) \equiv 27 \pmod{7} \]
\[ \left( \frac{3}{7} \right) \equiv 6 \pmod{7} \]
Sapendo che \( 6 \equiv -1 \pmod{7} \)
\[ \left( \frac{3}{7} \right) \equiv -1 \pmod{7} \]
Poiché il risultato è \( -1 \), posso concludere che \( 3 \) non è un residuo quadratico modulo \( 7 \).
Proprietà del criterio di Eulero
Il criterio di Eulero ha diverse proprietà importanti.
- Moltiplicatività del simbolo di Legendre
Se \( a \) e \( b \) sono interi, allora: \[ \left( \frac{a \cdot b}{p} \right) = \left( \frac{a}{p} \right) \cdot \left( \frac{b}{p} \right).
\] - Compatibilità con il Piccolo Teorema di Fermat
Per il piccolo teorema di Fermat, so che \[ a^{p-1} \equiv 1 \pmod{p} \] Poiché il criterio di Eulero usa l’esponente \( \frac{p-1}{2} \), sfrutta questa proprietà per determinare i residui quadratici.
E così via.
