Congruenze

Definizione

Dato un insieme $X$$X$ si possono generare tante relazioni di equivalenza. Prendiamo un insieme $X$$X$ con un'operazione binaria $\ast$$\ast$ e sia $R$$R$ una relazione di equivalenza definita su $X$$X$.

Definizione (112)

Si dice che $R$$R$ è una congruenza rispetto all'operazione $\ast$$\ast$, o anche che $R$$R$ è compatibile con $\ast$$\ast$, se $\forall a,b,a',b'\in X$$\forall a,b,a',b'\in X$, e supponiamo $aRa'$$aRa'$ e $bRb'$$bRb'$, questo implica necessariamente che $(a\ast b)R(a'\ast b')$$(a\ast b)R(a'\ast b')$.

 

Queste relazioni consentono di indurre sull'insieme quoziente un'operazione che ha quasi tutte le proprietà dell'operazione $\ast$$\ast$.

Osservazione (113)

Se $R$$R$ è una congruenza rispetto a $\ast$$\ast$, si induce un'operazione binaria chiamata $\ast _{R}$$\ast _{R}$ sull'insieme quoziente $X/R$$X/R$ ponendo per ogni coppia $([a]_{r},[b]_{r})\in X/R$$([a]_{r},[b]_{r})\in X/R$ l'uguaglianza $[a_{r}]\ast _{r}[b]_{r}=[a\ast b]_{r}$$[a_{r}]\ast _{r}[b]_{r}=[a\ast b]_{r}$.

 

$\ast _{R}$$\ast _{R}$ è un'operazione ben definita $\colon X/R\times X/R\to X/R$$\colon X/R\times X/R\to X/R$, perché $R$$R$ è una congruenza e quindi preso un elemento qualsiasi in $[a]_{R}$$[a]_{R}$ e uno in $[b]_{r}$$[b]_{r}$, il loro prodotto è associato a quello di altri due elementi presi rispettivamente in $[a]_{R}$$[a]_{R}$ e $[b]_{r}$$[b]_{r}$, cioè $a'\ast b'$$a'\ast b'$ e $a\ast b$$a\ast b$ appartengono alla stessa classe di equivalenza, che chiamo $[a\ast b]_{R}$$[a\ast b]_{R}$.

Osservazione (114)

Si può esprimere $\ast _{R}$$\ast _{R}$ in termini della proiezione canonica. Si chiama $\pi _{r}$$\pi _{r}$ la proiezione canonica da $X$$X$ a $X/R$$X/R$. Allora si può anche scrivere:

$$[a]_{r}\ast [b]_{r}=\pi _{r}(a)\ast \pi _{r}(b)=\pi ([a\ast b]_{r})=\pi _{R}(a\ast b)$$

$$[a]_{r}\ast [b]_{r}=\pi _{r}(a)\ast \pi _{r}(b)=\pi ([a\ast b]_{r})=\pi _{R}(a\ast b)$$

(la proiezione canonica conserva il prodotto). $\pi _{r}$$\pi _{r}$ in queste condizioni è un morfismo.

 

Osservazione (115)

L'operazione indotta sul quoziente eredita alcune proprietà di $\ast$$\ast$. Le proprietà di $\ast _{R}$$\ast _{R}$ esreditate da $\ast$$\ast$ sono:

1. le proprietà di tipo equazionale (commutativa o associativa);
2. Se $\ast$$\ast$ ammette unità sinistra $u_{s}$$u_{s}$ o unità destra $u_{d}$$u_{d}$ o unità bilatera $u$$u$, allora le immagini mediante la proiezione canonica che contengono $u_{s},u_{d},u$$u_{s},u_{d},u$ funzionano da unità rispetto all'operazione indotta e si denotano con $[u_{s}],[u_{d}],[u]$$[u_{s}],[u_{d}],[u]$.
3. Infine, se $x\in X$$x \in X$ e $\ast$$\ast$ ammette unità $u$$u$, e $x\in X$$x \in X$ ammette inverso sinistro ${\bar {x}}_{s}$${\bar {x}}_{s}$ e inverso destro ${\bar {x}}_{d}$${\bar {x}}_{d}$ o inverso bilatero ${\bar {x}}$$\bar x$, ispetto a $\ast$$\ast$, allora l'immagine $[x]_{R}$$[x]_{R}$ ammette rispettivamente inverso sinistro $[{\bar {x}}_{s}]_{r}$$[{\bar {x}}_{s}]_{r}$, inverso destro $[{\bar {x}}_{d}]_{r}$$[{\bar {x}}_{d}]_{r}$ e inverso bilatero $[{\bar {x}}]$$[{\bar {x}}]$ rispetto all'unità $u$$u$.

 

Proposizione (116)

[Proprietà di annullamento del prodotto] Il prodotto di due interi $m,n\neq 0$$m,n\neq 0$ è diverso da $0$$0$.

 

Prese due matrici elementari, due matrici non nulle possono avere prodotto $0$$0$.

Se questa proprietà vale per $(X,\ast )$$(X,\ast )$, può non valere per l'operazione indotta.

Relazione di congruenza in Z

Definizione (117)

Sia $n$$n$ un fissato intero $\geq 1$$\geq 1$. Due interi $a$$a$ e $b$$b$ si dicono congrui modulo $n$$n$ se la differenza $a-b$$a-b$ è divisibile per $n$$n$, cioè se $n\mid a-b$$n\mid a-b$, ovvero esiste $h$$h$ tale che sia $a-b$$a-b$ è esprimibile come $h*n$$h*n$. Allora questa relazione su $\mathbb {Z}$$\mathbb {Z}$ si dice congruenza modulo $n$$n$ e se $a$$a$ e $b\in \mathbb {Z}$$b\in \mathbb {Z}$ sono congrui mod n fra loro, scriviamo $a\equiv b\mod n$$a\equiv b\mod n$ (uguale con tre lineette).

 

Osservazione (118)

Per $n=0$$n=0$, $a\equiv b\mod n$$a\equiv b\mod n$ se e solo se $a=b$$a=b$ e la relazione sarebbe l'identità.

 

Esempio (119)

Se $n=1$$n=1$, $a\equiv b\mod n$$a\equiv b\mod n$ per ogni $b$$b$, 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 $n>1$$n>1$.

 

Esempio (121)

La relazione di equivalenza modulo $2$$2$ consiste delle classi dei pari e dei dispari.

 

Esempio (122)

Per $n=6$$n=6$, allora le classi sono $[0],[1],[2],[3],[4],[5]$$[0],[1],[2],[3],[4],[5]$.

 

Si possono definire una somma e un prodotto di classi, tali che $[a]+[b]=[a+b]$$[a]+[b]=[a+b]$, e $[a]*[b]=[ab]$$[a]*[b]=[ab]$.

Se considero ad esempio $[2]*[3]=[6]=[0]$$[2]*[3]=[6]=[0]$, perché $6-0/6$$6-0/6$, si verifica che la proprietà dell'annullamento del prodotto non si eredita nel quoziente.

Congruenza modulo n come relazione di equivalenza

Nell'insieme $\mathbb {Z}$$\mathbb {Z}$ degli interi relativi, fissato un intero positivo maggiore di $1$$1$ si può dare la definizione di congruenza modulo $n$$n$: $a$$a$ è congruo a $b$$b$ modulo $n$$n$ ($a\equiv b\mod n$$a\equiv b\mod n$) se $n\mid a-b$$n\mid a-b$, cioè esiste un intero $h$$h$ tale che $a-b=hn$$a-b=hn$.

Proposizione (123)

La relazione di congruenza è di equivalenza su $\mathbb {Z}$$\mathbb {Z}$ e l'insieme quoziente è costituito da esattamente $n$$n$ classi, che sono indicate con $[0]_{n},[1]_{n},\dots ,[n-1]_{n}$$[0]_{n},[1]_{n},\dots ,[n-1]_{n}$. Ogni intero è contenuto in una di queste classi.

 

Dimostrazione

Dimostro che la relazione è di equivalenza:

1. Per ogni $a\in \mathbb {Z}$$a\in \mathbb {Z}$, $a\equiv a\mod n$$a\equiv a\mod n$ se pongo $h=0$$h=0$ (riflessiva).
2. se $a\equiv b\mod n$$a\equiv b\mod n$, allora $a-b=h*n,\,h\in \mathbb {Z}$$a-b=h*n,\,h\in \mathbb {Z}$ quindi $b-a=-h*n$$b-a=-h*n$, (simmetrica);
3. se $a\equiv b\mod n$$a\equiv b\mod n$ e $b\equiv c\mod n$$b\equiv c\mod n$, allora esiste $h$$h$ per cui $a-b=h*n$$a-b=h*n$, ed esiste $k$$k$ tale che $b-c=kn$$b-c=kn$. Sommando termine a termine ottengo $a-b+b-c=a-c=(h+k)*n$$a-b+b-c=a-c=(h+k)*n$, ovvero $a\equiv c\mod n$$a\equiv c\mod n$ (transitiva)

Sia $a$$a$ un intero e mostriamo che la classe che lo contiene è una di quelle indicate. Usiamo l'algoritmo della divisione.

Se $a>n$$a>n$, divido $a$$a$ per $n$$n$ e ottengo un quoziente e un resto, cioè scrivo $a=q*n+r$$a=q*n+r$, con $r\geq 0,\,r<n$$r\geq 0,\,r<n$. $a-r=q*n$$a-r=q*n$, quindi la differenza $a-r$$a-r$ è divisibile per $n$$n$ e $a\equiv r\mod n$$a\equiv r\mod n$, cioè la classe che contiene $a$$a$ è quella che contiene il resto. Siccome il resto può andare da $0$$0$ a $n-1$$n-1$, l'insieme delle classi di equivalenza consiste di $n$$n$ classi.

Dimostriamo che le $n$$n$ classi $[0]_{n},[1]_{n},[n-1]_{n}$$[0]_{n},[1]_{n},[n-1]_{n}$ sono a due a due distinte. Supponiamo per assurdo che $j_{1},j_{2}$$j_{1},j_{2}$ siano due interi fra $0$$0$ e $n-1$$n-1$, e quindi supponiamo che $[j_{1}]=[j_{2}]$$[j_{1}]=[j_{2}]$. Allora dev'essere $j_{1}-j_{2}$$j_{1}-j_{2}$ un multiplo di $n$$n$, ma $0\leq j_{1}<j_{2}<n$$0\leq j_{1}<j_{2}<n$, la differenza $j_{2}-j_{1}$$j_{2}-j_{1}$ è strettamente compresa tra $0$$0$ e $n$$n$. $j_{2}-j_{1}$$j_{2}-j_{1}$ è un multiplo di $n$$n$ se e solo se $h=0$$h=0$. Quindi $j_{1}\equiv j_{2}\mod n$$j_{1}\equiv j_{2}\mod n$ se e solo se coincidono, quindi l'insieme quoziente consiste esattamente di $n$$n$ classi.

 

Definizione (124)

L'insieme quoziente rispetto alla relazione di congruenza modulo $n$$n$ si denota con $\mathbb {Z} /(n\mathbb {Z} )$$\mathbb {Z} /(n\mathbb {Z} )$ e prende il nome di insieme delle classi di resti modulo $n$$n$.

 

Esempio (125)

Se $n=2$$n=2$, l'insieme quoziente di $\mathbb {Z}$$\mathbb {Z}$ consiste di due classi $[0],[1]$$[0],[1]$, dove $[0]$$[0]$ è la classe dei numeri pari e $[1]=\{2h+1\}$$[1]=\{2h+1\}$ è quella dei numeri dispari.

 

Esempio (126)

Se $n=3$$n=3$ ho tre oggetti: $[0]=\{3h\}$$[0]=\{3h\}$ costituita dai multipli di $3$$3$, $[1]=\{3h+1\}$$[1]=\{3h+1\}$, $[2]=\{3h+2\}$$[2]=\{3h+2\}$.

 

Compatibilità tra congruenza e operazioni

Per ogni fissato modulo $n>1$$n>1$, la relazione di congruenza modulo $n$$n$ è compatibile sia rispetto all'operazione di somma ordinaria, che rispetto a quella di prodotto fra interi.

Supponiamo che $a\equiv a'\mod n$$a\equiv a'\mod n$ e $b\equiv b'\mod n$$b\equiv b'\mod n$. Se la relazione è compatibile rispetto alla somma, allora $a+b\sim a'+b'$$a+b\sim a'+b'$. Infatti, se $a\sim a'$$a\sim a'$ esiste un intero $h$$h$ tale che $a=a'+hn$$a=a'+hn$. Invece $b\sim b'$$b\sim b'$ significa che esiste un intero $k$$k$ tale che $b=b'+kn$$b=b'+kn$. Se sommo le uguaglianze termine a termine, $a+b=a'+hn+b'+kn=a'+b'+(h+k)n$$a+b=a'+hn+b'+kn=a'+b'+(h+k)n$, cioè $a+b\equiv a'+b'\mod n$$a+b\equiv a'+b'\mod n$ perché i due numeri differiscono di un intero multiplo di $n$$n$.

Considerando la compatibilità rispetto al prodotto, $ab=(a'+hn)(b'+kn)=a'b'+(a'k+hb'+khn)*n$$ab=(a'+hn)(b'+kn)=a'b'+(a'k+hb'+khn)*n$. quindi $a'b'$$a'b'$ e $ab$$ab$ differiscono per un multiplo di $n$$n$.

Pertanto la somma e il prodotto tra gli interi inducono sull'insieme quoziente $\mathbb {Z} /(n\mathbb {Z} )$$\mathbb {Z} /(n\mathbb {Z} )$ due operazioni ben definite, che chiameremo somma e prodotto, tali che:

$${\hbox{somma}}=[a]_{n}+[b]_{n}=[a+b]_{n}$$

$${\hbox{somma}}=[a]_{n}+[b]_{n}=[a+b]_{n}$$

$${\hbox{prodotto}}=[a]_{n}*[b]_{n}=[ab]_{n}$$

$${\hbox{prodotto}}=[a]_{n}*[b]_{n}=[ab]_{n}$$

Le operazioni sono ben definite perché non dipendono dalla scelta dei rappresentanti della classe di equivalenza.

Dati due interi $a,b$$a,b$ e un'incognita $x$$x$, ci si chiede quando l'equazione $ax+b$$ax+b$ ha soluzioni intere.

Le congruenze lineari servono anche per risolvere le equazioni diofantee, della forma $ax+by+c=0$$ax+by+c=0$, di cui si vuole capire quando le coppie $x,y$$x,y$ sono soluzioni intere.

Tavole di composizione

Siccome l'insieme quoziente per ogni $n$$n$ fissato è finito, allora si possono scrivere le tavole di composizione di queste operazioni.

Queste tavole sono matrici $nxn$$nxn$ 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 $2+4=0$$2+4=0$, perché mi sto riferendo alle classi di equivalenza e $[0]=[6]$$[0]=[6]$). Nella cella $a_{23}$$a_{23}$ escluse la prima riga e la prima colonna, ad esempio c'è l'operazione $[1]+[2]$$[1]+[2]$. Ad esempio, se $n=6$$n=6$.

$${\begin{array}{c|cccccc}&0&1&2&3&4&5\\\hline 0&0&1&2&3&4&5\\1&1&2&3&4&5&0\\2&2&3&4&5&0&1\\3&3&4&5&0&1&2\\4&4&5&0&1&2&3\\5&5&0&1&2&3&4\end{array}}$$

$${\begin{array}{c|cccccc}&0&1&2&3&4&5\\\hline 0&0&1&2&3&4&5\\1&1&2&3&4&5&0\\2&2&3&4&5&0&1\\3&3&4&5&0&1&2\\4&4&5&0&1&2&3\\5&5&0&1&2&3&4\end{array}}$$

Tavola del prodotto:

$${\begin{array}{c|cccccc}&0&1&2&3&4&5\\0&0&0&0&0&0&0\\1&0&1&2&3&4&5\\2&0&2&4&0&2&4\\3&0&3&0&3&0&3\\4&0&4&2&0&4&2\\5&0&5&4&3&2&1\end{array}}$$

$${\begin{array}{c|cccccc}&0&1&2&3&4&5\\0&0&0&0&0&0&0\\1&0&1&2&3&4&5\\2&0&2&4&0&2&4\\3&0&3&0&3&0&3\\4&0&4&2&0&4&2\\5&0&5&4&3&2&1\end{array}}$$

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.