la legge di eulero

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 k2 ≡ 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

Dimostrazione del criterio di Eulero [modifica]

Come primo caso, assumiamo che a sia un residuo quadratico modulo p. Troviamo quindi k tale che k2 ≡ a (mod p). Allora a(p − 1)/2 = kp − 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 k2 = αi ≡ a (mod p).
Esempi [modifica]

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 = 171 ≡ 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 = 176 ≡ 1 (mod 13), quindi 17 è un residuo quadratico modulo 13. In effetti, 17 ≡ 4 (mod 13), and 22 = 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:
12 = 1
22 = 4
32 = 9
42 = 16
52 = 25 ≡ 8 (mod 17)
62 = 36 ≡ 2 (mod 17)
72 = 49 ≡ 15 (mod 17)
82 = 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 92 ≡ (−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 = 28 ≡ 1 (mod 17), perciò è un residuo quadratico. Analogamente, per il caso di 3 calcoliamo 3(17 − 1)/2 = 38 ≡ -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.