title: Criterio di Eulero
text: # 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.
  
  