Aritmetica modulare/La relazione di congruenza

Questo capitolo tratta le proprietà elementari delle congruenze: la definizione delle relazione 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 possiamo denotare con $\mathbb {Z} _{n}$) 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.