Differenze tra le versioni di "Aritmetica modulare/Congruenze quadratiche"

+lemma di gauss
m (+cat)
(+lemma di gauss)
:<math>\left(\frac{-1}{p}\right)=(-1)^{2k+1}=-1</math>
L'unico caso rimanente è ''p'' =2, per cui -1=1 è (ovviamente) residuo quadratico.
 
== Il lemma di Gauss ==
Avanzando nello studio dei residui quadratici, il prossimo passo è il lemma di Gauss. Sia ''p'' un primo e ''a'' un numero compreso tra 0 e ''p'' (esclusi). Consideriamo i numeri <math>1a,~2a,\ldots,Pa</math> e sottraiamo ''p'' finché non rimane un numero compreso tra <math>-\frac{1}{2}p</math> e <math>\frac{1}{2}p</math> (o, detto in un'altra maniera, prendiamo il valore assoluto modulo ''p'' di questi numeri). Sia ''k'' il numero di elementi negativi in questo insieme. Il lemma di Gauss afferma che
:<math>\left(\frac{a}{p}\right)=(-1)^k</math>
 
La dimostrazione di questo lemma è simile, per certi versi, alla dimostrazione del piccolo teorema di Fermat. È infatti ovvio che, se
:<math>ia\equiv ja\mod p</math>
allora <math>i\equiv j\mod p</math>, e quindi i vari numeri considerati non sono tra loro congrui modulo ''p''. Allo stesso modo, se
:<math>ia\equiv -ja\mod p</math>
allora <math>i\equiv -j\mod p</math> e quindi ''i'' e ''j'' non possono essere entrambi minori o uguali di ''P''. Da questo segue che i numeri <math>1a,~2a,\ldots,Pa</math> sono congrui, in qualche ordine, all'insieme
:<math>\pm 1,~\pm 2,\ldots,\pm P</math>
dove si prende o il più o il meno. Sia ''k'' il numero di segni meno. Allora, moltiplicandoli tutti insieme abbiamo
:<math>(1a)(2a)\cdots(Pa)\equiv (-1)^k 1\cdot 2\cdots P\mod p</math>
e semplificando
:<math>a^P\equiv (-1)^k\mod p</math>
come volevasi dimostrare.
 
[[Categoria:Aritmetica modulare|Congruenze quadratiche]]
66

contributi