Aritmetica modulare/Congruenze quadratiche

Template:Aritmetica modulare In questo modulo verranno studiate le congruenze quadratiche, ossia di secondo grado, e in particolare verrà dimostrata la legge di reciprocità quadratica.

Introduzione

Partiamo da un'equazione qualsiasi di secondo grado in un'incognita con un modulo primo (maggiore di 2), ovvero $a{x}^2+bx+c\equiv 0modp$. Possiamo applicare ad essa gli stessi passaggi di un'equazione nei reali:

$a{x}^2+bx+c\equiv 0modp⟺4a^2{x}^2+4abx+4ac\equiv 0modp$

$4a^2{x}^2+4abx+b^2\equiv b^2-4acmodp⟺(2ax+b{)}^2\equiv b^2-4acmodp$

A questo punto abbiamo bisogno di risolvere due congruenze diverse:

$y^2\equiv dmodp$

$2ax+b\equiv \bar{y}modp$

dove $\bar{y}$ è una soluzione della prima congruenza. Poiché quest'ultima è sempre risolubile (se a non è divisibile per p), per risolvere la congruenza originaria basta concentrarsi su quelle del tipo $y^2\equiv dmodp$.

È evidente che questa non sempre è risolubile, in quanto $a^2\equiv (-a{)}^{2}modp$ per ogni a; quindi per almeno metà dei d non abbiamo soluzioni. Tuttavia, poiché l'equazione $y^2-d\equiv 0modp$ non può avere più di due soluzioni, e visto che una soluzione a ne "chiama" un'altra -a, esattamente metà dei d hanno delle soluzioni. Chiameremo quelli la cui congruenza è risolubile residui quadratici.

C'è un altro modo, più generale, per vedere le cose. Consideriamo un generatore g modulo p. L'insieme dei numeri

$1^2,2^2,3^2,\dots ,(p-1{)}^2$

coincide, a parte l'ordine, con quello dei numeri

$g^2,g^4,g^6,\dots ,g^{2(p-1)}$

Riducendo modulo p -1 gli esponenti, questi rimarranno pari (perché anche p -1 è pari); quindi i residui quadratici sono esattamente quegli elementi il cui indice è pari. Questo metodo può essere esteso per individuare i residui n-esimi, cioè gli a per cui ha soluzioni una congruenza del tipo

$x^n\equiv amodp$

Se n divide p -1, allora i residui n -esimi sono esattamente gli elementi i cui indici sono divisibile per n; viceversa, se n e p -1 sono coprimi, tutti i numeri sono residui n -esimi. Nei casi intermedi è facile dimostrare che, se k = MCD(n,p -1), allora i residui n -esimi coincidono con i residui k -esimi.

Il simbolo di Legendre e il criterio di Eulero

Per indicare se un numero è residuo quadratico o meno, si può usare il cosiddetto simbolo di Legendre: questo è

$\left(\frac{a}{p}\right)=\{\begin{array}{cc}1& a\text{ residuo quadratico modulo }p\\ 0& a\text{ divisibile per }p\\ -1& a\text{ non residuo quadratico modulo }p\end{array}$

Attraverso l'uso degli indici è facile dimostrare che

$\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$

cioè il simbolo di Legendre è una funzione completamente moltiplicativa nel suo primo argomento. Questo avviene perché, se a e b sono entrambi residui o non residui, sommando i loro indici si avrà un indice pari, ovvero moltiplicandoli si avrà un residuo quadratico; viceversa, se uno è un residuo e l'altro no, l'indice del loro prodotto sarà dispari, e ab non è un residuo.

Un test generale ma di non molta utilità pratica è il criterio di Eulero. Posto $P=\frac{p-1}{2}$, questo afferma che

$a^{P}modp=\left(\frac{a}{p}\right)$

Anche questo è banale se considerato con gli indici: se a è un residuo, allora esiste k tale che $k^2\equiv amodp$; quindi

$a^P\equiv k^{2P}modp\equiv a^{p-1}modp\equiv 1modp$

Se viceversa a non è un residuo quadratico, allora $a\equiv g^{n}modp$, dove g è una radice primitiva e n è dispari, e

$a^P\equiv g^{nP}modp$

Poiché n è dispari, nP è congruo a P modulo p -1, ovvero

$a^P\equiv g^{P}modp\equiv -1modp$

perché l'ordine di g è esattamente p -1.

Attraverso questo criterio si determina immediatamente la caratteristica quadratica di -1 modulo un qualsiasi primo p. Se infatti $p\equiv 1mod4$, ovvero $p=4k+1$, allora $P=2k$, e

$\left(\frac{-1}{p}\right)=(-1{)}^{2k}=1$

Se invece $p\equiv 3mod4$, cioè $p=4k+3$, $P=2k+1$ e

$\left(\frac{-1}{p}\right)=(-1{)}^{2k+1}=-1$

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 $1a,2a,\dots ,Pa$ e sottraiamo p finché non rimane un numero compreso tra $-\frac{1}{2}p$ e $\frac{1}{2}p$ (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

$\left(\frac{a}{p}\right)=(-1{)}^k$

La dimostrazione di questo lemma è simile, per certi versi, alla dimostrazione del piccolo teorema di Fermat. È infatti ovvio che, se

$ia\equiv jamodp$

allora $i\equiv jmodp$, e quindi i vari numeri considerati non sono tra loro congrui modulo p. Allo stesso modo, se

$ia\equiv -jamodp$

allora $i\equiv -jmodp$ e quindi i e j non possono essere entrambi minori o uguali di P. Da questo segue che i numeri $1a,2a,\dots ,Pa$ sono congrui, in qualche ordine, all'insieme

$\pm 1,\pm 2,\dots ,\pm P$

dove si prende o il più o il meno. Sia k il numero di segni meno. Allora, moltiplicandoli tutti insieme abbiamo

$(1a)(2a)\cdots (Pa)\equiv (-1{)}^{k}1\cdot 2\cdots Pmodp$

e semplificando

$a^P\equiv (-1{)}^{k}modp$

come volevasi dimostrare.

Come conseguenza di questo lemma si può dimostrare un importante teorema: se p e q sono primi tali che $p\equiv qmod4a$ oppure $p\equiv -qmod4a$, allora

$\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)$

Per il lemma di Gauss, infatti, il primo dei due simboli di Legendre dipende dal numero di interi dell'insieme $a,2a,3a,\dots ,Pa$ che sono negli intervalli

$(\frac{1}{2}p,p),(\frac{3}{2}p,2p),(\frac{5}{2}p,3p),\dots ,((b-\frac{1}{2}p),bp)$

dove $b=\frac{1}{2}(a-1)$ o $b=\frac{1}{2}a$, a seconda di quale dei due sia un intero. ($Pa=\frac{1}{2}a(p-1)=\frac{1}{2}ap-\frac{1}{2}a\le \frac{1}{2}ap$)

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

$(\frac{1}{2}\frac{p}{a},\frac{p}{a}),(\frac{3}{2}\frac{p}{a},2\frac{p}{a}),\dots ,((b-\frac{1}{2}\frac{p}{a}),b\frac{p}{a})$

e ponendo p=4ak+r,

$(\frac{1}{2}\frac{4ak+r}{a},\frac{4ak+r}{a}),(\frac{3}{2}\frac{4ak+r}{a},2\frac{4ak+r}{a}),\dots ,((b-\frac{1}{2}\frac{4ak+r}{a}),b\frac{4ak+r}{a})$

cioè

$(2k+\frac{1}{2}\frac{r}{a},4k+\frac{r}{a}),(6k+\frac{3}{2}\frac{r}{a},8k+2\frac{r}{a}),\dots ,((2kb+\frac{(2b-1)r}{a}),4kb+\frac{br}{a})$

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 $\left(\frac{a}{p}\right)$ dipende soltanto da r. Ma questo vuol dire che per ogni q congruo a r (cioè a p) modulo 4a la caratteristica quadratica è la stessa. Questo dimostra la prima parte del teorema. Se invece $q\equiv -p\equiv 4a-rmod4a$, allora, sostituendo r con 4a-r negli intervalli, si ha

$(2k+\frac{1}{2}\frac{4a-r}{a},4k+\frac{4a-r}{a}),(6k+\frac{3}{2}\frac{4a-r}{a},8k+2\frac{4a-r}{a}),\dots ,((2kb+\frac{(2b-1)(4a-r)}{a}),4kb+\frac{b(4a-r)}{a})$

$(2k+2-\frac{1}{2}\frac{r}{a},4k+4-\frac{r}{a}),(6k+6-\frac{3}{2}\frac{r}{a},8k+8-\frac{2r}{a}),\dots ,((2kb+4(2b-1)-\frac{(2b-1)r}{a}),4kb+4b-\frac{b(4a-r)}{a})$

che, come numero di interi, coincide col numero precedente.

Il caso a=2

Consideriamo in particolare il caso a=2. Questo può essere trattato con lo stesso metodo visto precedentemente: sia p=8k+r un primo; i numeri 2, 4, 6, ..., 2P sono tutti minori di p, e quindi per il lemma di Gauss la caratteristica quadratica di 2 corrisponde a (-1)ⁿ, dove n è la parità del numero di quegli elementi maggiori di p/2. Sia x un numero minore di P.

$\frac{1}{2}p<2x<p$

equivale a

$2k+\frac{1}{4}r<x<4k+\frac{1}{2}r$

e ignorando 2k e 4k, che non variano la parità, si ottengono, come soluzioni di x in interi:

• 0 soluzioni se r=1;
• 1 soluzione se r=3 o r=5;
• 2 soluzioni se r=7

e quindi 2 è residuo quadratico se $p=8k\pm 1$ e non lo è altrimenti.

Naturalmente si poteva anche applicare il teorema generale dimostrato precedentemente, trovando un primo congruo a 1 modulo 8 e uno congruo a 3, e dedurne il comportamento per ogni p.

La legge di reciprocità

La legge di reciprocità quadratica, infine, afferma che

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\frac{q-1}{2}}$

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 $p\equiv qmod4$, ovvero che $p-q=4a$ (possiamo supporre p>q) per un qualche intero a. Allora

$\left(\frac{p}{q}\right)=\left(\frac{4a+q}{q}\right)=\left(\frac{4a}{q}\right)=\left(\frac{a}{q}\right)$

e similmente

$\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)$

e quindi

$\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)$

Ora p e q hanno lo stesso resto nella divisione per 4a (p=4a+q) e quindi due dei coefficienti di Legendre sono uguali, e quindi il loro prodotto è 1. Cioè

$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=\left(\frac{-1}{p}\right)$

che, per quanto abbiamo detto prima, è 1 se p è congruo a 1 modulo 4 e -1 altrimenti.

Se invece $p\equiv -qmod4$ si ha p+q=4a, e

$\left(\frac{p}{q}\right)=\left(\frac{4a-q}{q}\right)=\left(\frac{4a}{q}\right)=\left(\frac{a}{q}\right)$

così come

$\left(\frac{q}{p}\right)=\left(\frac{4a-p}{p}\right)=\left(\frac{4a}{p}\right)=\left(\frac{a}{p}\right)$

Questi due risultati sono di nuovo uguali per il teorema precedente, in quanto p e q hanno resti opposti nella divisione per 4a, e quindi sono uguali, e il loro prodotto è 1.

Esempi

Per mostrare la potenza di questo teorema, calcoliamo ad esempio

$\left(\frac{637}{719}\right)$

Fattorizzando 637, abbiamo

$\left(\frac{637}{719}\right)=\left(\frac{7}{719}\right)\left(\frac{91}{719}\right)$

719 è congruo a 3 modulo 4, così come 7 e 91; quindi

$\left(\frac{7}{719}\right)=-\left(\frac{719}{7}\right)=-\left(\frac{5}{7}\right)=(-1)(-1)=1$

$\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$

(considerando che $91\equiv 3mod8$), e infine

$\left(\frac{637}{719}\right)=1\cdot 1=1$

e 637 è un residuo quadratico modulo 719. Template:Avanzamento