Aritmetica modulare/La relazione di congruenza: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
Riga 10: Riga 10:


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



Versione delle 12:18, 12 lug 2013

Indice del libro

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

  • è riflessiva:
Errore del parser (errore di sintassi): {\displaystyle 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}

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

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

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