# Aritmetica modulare/Congruenze quadratiche

Aritmetica modulare
Copertina Bibliografia Tutti i moduli · Sviluppo
    CopertinaAritmetica modulare/Copertina
* La relazione di congruenzaAritmetica modulare/La relazione di congruenza
* Prime proprietà e applicazioniAritmetica modulare/Prime proprietà e applicazioni
* Congruenze lineariAritmetica modulare/Congruenze lineari
* Polinomi in aritmetica modulareAritmetica modulare/Polinomi in aritmetica modulare
* Radici primitiveAritmetica modulare/Radici primitive
* Congruenze quadraticheAritmetica modulare/Congruenze quadratiche
* Alcune applicazioniAritmetica modulare/Alcune applicazioni
* BibliografiaAritmetica modulare/Bibliografia
* EserciziAritmetica modulare/Esercizi
Modifica il sommario
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)$^n$, 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.