Aritmetica modulare/Alcune applicazioni

Wikibooks, manuali e libri di testo liberi.
Jump to navigation Jump to search

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

Numeri primi[modifica]

I numeri primi sono infiniti. La prima e più semplice dimostrazione è quella di Euclide: se fossero in numero finito (ad esempio ), allora il numero

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 , allora quando (dove n è il prodotto di tutti i primi) viene scomposto attraverso il teorema cinese del resto, ogni suo elemento x sarebbe divisibile per qualche , e quindi rappresentando x secondo i moduli 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 : allora è ancora congruo a 3 modulo 4 e non è diviso da nessuno dei . 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 . Costruiamo il numero : questo è ancora una volta congruo a 1 modulo 4, e non è divisibile per nessuno dei . 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 , e quindi dovrebbe essere risolubile la congruenza

ovvero -1 dovrebbe essere un residuo quadratico modulo q, il che è impossibile perché . 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[modifica]

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 . Per il lemma di Thue esiste una soluzione alla congruenza

dove x e y sono minori in modulo di . Elevando al quadrato entrambi i lati si ha

(dove k è intero). Ma poiché , si ha e quindi

Di conseguenza si deve avere k=1, cioè .

Un problema additivo[modifica]

Abbiamo visto che in vi sono 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 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 (dove gli sono tutti i residui) sono tutti diversi e sono tutti non residui. Inoltre, se , allora

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