Visualizza wikitesto di Aritmetica modulare/La relazione di congruenza

{{aritmetica modulare}}
Questo capitolo tratta le proprietà elementari delle congruenze: la definizione delle relazioni di congruenza e del relativo insieme quoziente, più il suo rapporto con le operazioni.

== La relazione ==
Sia <math>\mathbb{Z}</math> l'insieme dei numeri interi, e ''n'' un intero maggiore o uguale a 2. All'interno di <math>\mathbb{Z}</math> definiamo la '''relazione di congruenza''' <math>\equiv_n</math> come:
:<math>a\equiv_n b\iff n|(a-b)</math>
dove la notazione ''k''|''h'' indica che ''k'' divide ''h'', ossia esiste un numero intero ''m'' tale che ''h''=''mk''. Il fatto che ''a'' è in relazione con ''b'' può anche essere scritto come
:<math>a\equiv b\mod n</math> 
e può essere espresso dicendo che ''a'' è '''congruo''', o '''congruente''' a ''b'' modulo ''n''. Chiaramente, diverse scelte di ''n'' porteranno a diverse relazioni, ma molte proprietà (e tutte quelle di carattere elementare) sono indipendenti da questa scelta.

È di facile verifica che la relazione <math>\equiv_n</math> così definita è una particolare relazione di equivalenza: 
*è riflessiva: 
:<math>a-a=0</math>, e 0 è divisibile per ''n'';
*è simmetrica: 
se ''a'' - ''b'' = ''kn'', allora ''b'' - ''a'' = -(''a'' - ''b'')=-''kn''=(-''k'')''n'', e -''k'' è ancora un intero;
*è transitiva: 
se ''a'' - ''b'' = ''kn'' e ''b'' - ''c'' = ''jn'', allora 
:<math>a-c=a-b+b-c=kn+jn=(k+j)n</math>

Inoltre, se ''b'' e ''c'' sono due numeri diversi tra loro ma entrambi compresi tra 0 e ''n'' -1, allora non possono essere congruenti: uno dei due deve essere infatti maggiore (sia ad esempio ''b''): a questo punto ''b'' - ''c'' è un numero minore di ''b'' (e quindi strettamente minore di ''n'') ma diverso da 0 (essendo ''b'' e ''c'' diversi). Quindi ''b'' - ''c'', essendo minore di ''n'' e maggiore di 0, non può essere divisibile per ''n'', ovvero ''b'' e ''c'' non sono in relazione tra loro.

Ora, dato un qualsiasi intero ''a'', lo si può scrivere, grazie alla divisione euclidea, come
:<math>a=qn+b</math>
dove ''b'' è compreso tra 0 e ''n'' -1. Di conseguenza, ''a'' e ''b'' sono congrui modulo ''n''. Per quanto abbiamo dimostrato prima, ''a'' non può essere anche congruo ad un altro numero ''c'' compreso tra 0 e ''n'' -1, perché altrimenti ''b'' e ''c'' sarebbero in relazione tra loro (per la proprietà transitiva). Quindi, dato un intero ''a'', esiste ed è unico un ''b'' compreso tra 0 e ''n'' -1 a cui è congruo.

A questo punto è possibile passare all'insieme quoziente della relazione sull'insieme <math>\mathbb{Z}</math>, ovvero creare un nuovo insieme (che denoteremo sinteticamente con <math>\mathbb{Z}_n</math>, al posto del più chiaro <math>\mathbb{Z}/_{n \mathbb{Z}}</math>) i cui elementi saranno le classi di equivalenza della relazione<math>\equiv_n</math>. In base ai risultati precedenti, possiamo considerare questo insieme come costituito dalle classi degli elementi 0, 1, 2, ..., ''n'' -1, ovvero
:<math>\mathbb{Z}_n=\{[0]_n, [1]_n, [2]_n, \ldots, [n-1]_n\}</math>
dove i pedici possono essere omessi quando è chiaro senza possibilità d'equivoco di quale modulo stiamo parlando.

A volte è conveniente usare i valori -1, -2, e così via, al posto di ''n'' - 1, ''n'' - 2, eccetera. In questo senso, è possibile anche parlare di modulo:
:<math>|a| \mod n=\begin{cases}a & \text{se}~a\leq n/2\\ n-a & \text{se}~a>n/2\end{cases}</math>

== Le operazioni ==
È naturale a questo punto chiedersi che rapporto abbia la relazione di congruenza con le usuali operazioni tra interi, ovvero l'addizione (e quindi la sottrazione) e la moltiplicazione (non la divisione, perché questa non può generalmente essere compiuta tra due interi).

La relazione di congruenza è ''compatibile'' con l'addizione e la moltiplicazione nel senso seguente: dati due numeri ''a'' e ''b'', si ha che la classe di equivalenza cui appartiene la somma (rispettivamente il prodotto) non cambia se si variano i rappresentanti delle classi di equivalenza.

Infatti, siano ''a''<nowiki>'</nowiki> e ''b''<nowiki>'</nowiki> due interi rispettivamente nelle classi di equivalenza di ''a'' e di ''b'', ovvero tali che
:<math>a'=a+kn \mathrm{~~~e~~~} b'=b+jn</math>
Si ha allora
:<math>a'+b'=a+kn+b+jn=(a+b)+(k+j)n</math>
ovvero ''a''<nowiki>'</nowiki> + ''b''<nowiki>'</nowiki> è nella stessa classe di ''a'' + ''b''.

Lo stesso può essere fatto con la sottrazione e la moltiplicazione, così come con l'elevamento a potenza: questo significa che è possibile indicare le classi di equivalenza come semplici numeri (alleggerendo la notazione), senza incorrere in errori pratici.

Queste operazioni conservano tutte le proprietà che avevano tra gli interi: in particolare l'addizione e la moltiplicazione sono commutative e associative, e la moltiplicazione è distributiva rispetto all'addizione. L'elemento neutro dell'addizione è la classe 0 (ovvero la classe dei multipli di ''n''), mentre quello della moltiplicazione è la classe 1. Queste proprietà fanno sì che l'insieme <math>\mathbb{Z}_n</math> sia un ''anello commutativo unitario'' rispetto a queste operazioni.

Un'altra proprietà invece ''non'' si conserva passando a questo nuovo insieme: non vale la ''legge di annullamento del prodotto'', ovvero non sempre il prodotto di due elementi non nulli è ancora diverso da 0. Ad esempio, se ''n'' =8, 2 e 4 sono chiaramente diversi da 0, ma
:<math>2\cdot 4\equiv 8\mod 8\equiv 0\mod 8</math>

È facile dimostrare che questo può avvenire se e solo se ''n'' non è un numero primo: se infatti ''n'' = ''ab'', allora il prodotto di ''a'' e ''b'' è congruo a 0, ma entrambi i fattori non sono nulli. Se invece ''n'' è primo, e <math>ab\equiv 0\mod n</math>, allora ''n''|''ab''. Per il lemma di Euclide, allora, ''n'' deve dividere o ''a'' o ''b'', ovvero almeno uno dei due deve essere congruo a 0 modulo ''n''. Detto in altri termini, poiché in <math>\mathbb{Z}</math> ogni numero ha una sola fattorizzazione, ''n'' deve essere presente o nella fattorizzazione di ''a'' o in quella di ''b'', perché altrimenti non potrebbe essere presente nella fattorizzazione di ''ab''.

== La divisione ==
Eseguire la divisione tra ''a'' e ''b'' significa trovare un ''k'' tale che ''a'' = ''kb'', oppure moltiplicare ''a'' per l'inverso di ''b'', ovvero quel numero che moltiplicato per ''b'' dà l'elemento neutro della moltiplicazione. In <math>\mathbb{Z}_n</math> tale elemento è 1: trovare l'inverso ''x'' di un elemento ''a'' equivale dunque a risolvere la congruenza
:<math>ax\equiv 1\mod n</math>
ovvero a trovare ''x'' e ''b'' tali che
:<math>ax=1+bn \mathrm{~~~ovvero~~~} ax-bn=1</math>

Attraverso l'algoritmo euclideo è possibile dimostrare che questa congruenza è risolubile se e solo se il massimo comun divisore tra ''a'' e ''n'' è 1 (cioè se ''a'' e ''n'' sono ''coprimi''). In tal caso, anche ''x'' sarà coprimo con ''n''. Quindi ''a'' e ''x'' sono uno l'inverso dell'altro. ''x'' viene spesso denotato con <math>a^{-1}</math>. 

Se indichiamo con <math>\mathbb{Z}_n^*</math> l'insieme degli elementi che possiedono un inverso (ovvero degli elementi ''invertibili'') otteniamo che questi verificano senza sforzo gli assiomi di gruppo rispetto alla moltiplicazione: infatti essa è
*associativa: come in <math>\mathbb{Z}_n</math>;
*possiede elemento neutro: 1 ha come inverso sé stesso, e quindi appartiene a <math>\mathbb{Z}_n^*</math>;
*ogni elemento ha un inverso: ovvio per come abbiamo definito l'insieme.
In più la moltiplicazione è commutativa, e quindi l'insieme <math>\mathbb{Z}_n^*</math> è un gruppo abeliano.

0, ovviamente, non ha mai un inverso; se invece ''n'' è un numero primo, ogni elemento non nullo possiede un inverso, e quindi è invertibile. Di conseguenza, per ''n'' primo, l'insieme <math>\mathbb{Z}_n^*</math> coincide con <math>\mathbb{Z}_n\setminus\{0\}</math> (cioè la divisione ha sempre senso, eccetto quella per 0). Poiché <math>\mathbb{Z}_n</math> era già un anello commutativo, in questo caso abbiamo una struttura molto più potente, e cioè quella di ''campo''. Non solo: è possibile dimostrare, con strumenti molto più sofisticati, che ogni campo con un numero finito di elementi è o un <math>\mathbb{Z}_n</math>, per ''n'' primo, o una sua estensione. Se invece ''n'' non è primo, in generale l'insieme degli invertibili sarà decisamente più piccolo di <math>\mathbb{Z}_n</math>.

La cardinalità dell'insieme <math>\mathbb{Z}_n^*</math> è generalmente denotata con <math>\phi(n)</math>: tale funzione è detta ''funzione phi'' o ''funzione di Eulero''.

La moltiplicazione tra ''a'' e <math>b^{-1}</math> può anche essere denotata come frazione, cioè
:<math>ab^{-1}=\frac{a}{b}</math>
Con questa notazione, possiamo dire che le frazioni "hanno senso" in aritmetica modulare, purché ''b'' sia coprimo con ''n''.

[[categoria:Aritmetica modulare]]
{{Avanzamento|100%|29 giugno 2008}}