title: Lemma di Gauss (teoria dei numeri)
text: # Lemma di Gauss (teoria dei numeri)
  
  In teoria dei numeri, il lemma di Gauss, che ha preso il nome da Carl Friedrich Gauss, è un teorema utilizzato in alcune dimostrazioni della reciprocità quadratica.
  
  Per ogni primo dispari $p$, sia $a$ un intero coprimo con $p$. Si considerino gli interi:
  
      $a,2a,3a,\ldots ,{\frac {p-1}{2}}a$
  
  e i loro residui modulo $p$ ridotti nell'intervallo $\left[-{\frac {p}{2}},{\frac {p}{2}}\right]$. Sia $s$ il numero di questi residui che sono negativi. Allora:
  
      $\left({\frac {a}{p}}\right)=(-1)^{s},$
  
  dove $\left({\frac {a}{p}}\right)$ è il simbolo di Legendre. Da un punto di vista piuttosto sofisticato, ciò rappresenta un caso di trasferimento.
  
  ## Dimostrazione
  
  Per il criterio di Eulero si sa che
  
      $\left({\frac {a}{p}}\right)=a^{\frac {p-1}{2}}{\pmod {p}}$
  
  moltiplicando entrambi i membri per il fattoriale di ${\frac {p-1}{2}}$
  
      $\left({\frac {a}{p}}\right)\left({\frac {p-1}{2}}\right)!=\prod _{n=1}^{\frac {p-1}{2}}an{\pmod {p}}$
  
  consideriamo adesso i residui di $an$ ridotti nell'intervallo $\left[-{\frac {p}{2}},{\frac {p}{2}}\right]$. Allora:
  
  * non ci sono due residui uguali; infatti se
  
         $ak_{1}=ak_{2}{\pmod {p}}$
      allora $p|k_{1}-k_{2}$, ed essendo $k_{1},k_{2}<p$, ciò e possibile solo se $k_{1}=k_{2}$
  * non ci sono due residui opposti; infatti se
  
         $ak_{1}=-ak_{2}{\pmod {p}}$
      allora $p|k_{1}+k_{2}$ ma essendo $k_{1},k_{2}<{\frac {p}{2}}$ ciò è impossibile.
  
  Di conseguenza i valori assoluti dei residui $an$ sono tutti diversi e nell'intervallo $\left[1,{\frac {p-1}{2}}\right]$, dunque per il prodotto di detti residui vale
  
      $\prod _{n=1}^{\frac {p-1}{2}}an=\left({\frac {p-1}{2}}\right)!\left(-1\right)^{s}{\pmod {p}}$
  
  dove $s$ è il numero dei residui negativi, quindi
  
      $\left({\frac {a}{p}}\right)\left({\frac {p-1}{2}}\right)!=\left({\frac {p-1}{2}}\right)!\left(-1\right)^{s}{\pmod {p}}$
  
  e semplificando per il fattoriale di ${\frac {p-1}{2}}$ si ottiene la tesi:
  
      $\left({\frac {a}{p}}\right)=\left(-1\right)^{s}$
  