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² ≡ 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² ≡ 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 = αⁱ. 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² = αⁱ ≡ 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¹ ≡ 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⁶ ≡ 1 (mod 13), quindi 17 è un residuo quadratico modulo 13. In effetti, 17 ≡ 4 (mod 13), e 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² = 1

2² = 4

3² = 9

4² = 16

5² = 25 ≡ 8 (mod 17)

6² = 36 ≡ 2 (mod 17)

7² = 49 ≡ 15 (mod 17)

8² = 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² ≡ (−8)² = 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⁸ ≡ 1 (mod 17), perciò è un residuo quadratico. Analogamente, per il caso di 3 calcoliamo 3^{(17 − 1)/2} = 3⁸ ≡ -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.

Bibliografia

• Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9, (Chapter 9.2)
• H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546 - Capitolo III.3