Aritmetica modulare/La relazione di congruenza: differenze tra le versioni
Nuova pagina: 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.... |
(Nessuna differenza)
|
Versione delle 17:31, 20 giu 2008
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 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 è 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
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 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 possiamo denotare con ) 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.
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
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
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.
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 . 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.