Aritmetica modulare/Congruenze quadratiche - Wikibooks, manuali e libri di testo liberi (2024)

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

Introduzione[modifica]

Partiamo da un'equazione qualsiasi di secondo grado in un'incognita con un modulo primo (maggiore di 2), ovvero . Possiamo applicare ad essa gli stessi passaggi di un'equazione nei reali:

A questo punto abbiamo bisogno di risolvere due congruenze diverse:

dove è 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 .

È evidente che questa non sempre è risolubile, in quanto per ogni a; quindi per almeno metà dei d non abbiamo soluzioni. Tuttavia, poiché l'equazione 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

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

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

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[modifica]

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

Attraverso l'uso degli indici è facile dimostrare che

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 , questo afferma che

Anche questo è banale se considerato con gli indici: se a è un residuo, allora esiste k tale che ; quindi

Se viceversa a non è un residuo quadratico, allora , dove g è una radice primitiva e n è dispari, e

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

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 , ovvero , allora , e

Se invece , cioè , e

L'unico caso rimanente è p =2, per cui -1=1 è (ovviamente) residuo quadratico.

Il lemma di Gauss[modifica]

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 e sottraiamo p finché non rimane un numero compreso tra e (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

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

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

allora e quindi i e j non possono essere entrambi minori o uguali di P. Da questo segue che i numeri sono congrui, in qualche ordine, all'insieme

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

e semplificando

come volevasi dimostrare.

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

Per il lemma di Gauss, infatti, il primo dei due simboli di Legendre dipende dal numero di interi dell'insieme che sono negli intervalli

dove o , a seconda di quale dei due sia un intero. ()

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

e ponendo p=4ak+r,

cioè

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

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

Il caso a=2[modifica]

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.

equivale a

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 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à[modifica]

La legge di reciprocità quadratica, infine, afferma che

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

e similmente

e quindi

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è

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

Se invece si ha p+q=4a, e

così come

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[modifica]

Per mostrare la potenza di questo teorema, calcoliamo ad esempio

Fattorizzando 637, abbiamo

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

(considerando che ), e infine

e 637 è un residuo quadratico modulo 719.