Aritmetica modulare/Congruenze quadratiche

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 $ax^{2}+bx+c\equiv 0\mod p$. Possiamo applicare ad essa gli stessi passaggi di un'equazione nei reali:

$ax^{2}+bx+c\equiv 0\mod p\iff 4a^{2}x^{2}+4abx+4ac\equiv 0\mod p$

$4a^{2}x^{2}+4abx+b^{2}\equiv b^{2}-4ac\mod p\iff (2ax+b)^{2}\equiv b^{2}-4ac\mod p$

A questo punto abbiamo bisogno di risolvere due congruenze diverse:

$y^{2}\equiv d\mod p$

$2ax+b\equiv {\overline {y}}\mod p$

dove ${\overline {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 d\mod p$.

È evidente che questa non sempre è risolubile, in quanto $a^{2}\equiv (-a)^{2}\mod p$ per ogni a; quindi per almeno metà dei d non abbiamo soluzioni. Tuttavia, poiché l'equazione $y^{2}-d\equiv 0\mod p$ 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},\ldots ,(p-1)^{2}$

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

$g^{2},~g^{4},~g^{6},\ldots ,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 a\mod p$

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{cases}1&a{\text{ residuo quadratico modulo }}p\\0&a{\text{ divisibile per }}p\\-1&a{\text{ non residuo quadratico modulo }}p\end{cases}}$

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}\mod p=\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 a\mod p$; quindi

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

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

$a^{P}\equiv g^{nP}\mod p$

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

$a^{P}\equiv g^{P}\mod p\equiv -1\mod p$

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 1\mod 4$, ovvero $p=4k+1$, allora $P=2k$, e

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

Se invece $p\equiv 3\mod 4$, 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,\ldots ,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 ja\mod p$

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

$ia\equiv -ja\mod p$

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

$\pm 1,~\pm 2,\ldots ,\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 P\mod p$

e semplificando

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

come volevasi dimostrare.

Come conseguenza di questo lemma si può dimostrare un importante teorema: se p e q sono primi tali che $p\equiv q\mod 4a$ oppure $p\equiv -q\mod 4a$, 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,\ldots ,Pa$ che sono negli intervalli

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

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\leq {\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

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

e ponendo p=4ak+r,

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

cioè

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

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-r\mod 4a$, allora, sostituendo r con 4a-r negli intervalli, si ha

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

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

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 q\mod 4$, 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 -q\mod 4$ 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 3\mod 8$), e infine

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

e 637 è un residuo quadratico modulo 719.