Criterio di Eulero
# Criterio di Eulero

In matematica, il criterio di Eulero è usato, in teoria dei numeri, per verificare se un dato intero è un residuo quadratico modulo un primo.

## Definizione

Se p è un primo dispari ed a è un intero coprimo con p, il criterio di Eulero afferma: se a è un residuo quadratico modulo p (ossia esiste un numero k tale che $k^2$ ≡ a (mod p)), allora

    $a^{(p−1)/2}$ ≡ 1 (mod p)

mentre se a è un non-residuo quadratico modulo p, allora

    $a^{(p−1)/2}$ ≡ −1 (mod p).

Alternativamente, si può utilizzare il simbolo di Legendre per enunciare il criterio di Eulero in maniera più compatta. Eulero dimostrò infatti che

    $\left({\frac {a}{p}}\right)\equiv a^{\left({\frac {p-1}{2}}\right)}{\pmod {p}}$

## Dimostrazione del criterio di Eulero

Come primo caso, assumiamo che a sia un residuo quadratico modulo p. Troviamo quindi k tale che $k^2$ ≡ a (mod p). Allora $a^{(p−1)/2}$ ≡ $k^{p−1}$ ≡ 1 (mod p) per il piccolo teorema di Fermat.

Viceversa, assumiamo che $a^{(p−1)/2}$ ≡ 1 (mod p). Sia α un elemento primitivo modulo p, in modo che possiamo dire a = $α^i.$ Allora, $α^{i(p−1)/2}$ ≡ 1 (mod p). Per il piccolo teorema di Fermat, (p − 1) divide i(p − 1)/2, perciò i deve essere pari. Sia k ≡ $α^{i/2}$ (mod p). Abbiamo infine $k^2$ = $α^i$ ≡ a (mod p).

## Esempi

Esempio 1: Trovare per quali primi a è un residuo quadratico

Sia a = 17. Per quali primi p 17 è un residuo quadratico?

Possiamo controllare i primi p manualmente utilizzando la formula di sopra.

Ad esempio, per p = 3, abbiamo $17^{(3−1)/2}$ = $17^1$ ≡ 2 (mod 3) ≡ -1 (mod 3), quindi 17 è un non-residuo quadratico modulo 3.

In un altro caso, per p = 13, otteniamo $17^{(13−1)/2}$ = $17^6$ ≡ 1 (mod 13), quindi 17 è un residuo quadratico modulo 13. In effetti, 17 ≡ 4 (mod 13), e $2^2$ = 4.

Si possono velocizzare questi calcoli sfruttando le proprietà del simbolo di Legendre.

Continuando a calcolare per altri valori di p, otteniamo:

    (17/p) = +1 per p = {13, 19, ...} (17 è un residuo quadratico modulo questi valori)
    (17/p) = −1 per p = {3, 5, 7, 11, 23, ...} (17 è un non-residuo quadratico modulo questi valori)

Esempio 2: Trovare i residui quadratici modulo un primo assegnato p

Quali numeri sono residui quadratici modulo 17?

Si può calcolare a mano:

    $1^2$ = 1
    $2^2$ = 4
    $3^2$ = 9
    $4^2$ = 16
    $5^2$ = 25 ≡ 8 (mod 17)
    $6^2$ = 36 ≡ 2 (mod 17)
    $7^2$ = 49 ≡ 15 (mod 17)
    $8^2$ = 64 ≡ 13 (mod 17)

Perciò l'insieme dei residui quadratici modulo 17 è {1,2,4,8,9,13,15,16}. Ovviamente non c'è bisogno di calcolare i valori da 9 a 16, dal momento che essi sono gli opposti dei numeri da 1 ad 8 (per esempio 9 ≡ −8 (mod 17), dunque $9^2$ ≡ $(−8)^2$ = 64 ≡ 13 (mod 17)).

È possibile trovare a mano questi valori o verificarli con la formula sopra citata. Per controllare se 2 è un residuo quadratico modulo 17, calcoliamo $2^{(17−1)/2}$ = $2^8$ ≡ 1 (mod 17), perciò è un residuo quadratico. Analogamente, per il caso di 3 calcoliamo $3^{(17−1)/2}$ = $3^8$ ≡ -1 (mod 17), dunque 3 è un non-residuo.

Il criterio di Eulero è correlato alla legge di reciprocità quadratica ed è utilizzato nella definizione degli pseudoprimi di Eulero-Jacobi.

