Dato un insieme
si possono generare tante relazioni di equivalenza. Prendiamo un insieme
con un'operazione binaria
e sia
una relazione di equivalenza definita su
.
Definizione (112)
Si dice che
è una congruenza rispetto all'operazione
, o anche che
è compatibile con
, se
, e supponiamo
e
, questo implica necessariamente che
.
Queste relazioni consentono di indurre sull'insieme quoziente un'operazione che ha quasi tutte le proprietà dell'operazione
.
Se
è una congruenza rispetto a
, si induce un'operazione binaria chiamata
sull'insieme quoziente
ponendo per ogni coppia
l'uguaglianza
.
è un'operazione ben definita
, perché
è una congruenza e quindi preso un elemento qualsiasi in
e uno in
, il loro prodotto è associato a quello di altri due elementi presi rispettivamente in
e
, cioè
e
appartengono alla stessa classe di equivalenza, che chiamo
.
Si può esprimere
in termini della proiezione canonica. Si chiama
la proiezione canonica da
a
. Allora si può anche scrivere:
![{\displaystyle [a]_{r}\ast [b]_{r}=\pi _{r}(a)\ast \pi _{r}(b)=\pi ([a\ast b]_{r})=\pi _{R}(a\ast b)}](//restbase.wikitolearn.org/it.wikitolearn.org/v1/media/math/render/svg/d465a42d5d1e7cac5c772b08a531a4fa025d5f74)
(la proiezione canonica conserva il prodotto).

in queste condizioni è un morfismo.
L'operazione indotta sul quoziente eredita alcune proprietà di
. Le proprietà di
esreditate da
sono:
- le proprietà di tipo equazionale (commutativa o associativa);
- Se
ammette unità sinistra
o unità destra
o unità bilatera
, allora le immagini mediante la proiezione canonica che contengono
funzionano da unità rispetto all'operazione indotta e si denotano con
.
- Infine, se
e
ammette unità
, e
ammette inverso sinistro
e inverso destro
o inverso bilatero
, ispetto a
, allora l'immagine
ammette rispettivamente inverso sinistro
, inverso destro
e inverso bilatero
rispetto all'unità
.
Proposizione (116)
[Proprietà di annullamento del prodotto] Il prodotto di due interi
è diverso da
.
Prese due matrici elementari, due matrici non nulle possono avere prodotto
.
Se questa proprietà vale per
, può non valere per l'operazione indotta.
Definizione (117)
Sia
un fissato intero
. Due interi
e
si dicono congrui modulo
se la differenza
è divisibile per
, cioè se
, ovvero esiste
tale che sia
è esprimibile come
.
Allora questa relazione su
si dice congruenza modulo
e se
e
sono congrui mod n fra loro, scriviamo
(uguale con tre lineette).
Per
,
se e solo se
e la relazione sarebbe l'identità.
Esempio (119)
Se
,
per ogni
, ottengo la relazione universale, tutti gli interi sono nella stessa classe.
Esempio (120)
Presi i numeri relativi, si otengono le stesse classi di equivalenza che avevo ottenuto con i numeri positivi. Per questo si sceglie
.
Esempio (121)
La relazione di equivalenza modulo
consiste delle classi dei pari e dei dispari.
Esempio (122)
Per
, allora le classi sono
.
Si possono definire una somma e un prodotto di classi, tali che
, e
.
Se considero ad esempio
, perché
, si verifica che la proprietà dell'annullamento del prodotto non si eredita nel quoziente.
Congruenza modulo n come relazione di equivalenza[modifica | modifica wikitesto]
Nell'insieme
degli interi relativi, fissato un intero positivo maggiore di
si può dare la definizione di congruenza modulo
:
è congruo a
modulo
(
) se
, cioè esiste un intero
tale che
.
Proposizione (123)
La relazione di congruenza è di equivalenza su
e l'insieme quoziente è costituito da esattamente
classi, che sono indicate con
. Ogni intero è contenuto in una di queste classi.
Dimostrazione
Dimostro che la relazione è di equivalenza:
- Per ogni
,
se pongo
(riflessiva).
- se
, allora
quindi
, (simmetrica);
- se
e
, allora esiste
per cui
, ed esiste
tale che
. Sommando termine a termine ottengo
, ovvero
(transitiva)
Sia
un intero e mostriamo che la classe che lo contiene è una di quelle indicate. Usiamo l'algoritmo della divisione.
Se
, divido
per
e ottengo un quoziente e un resto, cioè scrivo
, con
.
, quindi la differenza
è divisibile per
e
, cioè la classe che contiene
è quella che contiene il resto. Siccome il resto
può andare da
a
, l'insieme delle classi di equivalenza consiste di
classi.
Dimostriamo che le
classi
sono a due a due distinte. Supponiamo per assurdo che
siano due interi fra
e
, e quindi supponiamo che
. Allora dev'essere
un multiplo di
, ma
, la differenza
è strettamente compresa tra
e
.
è un multiplo di
se e solo se
. Quindi
se e solo se coincidono, quindi l'insieme quoziente consiste esattamente di
classi.
Definizione (124)
L'insieme quoziente rispetto alla relazione di congruenza modulo
si denota con
e prende il nome di insieme delle
classi di resti modulo
.
Esempio (125)
Se
, l'insieme quoziente di
consiste di due classi
, dove
è la classe dei numeri pari e
è quella dei numeri dispari.
Esempio (126)
Se
ho tre oggetti:
costituita dai multipli di
,
,
.
Per ogni fissato modulo
, la relazione di congruenza modulo
è compatibile sia rispetto all'operazione di somma ordinaria, che rispetto a quella di prodotto fra interi.
Supponiamo che
e
. Se la relazione è compatibile rispetto alla somma, allora
.
Infatti, se
esiste un intero
tale che
. Invece
significa che esiste un intero
tale che
. Se
sommo le uguaglianze termine a termine,
, cioè
perché i due numeri differiscono di un intero multiplo di
.
Considerando la compatibilità rispetto al prodotto,
. quindi
e
differiscono per un multiplo di
.
Pertanto la somma e il prodotto tra gli interi inducono sull'insieme quoziente
due operazioni ben definite, che chiameremo somma e prodotto, tali che:
![{\displaystyle {\hbox{somma}}=[a]_{n}+[b]_{n}=[a+b]_{n}}](//restbase.wikitolearn.org/it.wikitolearn.org/v1/media/math/render/svg/42a5df73bc71ef5e40e4eaa72752f1e1a60205b3)
![{\displaystyle {\hbox{prodotto}}=[a]_{n}*[b]_{n}=[ab]_{n}}](//restbase.wikitolearn.org/it.wikitolearn.org/v1/media/math/render/svg/85d66a8749b14b6b4dfa95aad74ce4308e636983)
Le operazioni sono ben definite perché non dipendono dalla scelta dei rappresentanti della classe di equivalenza.
Dati due interi
e un'incognita
, ci si chiede quando l'equazione
ha soluzioni intere.
Le congruenze lineari servono anche per risolvere le equazioni diofantee, della forma
, di cui si vuole capire quando le coppie
sono soluzioni intere.
Siccome l'insieme quoziente per ogni
fissato è finito, allora si possono scrivere le tavole di composizione di queste operazioni.
Queste tavole sono matrici
e permettono di evidenziare alcune proprietà.
La commutatività si vede dal fatto che la tavola è simmetrica. Non si riesce a vedere l'associatività.
Esempio (127)
Esempio di tavola della somma: scrivo sulla prima riga e sulla prima colonna le classi di equivalenza in ordine, poi nelle celle faccio le operazioni tra le classi di equivalenza (ad esempio
, perché mi sto riferendo alle classi di equivalenza e
). Nella cella
escluse la prima riga e la prima colonna, ad esempio c'è l'operazione
.
Ad esempio, se
.

Tavola del prodotto:

Dal fatto che nella tavola della somma la prima riga e la prima colonna rimangono invariate si capisce che l'operazione ha un elemento neutro.
Dal fatto che nella tavola del prodotto c'è una riga e una colonna di 0 si capisce che l'operazione ha un elemento annullatore.
Il prodotto di due classi di equivalenza diverse da 0 può essere 0.