Aritmetica modulare/Congruenze quadratiche: differenze tra le versioni
prime due sezioni |
(Nessuna differenza)
|
Versione delle 16:34, 2 lug 2008
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 . 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
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.