Lezione 6 (8 marzo 1999 h. 9.30-10.30)

Definizione di congruenza e prime proprietà

Definizione 6.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\big\vert a-b$.

Proposizione 6.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$.

Dim.  1. $n\big\vert0=a-a$ per ogni $n\in\mathbb Z$.

2. Se $n\big\vert a-b$ allora a-b=kn e quindi b-a=(-k)n e quindi $n\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$

Classi di congruenza

Definizione 6.3   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)}} {{}_{\!\textstyle {}(n... ...\scriptscriptstyle {}(n)}}=\big\{\left[a\right]_n\bigm\vert a\in\mathbb Z\big\}$

Osservazione 6.4   $x\cong a\quad{\rm mod}\ n$ se e solo se $n\big\vert(x-a)$ se e solo se esiste $k\in\mathbb Z$ tale che x-a=kn se e solo se esiste $k\in\mathbb Z$ tale che x=a+kn e quindi

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

Proposizione 6.5  

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

Dim.  1. Segue dalla proprietà riflessiva.

2. Se $\left[a\right]_n=\left[b\right]_n$ in particolare $b\in\left[b\right]_n=\left[a\right]_n$ e quindi $a\cong b \quad{\rm mod}\ n$. Viceversa sia $a\cong b \quad{\rm mod}\ n$. Se $x\in \left[a\right]_n$ allora $x\cong a\quad{\rm mod}\ n$; per la proprietà transitiva $x\cong b\quad{\rm mod}\ n$ ossia $x\in\left[b\right]_n$. Analogamente se $x\in\left[b\right]_n$ allora $x\in \left[a\right]_n$ e quindi le due classi coincidono.

3. Se $x\in\left[a\right]_n\cap\left[b\right]_n$ allora $x\cong a\quad{\rm mod}\ n$ e $x\cong b\quad{\rm mod}\ n$, usando le proprietà simmetrica e transitiva si ha allora che $a\cong b \quad{\rm mod}\ n$ e quindi, per la (2), appena dimostrata, $\left[a\right]_n=\left[b\right]_n$.     $\square$

Le classi modulo n sono esattamente n

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

Dim.  a=nq+r quindi $n\big\vert nq=a-r$.     $\square$

Corollario 6.7   $\mathbb Z\big/\mathchoice {{}_{\!\displaystyle {}(n)}} {{}_{\!\textstyle {}(n)}} {{}_{\!\scriptstyle {}(n)}} {{}_{\!\scriptscriptstyle {}(n)}}$ ha esattamente n elementi.

Dim.  Da 6.6 e dalla 2 di 6.5 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\big\vert(k-h)$ e quindi (sempre per la 2 di 6.5) $\left[h\right]_n\ne\left[k\right]_m$.     $\square$

Somma e prodotto di classi di congruenza

Proposizione 6.8   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$.

Dim.  (1). Se $n\big\vert(a-a')$ e $n\big\vert(b-b')$ allora $n\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 6.9   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 6.5 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 6.5 si ha che $\left[a+b\right]_n=\left[a'+b'\right]_n$ e $\left[ab\right]_n=\left[a'b'\right]_n$.

Il Teorema cinese del resto

Teorema 6.10 (teorema cinese del resto)   Il sistema di congruenze

$$\left\{ \begin{array}{rcl} x&\cong &a\quad{\rm mod}\ n \\ x&\cong &b\quad{\rm mod}\ m \end{array}\right.$$

ha soluzione se e solo se $(n,m)\big\vert b-a$. Se c è una soluzione del sistema, allora gli elementi di $\left[c\right]_{[n,m]}$ sono tutte e sole le soluzioni del sistema.

Dim.  Sia c una soluzione del sistema allora esistono $h,k\in\mathbb Z$ tali che c=a+hn=b+km e quindi a-b=km-hn. Ma allora dal fatto che $(n,m)\big\vert n$ e $(n,m)\big\vert m$ si ha che $(n,m)\big\vert a-b$. Viceversa, supponiamo che $(n,m)\big\vert a-b$, allora esistono $h,k\in\mathbb Z$ tali che a-b=hn+km. Ma allora a-hn=b+kn, detto quindi c=a-hn=b+kn, si ha evidentemente che c risolve entrambe le congruenze.

Sia $S=\{x\in\mathbb Z\mid x \hbox{\rm { risolve il sistema}}\}$. Dobbiamo provare che se c è una soluzione allora $S=\left[c\right]_{[n,m]}$.

$S\subseteq\left[c\right]_{[n,m]}$. Sia c' un'altra soluzione, allora c=a+hn=b+km e c'=a+h'n=b+k'm e quindi sottraendo si ha

$$\begin{array}{rclcl} c-c'&=&a+hn-a'-h'n=(h-h')n &\Rightarrow&... ...=&b+km-b'-k'm=(k-k')m &\Rightarrow&m\big\vert(c-c') \end{array}$$

Ma allora $[n,m]\big\vert c-c'$ ossia $c'\cong c\quad{\rm mod}\ [n,m]$ ovvero $c'\in\left[c\right]_{[n,m]}$.

$\left[c\right]_{[n,m]}\subseteq S$. Sia $c'\in\left[c\right]_{[n,m]}$, ovvero c'=c+h[n,m]. Dal fatto che $c\cong a \quad{\rm mod}\ n$ e che $h[n,m]\cong 0\quad{\rm mod}\ n$ segue che $c'=c+h[n,m]\cong a \quad{\rm mod}\ n$. In modo analogo si ha che $c'\cong b\quad{\rm mod}\ m$ e quindi che $c'\in S$.     $\square$