# Aritmetica modulare/La relazione di congruenza

Aritmetica modulare
Copertina Bibliografia Tutti i moduli · Sviluppo
    CopertinaAritmetica modulare/Copertina
* La relazione di congruenzaAritmetica modulare/La relazione di congruenza
* Prime proprietà e applicazioniAritmetica modulare/Prime proprietà e applicazioni
* Congruenze lineariAritmetica modulare/Congruenze lineari
* Polinomi in aritmetica modulareAritmetica modulare/Polinomi in aritmetica modulare
* Radici primitiveAritmetica modulare/Radici primitive
* Congruenze quadraticheAritmetica modulare/Congruenze quadratiche
* Alcune applicazioniAritmetica modulare/Alcune applicazioni
* BibliografiaAritmetica modulare/Bibliografia
* EserciziAritmetica modulare/Esercizi
Modifica il sommario
chiudi indice
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 $\mathbb {Z}$ l'insieme dei numeri interi, e n un intero maggiore o uguale a 2. All'interno di $\mathbb {Z}$ definiamo la relazione di congruenza $\equiv _{n}$ come:
    $a\equiv _{n}b\iff n|(a-b)$
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
    $a\equiv b\mod n$
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 $\equiv _{n}$ così definita è una particolare relazione di equivalenza:
* è riflessiva:
    $a-a=0$, 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
    $a-c=a-b+b-c=kn+jn=(k+j)n$
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
    $a=qn+b$
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 $\mathbb {Z}$, ovvero creare un nuovo insieme (che denoteremo sinteticamente con $\mathbb {Z} _{n}$, al posto del più chiaro $\mathbb {Z} /_{n\mathbb {Z} }$) i cui elementi saranno le classi di equivalenza della relazione$\equiv _{n}$. In base ai risultati precedenti, possiamo considerare questo insieme come costituito dalle classi degli elementi 0, 1, 2, ..., n -1, ovvero
    $\mathbb {Z} _{n}=\{[0]_{n},[1]_{n},[2]_{n},\ldots ,[n-1]_{n}\}$
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:
    $|a|\mod n={\begin{cases}a&{\text{se}}~a\leq n/2\\n-a&{\text{se}}~a>n/2\end{cases}}$

## 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' e b' due interi rispettivamente nelle classi di equivalenza di a e di b, ovvero tali che
    $a'=a+kn\mathrm {~~~e~~~} b'=b+jn$
Si ha allora
    $a'+b'=a+kn+b+jn=(a+b)+(k+j)n$
ovvero a' + b' è 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 $\mathbb {Z} _{n}$ 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
    $2\cdot 4\equiv 8\mod 8\equiv 0\mod 8$
È 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 $ab\equiv 0\mod n$, 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 $\mathbb {Z}$ 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 $\mathbb {Z} _{n}$ tale elemento è 1: trovare l'inverso x di un elemento a equivale dunque a risolvere la congruenza
    $ax\equiv 1\mod n$
ovvero a trovare x e b tali che
    $ax=1+bn\mathrm {~~~ovvero~~~} ax-bn=1$
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 $a^{-1}$.
Se indichiamo con $\mathbb {Z} _{n}^{*}$ 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 $\mathbb {Z} _{n}$;
* possiede elemento neutro: 1 ha come inverso sé stesso, e quindi appartiene a $\mathbb {Z} _{n}^{*}$;
* ogni elemento ha un inverso: ovvio per come abbiamo definito l'insieme.
In più la moltiplicazione è commutativa, e quindi l'insieme $\mathbb {Z} _{n}^{*}$ è 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 $\mathbb {Z} _{n}^{*}$ coincide con $\mathbb {Z} _{n}\setminus \{0\}$ (cioè la divisione ha sempre senso, eccetto quella per 0). Poiché $\mathbb {Z} _{n}$ 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 $\mathbb {Z} _{n}$, per n primo, o una sua estensione. Se invece n non è primo, in generale l'insieme degli invertibili sarà decisamente più piccolo di $\mathbb {Z} _{n}$.
La cardinalità dell'insieme $\mathbb {Z} _{n}^{*}$ è generalmente denotata con $\phi (n)$: tale funzione è detta funzione phi o funzione di Eulero.
La moltiplicazione tra a e $b^{-1}$ può anche essere denotata come frazione, cioè
    $ab^{-1}={\frac {a}{b}}$
Con questa notazione, possiamo dire che le frazioni "hanno senso" in aritmetica modulare, purché b sia coprimo con n.