Lezione 11

Definizione di congruenza e prime proprietà

Definizione 11.1   Siano $a,b\in\mathbb{Z}$, si dice che $a$ è congruo a $b$ modulo $n$ (in simboli $a\cong b \quad{\rm mod} n$) se $n\mathrel{\big\vert}a-b$.

Proposizione 11.2   Valgono le seguenti proprietà:

1. (proprietà riflessiva) $a\cong a \quad{\rm mod} n$ per ogni $a,n\in\mathbb{Z}$;
2. (proprietà simmetrica) $a\cong b\quad{\rm mod} n\Rightarrow b\cong a \quad{\rm mod} n$ per ogni $a,b,n\in\mathbb{Z}$;
3. (proprietà transitiva) $a\cong b \quad{\rm mod} n$ e $b\cong c\quad{\rm mod} n\Rightarrow a\cong c\quad{\rm mod} n$ per ogni $a,b,c,n\in\mathbb{Z}$.

Dimostrazione.  1. $n\mathrel{\big\vert}0=a-a$ per ogni $n\in\mathbb{Z}$.

2. Se $n\mathrel{\big\vert}a-b$ allora $a-b=kn$ e quindi $b-a=(-k)n$ e quindi $n\mathrel{\big\vert}b-a$ ossia $b\cong a \quad{\rm mod} n$.

3. Se $a\cong b \quad{\rm mod} n$ e $b\cong c \quad{\rm mod} n$ allora $a-b=kn$ e $b-c=hn$ e quindi $a-c=a-b+b-c=kn+hn=(k+h)n$ e quindi $a\cong c\quad{\rm mod} n$.     $\square$

Ricordiamo la definizione di relazione d'equivalenza su un insieme.

Definizione 11.3   Una relazione ${\cal R}$ su $X$ si dice d'equivalenza se

1. è riflessiva, ossia $\forall x\in X$ $x{\cal R}x$;
2. è simmetrica, ossia $\forall x,y\in X$ $x{\cal R} y\Rightarrow y{\cal R}x$
3. è transitiva, ossia $\forall x,y,z\in X$ $(x{\cal R}y$    e $y{\cal R}z )\Rightarrow x{\cal R}z$.

Osservazione 11.4   È prassi comune denotare le relazioni d'equivalenza con simboli del tipo $\sim$, $\cong$, $\approx$ e simili.

Osservazione 11.5   La proposizione precedente può essere allora rienunciato dicendo che la relazione di congruenza modulo $n$ è una relazione d'equivalenza su $\mathbb{Z}$.

Classi d'equivalenza

Definizione 11.6   Siano $X$ un insieme, $\sim$ una relazione d'equivalenza su $X$ e $x\in X$. Si chiame classe d'equivalenza di $x$ in $X$ rispetto a $\sim$, l'insieme:

$$\left[x\right]_\sim=\{y\in x\mid y\sim x\}.$$

Quando non ci sarà ambiguità, si scriverà semplicemente $\left[x\right]$ invece che $\left[x\right]_\sim$.

L'isieme costituito da tutte le classi d'equivalenza si chiama insieme quoziente di $X$ modulo $\sim$ e si denota con il simbolo $X\big/\mathchoice {{}_{\!\displaystyle {}\sim}} {{}_{\!\textstyle {}\sim}} {{}_{\!\scriptstyle {}\sim}} {{}_{\!\scriptscriptstyle {}\sim}}$, quindi:

$$X\big/\mathchoice {{}_{\!\displaystyle {}\sim}} {{}_{\!\textstyle... ...\sim}} {{}_{\!\scriptscriptstyle {}\sim}}=\{\left[x\right]_\sim \mid x\in X\}.$$

Proposizione 11.7   Sia $X$ un insieme e sia $\sim$ una relazione d'equivalenza su $X$, allora

1. per ogni $x\in X$ $x\in\left[x\right]$
2. per ogni $x,y\in X$ $\left[x\right]=\left[y\right]$ se e solo se $x\sim y$.
3. per ogni $x,y\in X$ $\left[x\right]\cap\left[y\right]\ne\varnothing\Rightarrow \left[x\right]=\left[y\right]$.

Dimostrazione.  1. Segue dalla proprietà riflessiva.

2. Se $\left[x\right]=\left[y\right]$ in particolare $y\in\left[y\right]=\left[x\right]$ e quindi $x\sim y$. Viceversa sia $x\sim y$. Se $z\in \left[x\right]$ allora $z\sim x$; per la proprietà transitiva $z\cong y$ ossia $z\in\left[y\right]$, ossia $\left[x\right]\subseteq \left[y\right]$. Scambiando i ruoli di $x$ e $y$ si ha anche l'inclusione opposta e quindi l'uguaglianza.

3. Se $z\in\left[x\right]\cap\left[y\right]$ allora $z\sim x$ e $z\sim y$, usando le proprietà simmetrica e transitiva si ha allora che $x\sim y$ e quindi, per la (2), appena dimostrata, $\left[x\right]=\left[y\right]$.     $\square$

Osservazione 11.8   Le proprietà (1) e (3) assicurano che l'insieme delle classi d'equivalenza di un insieme rispetto ad una relazione d'equivalenza (il quoziente) costituisce una partizione dell'insieme ossia sono una collezione ${\cal P}$ di sottinsiemi di $X$ (i.e. ${\cal P}\subset2^X$) che hanno le seguenti proprietà:

1. sono tutti non vuoti, ovvero $\forall A \in {\cal P}\quad A\ne\varnothing$ (questo è garantito da (1))
2. ricoprono $X$, ovvero $\bigcup_{A \in {\cal P}} A = X$ (questo è garantito da (1))
3. sono a due a due disgiunti, ovvero $\forall A,B\in{\cal P}\quad A\ne B \Rightarrow A \cap B =\varnothing$ (questo è garantito da (3))

Esercizio 11.1   Sia $X$ un insieme. Si dimostri che gli insiemi

$R=\{{\cal R}\mid{\cal R}$ è una relazione d'equivalenza su $X\}$
$P=\{{\cal P}\mid{\cal P}$ è una partizione di $X\}$

sono in bigezione.
Soluzione

Classi di congruenza

Definizione 11.9   Siano $a,n\in\mathbb{Z}$, si chiama classe di congruenza di $a$ modulo $n$ l'insieme

$$\left[a\right]_n=\{x\in\mathbb{Z}\mid x\cong a\quad{\rm mod} n\}.$$

Indicheremo $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\textst... ...riptstyle {}n\mathbb{Z}}}=\big\{\left[a\right]_n\bigm\vert a\in\mathbb{Z}\big\}$

Osservazione 11.10   Osserviamo che

$$x\cong a\quad{\rm mod} n \iff n\mathrel{\big\vert}(x-a) \iff \exists k\in \mathbb{Z}:x-a=kn \iff \exists k\in \mathbb{Z}:x=a+kn$$

e quindi

$$\left[a\right]_n=\{a +kn\mid k\in \mathbb{Z}\}.$$

Osservazione 11.11   La classe di congruenza di $a$ modulo $n$ non è altro che la classe d'equivalenza di $a$ rispetto alla relazione d'equivalenza $\cong\quad{\rm mod} n$ e $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\textst... ...} {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$ quindi è l'insieme quoziente di $\mathbb{Z}$ rispetto a tale relazione d'equivalenza.

In virtù di questa osservazione e della proposizione 11.7 si ha la seguente:

Proposizione 11.12  

1. per ogni $a\in\mathbb{Z}$ $a\in\left[a\right]_n$
2. per ogni $a,b\in\mathbb{Z}$ $\left[a\right]_n=\left[b\right]_n$ se e solo se $a\cong b \quad{\rm mod} n$.
3. per ogni $a,b\in\mathbb{Z}$ $\left[a\right]_n\cap\left[b\right]_n\ne\varnothing\Rightarrow \left[a\right]_n=\left[b\right]_n$.

Le classi modulo $n$ sono esattamente $n$

Proposizione 11.13   Se $n>0$ e $r$ è il resto della divisione euclidea di $a$ per $n$ allora $a\cong r\quad{\rm mod} n$.

Dimostrazione.  $a=nq+r$ quindi $n\mathrel{\big\vert}nq=a-r$.     $\square$

Corollario 11.14   Se $n>0$ allora $\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}n\mathbb{Z}}} {{}_{\!\textst... ...} {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$ ha esattamente $n$ elementi.

Dimostrazione.  Da 11.13 e dalla 2 di 11.12 segue immediatamente che l'insieme in questione ha al più $n$ elementi e precisamente $\left[0\right]_n,\left[1\right]_n,\dots,\left[n-1\right]_n$. D'altra parte se $0\le h<k<n$ allora $0<k-h<n$ e quindi $n\not\mathrel{\big\vert}(k-h)$ e quindi (sempre per la 2 di 11.12) $\left[h\right]_n\ne\left[k\right]_m$.     $\square$

Osservazione 11.15   La proposizione precedente spiega come mai le classi di congruenza modulo $n$ vengono anche chiamate classi di resto modulo $n$.

Somma e prodotto di classi di congruenza

Proposizione 11.16   Siano $a,b,a',b',n\in\mathbb{Z}$ e si supponga che $a\cong a'\quad{\rm mod} n$ e $b\cong b'\quad{\rm mod} n$. Allora

1. $a+b\cong a'+b'\quad{\rm mod} n$;
2. $ab\cong a'b'\quad{\rm mod} n$.

Dimostrazione.  (1). Se $n\mathrel{\big\vert}(a-a')$ e $n\mathrel{\big\vert}(b-b')$ allora $n\mathrel{\big\vert}((a-a')+(b-b'))=((a+b)-(a'+b'))$.

(2). Esistono $k,h\in\mathbb{Z}$ tali che $a=a'+kn$ e $b=b'+hn$, ma allora, moltiplicando membro a membro si ottiene $ab=a'b'+a'hn+b'kn+hkn^2=a'b'+n(a'h+b'k+hkn)$ e quindi la tesi.     $\square$

Osservazione 11.17   La proposizione precedente permette di definire le operazioni di somma e prodotto tra classi modulo $n$. Ponendo

$$\left[a\right]_n+\left[b\right]_n = \left[a+b\right]_n$$

$$\left[a\right]_n \left[b\right]_n = \left[ab\right]_n$$

si ottengono delle buone definizioni. Infatti se $\left[a\right]_n=\left[a'\right]_n$ e $\left[b\right]_n=\left[b'\right]_n$ allora per la 2 di 11.12 si ha che $a\cong a'\quad{\rm mod} n$ e $b\cong b'\quad{\rm mod} n$ e quindi per la proposizione precedente si ha che $a+a'\cong b+b'\quad{\rm mod} n$ e $aa'\cong bb'\quad{\rm mod} n$ e quindi di nuovo per la 2 di 11.12 si ha che $\left[a+b\right]_n=\left[a'+b'\right]_n$ e $\left[ab\right]_n=\left[a'b'\right]_n$.

Nel seguito, quando parleremo di classi di congruenza e di operazioni tra esse, potrà succedere che, nella notazione, confonderemo la classe con uno dei suoi rappresentanti. Sarà chiaro dal contesto a cosa ci si starà riferendo. Ad esempio useremo indifferentemente una delle tre espressioni

$$\begin{array}{l} 3 + 3 \cong 0 \quad{\rm mod} 6 \\ \left[3\righ... ...riptstyle {}6\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}6\mathbb{Z}}} \end{array}$$

per indicare lo stesso concetto.

Esercizio 11.2   Si provino le seguenti proprietà delle operazioni tra classi di congruenza:

1. $(\left[a\right] + \left[b\right] ) + \left[c\right] = \left[a\right] + ( \left[b\right] + \left[c\right])$
2. $(\left[a\right] \left[b\right] ) \left[c\right] = \left[a\right] ( \left[b\right] \left[c\right])$
3. $\left[a\right] + \left[b\right] = \left[b\right] + \left[a\right]$
4. $\left[a\right] \left[b\right] = \left[b\right] \left[a\right]$
5. $\left[a\right] + \left[0\right] = \left[a\right]$
6. $\left[a\right] + \left[-a\right] = \left[0\right]$
7. $\left[a\right] \left[1\right] = \left[a\right]$
8. $\left[a\right] ( \left[b\right] + \left[c\right]) = ( \left[a\right] \left[b\right] ) + (\left[a\right] \left[c\right])$

Soluzione

Osservazione 11.18   L'esercizio precedente, mostra che le operazioni tra classi di congruenza godono delle stesse proprietà di cui godono le operazioni tra interi. Attenzione però a due importanti differenze:

1. Ci possono essere classi diverse da 0 che moltiplicate tra loro danno 0, ad esempio
   $$2 \cdot 3 = 0$$    in $$\mathbb{Z}\big/\mathchoice {{}_{\!\displaystyle {}6\mathbb{Z}}} {... ... {{}_{\!\scriptstyle {}6\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}6\mathbb{Z}}}$$

2. Se $n>0$ allora
   $$\underbrace{1+1+\dots + 1}_{n-\text{volte}} = 0 \text{ in } \math... ... {{}_{\!\scriptstyle {}n\mathbb{Z}}} {{}_{\!\scriptscriptstyle {}n\mathbb{Z}}}$$