Aritmetica modulare/La relazione di congruenza

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

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[modifica]

Sia l'insieme dei numeri interi, e n un intero maggiore o uguale a 2. All'interno di definiamo la relazione di congruenza come:

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

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 così definita è una particolare relazione di equivalenza:

  • è riflessiva:
, 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

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

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 , ovvero creare un nuovo insieme (che denoteremo sinteticamente con , al posto del più chiaro ) i cui elementi saranno le classi di equivalenza della relazione. In base ai risultati precedenti, possiamo considerare questo insieme come costituito dalle classi degli elementi 0, 1, 2, ... , n -1, ovvero

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:

Le operazioni[modifica]

È 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

Si ha allora

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

È 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 , 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 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[modifica]

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 tale elemento è 1: trovare l'inverso x di un elemento a equivale dunque a risolvere la congruenza

ovvero a trovare x e b tali che

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 .

Se indichiamo con 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 ;
  • possiede elemento neutro: 1 ha come inverso sé stesso, e quindi appartiene a ;
  • ogni elemento ha un inverso: ovvio per come abbiamo definito l'insieme.

In più la moltiplicazione è commutativa, e quindi l'insieme è 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 coincide con (cioè la divisione ha sempre senso, eccetto quella per 0). Poiché 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 , per n primo, o una sua estensione. Se invece n non è primo, in generale l'insieme degli invertibili sarà decisamente più piccolo di .

La cardinalità dell'insieme è generalmente denotata con : tale funzione è detta funzione phi o funzione di Eulero.

La moltiplicazione tra a e può anche essere denotata come frazione, cioè

Con questa notazione, possiamo dire che le frazioni "hanno senso" in aritmetica modulare, purché b sia coprimo con n.