Aritmetica modulare/Congruenze quadratiche

Wikibooks, manuali e libri di testo liberi.

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

Indice

1 Introduzione
2 Il simbolo di Legendre e il criterio di Eulero
3 Il lemma di Gauss
- 3.1 Il caso a=2
4 La legge di reciprocità
- 4.1 Esempi

[modifica] 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^2x^2+4abx+4ac\equiv 0\mod p$

$4a^2x^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.

[modifica] 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 = 4 k + 1$ , allora $P = 2 k$ , e

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

Se invece $p\equiv 3\mod 4$ , cioè $p = 4 k + 3$ , $P = 2 k + 1$ e

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

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

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

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

[modifica] 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 = 4 a$ (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.

[modifica] Esempi

Per mostrare la potenza di questo teorema, calcoliamo ad esempio

$\left(\frac{637}{719}\right)$

Fattorizzando 520, 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.

Aritmetica modulare/Congruenze quadratiche

Wikibooks, manuali e libri di testo liberi.

Indice

[modifica] Introduzione

[modifica] Il simbolo di Legendre e il criterio di Eulero

[modifica] Il lemma di Gauss

[modifica] Il caso a=2

[modifica] La legge di reciprocità

[modifica] Esempi

Visite

Strumenti personali

Navigazione

Comunità

Stampa/esporta

Ricerca

strumenti