Criterio di Eulero

Da Wikipedia, l'enciclopedia libera.

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

Definizione[modifica | modifica sorgente]

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


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

Dimostrazione del criterio di Eulero[modifica | modifica sorgente]

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

Esempi[modifica | modifica sorgente]

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.

Bibliografia[modifica | modifica sorgente]

  • 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


matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica