Lezione 8 (28 marzo 2000 h. 11-13)

   
Somma e prodotto di classi di congruenza

Proposizione 8.1   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 8.2   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 7.7 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 7.7 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 8.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 8.3   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}}$$

   
equazioni lineari modulo n

Proposizione 8.4   Siano $a,b\in\mathbb Z$, allora esiste un intero x tale che

$$a x \cong b \quad{\rm mod}\ n$$

se e solo se $(a,n)\mathrel{\big\vert}b$.

Dimostrazione.  Se $a x \cong b \quad{\rm mod}\ n$ allora $n\mathrel{\big\vert}(ax-b)$ quindi esiste k tale che ax-b=kn ossia b=ax-kn e quindi $(a,n)\mathrel{\big\vert}b$.

Viceversa supponiamo che $(a,n)\mathrel{\big\vert}b$. Siano $\alpha,\beta$ tali che $(a,n)=\alpha a +\beta n$, e sia k tale che b = k(a,n) allora $b = k(\alpha a +\beta n)$ e quindi $n\mathrel{\big\vert}(a (k\alpha) -b)$, ossia $k\alpha$ è una soluzione della congruenza.     $\square$

Osservazione 8.5   La dimostrazione precedente dà un metodo operativo per trovare una soluzione della congruenza, basta usare l'algoritmo di Euclide per determINARE $\alpha$ e $\beta$ in modo che $(a,n)=\alpha a +\beta n$.

Esercizio 8.2    Si provi che quando ha soluzione, la congruenza $a x \cong b \quad{\rm mod}\ n$ è equivalente alla congruenza

$$a' x \cong b' \quad{\rm mod}\ n'$$

essendo a'=a/(a,n), b'=b/(a,n), n'=n/(a,n).
Soluzione

   
Il teorema cinese del resto

Teorema 8.6 (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)\mathrel{\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 (i.e. le soluzioni sono tutte e sole della forma c+k[n,m] al variare di $k\in\mathbb Z$).

Dimostrazione.  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)\mathrel{\big\vert}n$ e $(n,m)\mathrel{\big\vert}m$ si ha che $(n,m)\mathrel{\big\vert}a-b$. Viceversa, supponiamo che $(n,m)\mathrel{\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... ...'m=(k-k')m &\Rightarrow&m\mathrel{\big\vert}(c-c') \end{array}$$

Ma allora $[n,m]\mathrel{\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$

Esercizio 8.3    Siano $n_1,\dots,n_k$ interi a due a due primi tra loro. Si provi che il sistema di congruenze

$$\left\{\begin{array}{rcll} x & \cong & a_1 & \quad{\rm mod}\... ...\ x & \cong & a_k & \quad{\rm mod}\ n_k \end{array}\right.$$

ammette soluzione e che se c è una soluzione, tutte le altre sono del tipo $c + k n_1\cdot\dots\cdot n_k]$.
Soluzione

Esercizio 8.4    Siano $\varepsilon_0,\varepsilon_1,\dots,\varepsilon_k$ le cifre della espressione decimale del numero n. Si provi che

1.

$3\mathrel{\big\vert}n \iff 3\mathrel{\big\vert}(\varepsilon_0+\varepsilon_1+\dots+\varepsilon_k)$

2.

$9\mathrel{\big\vert}n \iff 9\mathrel{\big\vert}(\varepsilon_0+\varepsilon_1+\dots+\varepsilon_k)$

3.

$11\mathrel{\big\vert}n \iff 11\mathrel{\big\vert}(\varepsilon_0-\varepsilon_1+\dots+(-1)^k\varepsilon_k)$

Soluzione