Lezione 11 (29 marzo 2001 h. 10.30-11.30)

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 \hbox{\rm { 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}} {{}_{\!\tex... ...criptscriptstyle {}\sim}}=\{\left[x\right]_\sim \mid x\in X\}.$$

Proposizione 11.7  

Proposizione 11.8   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$

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}} {{}_{\!\textsty... ...scriptstyle {}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... ...sts\,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}} {{}_{\!\textsty... ...} {{}_{\!\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.8 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}} {{}_{\!\textsty... ...} {{}_{\!\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²=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

$$\begin{eqnarray*}\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 \end{eqnarray*}$$

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[... ...thbb Z}} {{}_{\!\scriptscriptstyle {}6\mathbb Z}} \end{array}$$

per indicare lo stesso concetto.

Esercizio 11.1      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 \hbox{\rm { in }} \mathbb Z\big/\mathchoice {{... ...tyle {}6\mathbb Z}} {{}_{\!\scriptscriptstyle {}6\mathbb Z}}$$

2.

Se n>0 allora

$$\underbrace{1+1+\dots + 1}_{n-\hbox{\rm {volte}}} = 0 \hbox{\... ...tyle {}n\mathbb Z}} {{}_{\!\scriptscriptstyle {}n\mathbb Z}}$$