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.

DefinizioneModifica

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 k2a (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 EuleroModifica

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

EsempiModifica

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), e 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.

BibliografiaModifica

  • 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
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica