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 (4ax+b)^{2}\equiv b^{2}-4ac\mod p$

A questo punto abbiamo bisogno di risolvere due congruenze diverse:

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

$4ax+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.