Aritmetica modulare/Alcune applicazioni

In questo capitolo vedremo tre applicazioni dell'aritmetica modulare alla teoria dei numeri.

Numeri primi

I numeri primi sono infiniti. La prima e più semplice dimostrazione è quella di Euclide: se fossero in numero finito (ad esempio $p_{1},~p_{2},\ldots ,p_{n}$), allora il numero

$p_{1}p_{2}p_{3}\cdots p_{n}-1$

non è uno dei primi, ma non è diviso da nessuno di essi, e quindi è primo, contro l'assunzione che tutti i primi siano contenuti nell'elenco precedente.

Questa dimostrazione ammette un'interpretazione in aritmetica modulare: se infatti i primi fossero soltanto quelli nella lista $p_{1},~p_{2},\ldots ,p_{n}$, allora quando $\mathbb {Z} _{n}$ (dove n è il prodotto di tutti i primi) viene scomposto attraverso il teorema cinese del resto, ogni suo elemento x sarebbe divisibile per qualche $p_{i}$, e quindi rappresentando x secondo i moduli $p_{1},~p_{2},\ldots ,p_{n}$ ci sarebbe sempre almeno uno zero. Ma questo è palesemente falso, in quanto basta scegliere la n-upla (1,1,...,-1) per ottenere un elemento che non verifica le ipotesi.

L'aritmetica modulare permette anche di spingersi oltre, e di dimostrare che esistono infiniti numeri primi congrui a 3 modulo 4. Supponiamo infatti tutti i primi di questo tipo $p_{1},~p_{2},\ldots ,p_{n}$: allora $n=4p_{1}p_{2}p_{3}\cdots p_{n}-1$ è ancora congruo a 3 modulo 4 e non è diviso da nessuno dei $p_{i}$. Ma se tutti i suoi fattori sono congrui a 1 modulo 4, allora anche n lo sarebbe, il che è impossibile. Quindi esistono infiniti numeri primi nella forma 4k+3. Una simile dimostrazione si applica ai primi congrui a 2 modulo 3 e congrui a 5 modulo 6.

Fin qui l'uso che è stato fatto dell'aritmetica modulare è puramente linguistico, cioè è semplicemente una conveniente notazione per spiegare le dimostrazioni. Per dimostrare che esistono infiniti primi congrui a 1 modulo 4 la situazione cambia, in quanto è necessario usare alcune nozioni della teoria dei residui quadratici.

Supponiamo, ancora una volta, che i primi di questo tipo siano finiti, e che siano $p_{1},~p_{2},\ldots ,p_{n}$. Costruiamo il numero $n=4(p_{1}p_{2}p_{3}\cdots p_{n})^{2}+1$: questo è ancora una volta congruo a 1 modulo 4, e non è divisibile per nessuno dei $p_{i}$. Questo ancora non dimostra il teorema (potrebbero esserci due fattori primi congrui a 3, che moltiplicati danno 1): supponiamo ora che q sia congruo a 3 modulo 4 e che divida n. Questo è nella forma $x^{2}+1$, e quindi dovrebbe essere risolubile la congruenza

$x^{2}+1\equiv 0\mod q$

ovvero -1 dovrebbe essere un residuo quadratico modulo q, il che è impossibile perché $q\equiv 3\mod 4$. Quindi n dovrebbe essere primo e congruo a 1 modulo 4, il che è assurdo. Quindi esistono infiniti primi nella forma 4k+1.

In realtà questi sono corollari di un teorema molto più generale, che dice che in ogni progressione aritmetica ak+b, dove a e b sono coprimi, esistono infiniti numeri primi; tuttavia i metodi necessari sono molto più complessi di quelli qui applicati.

Teorema di Fermat sulle somme di due quadrati

Questo teorema afferma che un numero primo p può essere scritto come somma di due quadrati se e solo se p=2 oppure p è congruo a 1 modulo 4.

Una delle implicazioni è facile da dimostrare: tutti i quadrati sono congrui a 0 o a 1 modulo 4, e quindi la somma di due di essi può essere congrua solamente a 0, 1 o 2.

Per l'altra implicazione una dimostrazione molto diretta si ottiene attraverso il lemma di Thue: sia a tale che $a^{2}+1\equiv 0\mod p$. Per il lemma di Thue esiste una soluzione alla congruenza

$ax\equiv y\mod p$

dove x e y sono minori in modulo di ${\sqrt {p}}$. Elevando al quadrato entrambi i lati si ha

$a^{2}x^{2}\equiv y^{2}\mod p\Longrightarrow -x^{2}\equiv y^{2}\mod p\Longrightarrow x^{2}+y^{2}\equiv 0\mod p\Longrightarrow x^{2}+y^{2}=kp$

(dove k è intero). Ma poiché $|x|,|y|<{\sqrt {p}}$, si ha $x^{2},y^{2}<p$ e quindi

$x^{2}+y^{2}<p+p=2p$

Di conseguenza si deve avere k=1, cioè $x^{2}+y^{2}=p$.

Un problema additivo

Abbiamo visto che in $\mathbb {Z} _{p}$ vi sono ${\frac {p-1}{2}}$ residui quadratici. È possibile chiedersi se ogni altro non residuo può essere scritto come somma di due residui. La risposta è positiva, e la dimostrazione è sorprendentemente semplice.

Naturalmente dobbiamo escludere 0 dal teorema, oppure considerarlo come la somma di zero residui quadratici, in quanto non sempre la congruenza $x^{2}+y^{2}\equiv 0\mod p$ ha soluzioni diverse da (0,0).

Sia a un non residuo. Poiché ax non è congruo a ay se x non è congruo a y, gli elementi $ax_{1},~ax_{2},\ldots ,ax_{k}$ (dove gli $x_{i}$ sono tutti i residui) sono tutti diversi e sono tutti non residui. Inoltre, se $a\equiv x^{2}+y^{2}$, allora

$az^{2}\equiv (xz)^{2}+(yz)^{2}$

e quindi se un non residuo è somma di due residui lo sono anche tutti gli altri.

A questo punto, basta osservare che esiste almeno un residuo x tale che x+1 non è un residuo, perché altrimenti tutti gli elementi sarebbero dei residui quadratici, e quindi tutti i non residui sono somma di due residui.

Argomenti del genere possono essere estesi anche a residui di ordine superiore, sebbene con considerazioni molto più lunghe: il maggior ostacolo è il fatto che, moltiplicando un a per i residui n-esimi, si ottengono soltanto ${\frac {p-1}{n}}$ altri elementi, e quindi non tutti sono ottenuti in questo modo; diventa quindi necessario introdurre una relazione di equivalenza che tenda conto di questo fatto, e dimostrare che gli elementi di ogni classe sono somma di un certo numero di residui n-esimi.