Aritmetica modulare/Congruenze quadratiche: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
+lemma di gauss
concludo
Riga 60:
:<math>a^P\equiv (-1)^k\mod p</math>
come volevasi dimostrare.
 
Come conseguenza di questo lemma si può dimostrare un importante teorema: se ''p'' e ''q'' sono primi tali che <math>p\equiv q\mod 4a</math> oppure <math>p\equiv -q\mod 4a</math>, allora
:<math>\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)</math>
 
Per il lemma di Gauss, infatti, il primo dei due simboli di Legendre dipende dal numero di interi dell'insieme <math>a,~2a,~3a,\ldots,Pa</math> che sono negli intervalli
:<math>\left(\frac{1}{2}p,p\right),~\left(\frac{3}{2}p,2p\right),~\left(\frac{5}{2}p,3p\right),\ldots,\left(\left(b-\frac{1}{2}p\right),bp\right)</math>
dove <math>b=\frac{1}{2}(a-1)</math> o <math>b=\frac{1}{2}a</math>, a seconda di quale dei due sia un intero. (<math>Pa=\frac{1}{2}a(p-1)=\frac{1}{2}ap-\frac{1}{2}a\leq\frac{1}{2}ap</math>)
 
Questo può essere interpretato come il numero di multipli di ''a'' nei vari intervalli; ovvero, dividendo tutto per ''a'', il numero di interi negli intervalli
:<math>\left(\frac{1}{2}\frac{p}{a},\frac{p}{a}\right),~\left(\frac{3}{2}\frac{p}{a},2\frac{p}{a}\right),\ldots,\left(\left(b-\frac{1}{2}\frac{p}{a}\right),b\frac{p}{a}\right)</math>
e ponendo ''p''=4''ak''+''r'',
:<math>\left(\frac{1}{2}\frac{4ak+r}{a},\frac{4ak+r}{a}\right),~\left(\frac{3}{2}\frac{4ak+r}{a},2\frac{4ak+r}{a}\right),\ldots,\left(\left(b-\frac{1}{2}\frac{4ak+r}{a}\right),b\frac{4ak+r}{a}\right)</math>
cioè
:<math>\left(2k+\frac{1}{2}\frac{r}{a},4k+\frac{r}{a}\right),~\left(6k+\frac{3}{2}\frac{r}{a},8k+2\frac{r}{a}\right),\ldots,\left(\left(2kb+\frac{(2b-1)r}{a}\right),4kb+\frac{br}{a}\right)</math>
 
Poiché a noi interessa solamente la ''parità'' del numero degli interi, e nessuno degli estremi degli intervalli è un intero, possiamo eliminare i vari multipli di ''k''; quindi <math>\left(\frac{a}{p}\right)</math> dipende soltanto da ''r''. Ma questo vuol dire che per ogni ''q'' congruo a ''r'' (cioè a ''p'') modulo 4''a'' la caratteristica quadratica è la stessa. Questo dimostra la prima parte del teorema. Se invece <math>q\equiv -p\equiv 4a-r\mod 4a</math>, allora, sostituendo ''r'' con 4''a''-''r'' negli intervalli, si ha
:<math>\left(2k+\frac{1}{2}\frac{4a-r}{a},4k+\frac{4a-r}{a}\right),~\left(6k+\frac{3}{2}\frac{4a-r}{a},8k+2\frac{4a-r}{a}\right),\ldots,\left(\left(2kb+\frac{(2b-1)(4a-r)}{a}\right),4kb+\frac{b(4a-r)}{a}\right)</math>
:<math>\left(2k+2-\frac{1}{2}\frac{r}{a},4k+4-\frac{r}{a}\right),~\left(6k+6-\frac{3}{2}\frac{r}{a},8k+8-\frac{2r}{a}\right),\ldots,\left(\left(2kb+4(2b-1)-\frac{(2b-1)r}{a}\right),4kb+4b-\frac{b(4a-r)}{a}\right)</math>
che, come numero di interi, coincide col numero precedente.
 
== La legge di reciprocità ==
La legge di reciprocità quadratica, infine, afferma che
:<math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}</math>
o, detto a parole, che pa caratteristica quadratica di ''p'' modulo ''q'' e di ''q'' modulo ''p'' è la stessa a meno che non siano entrambi congrui a 3 modulo 4.
 
Supponiamo innanzitutto che <math>p\equiv q\mod 4</math>, ovvero che <math>p-q=4a</math> (possiamo supporre ''p''>''q'') per un qualche intero ''a''. Allora
:<math>\left(\frac{p}{q}\right)=\left(\frac{4a+q}{q}\right)=\left(\frac{4a}{q}\right)=\left(\frac{a}{q}\right)</math>
e similmente
:<math>\left(\frac{q}{p}\right)=\left(\frac{p-4a}{p}\right)=\left(\frac{-4a}{p}\right)\left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)</math>
e quindi
:<math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(\frac{a}{q}\right)\left(\frac{a}{p}\right)\left(\frac{-1}{p}\right)</math>
Ora ''p'' e ''q'' hanno lo stesso resto nella divisione per 4''a'' (''p''=4''a''+''q'') e quindi due dei coefficienti di Legendre sono uguali, e quindi il loro prodotto è 1. Cioè
:<math>\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(\frac{-1}{p}\right)</math>
che, per quanto abbiamo detto prima, è 1 se ''p'' è congruo a 1 modulo 4 e -1 altrimenti.
 
Se invece <math>p\equiv -q\mod 4</math> si ha ''p''+''q''=4''a'', e
:<math>\left(\frac{p}{q}\right)=\left(\frac{4a-q}{q}\right)=\left(\frac{4a}{q}\right)=\left(\frac{a}{q}\right)</math>
così come
:<math>\left(\frac{q}{p}\right)=\left(\frac{4a-p}{p}\right)=\left(\frac{4a}{p}\right)=\left(\frac{a}{p}\right)</math>
Questi due risultati sono di nuovo uguali per il teorema precedente, in quanto ''p'' e ''q'' hanno resti opposti nella divisione per 4''a'', e quindi sono uguali, e il loro prodotto è 1.
 
=== Esempi ===
Per mostrare la potenza di questo teorema, calcoliamo ad esempio
:<math>\left(\frac{637}{719}\right)</math>
Fattorizzando 520, abbiamo
:<math>\left(\frac{637}{719}\right)=\left(\frac{7}{719}\right)\left(\frac{91}{719}\right)</math>
719 è congruo a 3 modulo 4, così come 7 e 91; quindi
:<math>\left(\frac{7}{719}\right)=-\left(\frac{719}{7}\right)=-\left(\frac{5}{7}\right)=(-1)(-1)=1</math>
:<math>\left(\frac{91}{719}\right)=-\left(\frac{719}{91}\right)=-\left(\frac{82}{91}\right)=-\left(\frac{2}{91}\right)\left(\frac{41}{91}\right)=(-1)\left(\frac{2}{3}\right)\left(\frac{91}{41}\right)=(-1)(-1)\left(\frac{9}{41}\right)=1</math>
(considerando che <math>3\equiv 91\mod 8</math>)
e infine
<math>\left(\frac{637}{719}\right)=1\cdot 1=1</math>
e 637 è un residuo quadratico modulo 719.
 
[[Categoria:Aritmetica modulare|Congruenze quadratiche]]