Come anticipato nella lezione precedente, dimostreremo ora che la relazione di congruenza modulo m in Z è compatibile sia con l’operazione di somma che con l’operazione di prodotto fra interi.

Matematica Discreta

Lezione del giorno 26 aprile 2010

Come anticipato nella lezione precedente, dimostreremo ora che la relazione di congruenza modulo m in Z è compatibile sia con l’operazione di somma che con l’operazione di prodotto fra interi.

Compatibilità della congruenza modulo m con la somma: se ac (mod m), e se bd (mod m) allora m è divisore delle differenze a-c, b-d, dunque a-c=mk, b-d=mh (con k,h interi), da cui:

(a+b)-(c+d)=m(h+k)

ossia m è divisore della differenza (a+b)-(c+d) e si conclude che (a+b)(c+d) (mod m);

Compatibilità della congruenza modulo m con il prodotto: con le stesse notazioni, si ha:

(ab)-(cd)=a(b-d)+d(a-c)=m(ah+dk)

ossia m è divisore della differenza (ab)-(cd) e si conclude che (ab)(cd) (mod m).

Come detto nella lezione precedente, la compatibilità di somma e prodotto di interi con la relazione di congruenza modulo m permette di definire 2 operazioni indotte di somma e prodotto di classi nell’insieme Z

:

[a]+[b] = [a+b] [a][b] = [ab]

Esempio.

Consideriamo l’insieme Z

delle 4 classi di congruenza modulo 4:

Z

= {[0],[1],[2],[3]}

Se costruiamo la tavola operazionale della somma fra classi (rispetto all’ordine [0],[1],[2],[3]) otteniamo la seguente matrice 4x4:



 









 







] 2 [ ] 1 [ ] 0 [ ] 3 [

] 1 [ ] 0 [ ] 3 [ ] 2 [

] 0 [ ] 3 [ ] 2 [ ] 1 [

] 3 [ ] 2 [ ] 1 [ ] 0 [

(per calcolare per esempio [2]+[3] si calcola [2+3]=[5]=[1], notando che 1 è il resto della divisione di 5 per il modulo 4, etc….)

Se invece costruiamo la tavola operazionale del prodotto fra classi (rispetto all’ordine [0],[1],[2], [3]) otteniamo la seguente matrice 4x4:



 









 







] 1 [ ] 2 [ ] 3 [ ] 0 [

] 2 [ ] 0 [ ] 2 [ ] 0 [

] 3 [ ] 2 [ ] 1 [ ] 0 [

] 0 [ ] 0 [ ] 0 [ ] 0 [

(per calcolare per esempio [2][3] si calcola [23]=[6]=[2], notando che 2 è il resto della divisione di 6 per il modulo 4, etc….)

Proprietà che si trasmettono da un’operazione all’operazione indotta.

Torniamo al caso generale di un insieme A in cui sono definite sia una relazione di equivalenza R che un’operazione * compatibile con R, in modo che nell’insieme quoziente A/R delle classi di equivalenza sia definita un’operazione indotta * fra le classi.

Notiamo che in tale caso molte proprietà dell’operazione * dell’insieme A si trasmettono all’analoga operazione * dell’insieme delle classi A/R:

1) se l’operazione * in A é associativa, l’operazione indotta * in A/R é anch’essa associativa. Infatti, date 3 classi [a],[b],[c] si ha (sfruttando la proprietà associativa valida in A):

[a]*([b]*[c]) = [a]*[b*c] = [a*(b*c)] = [(a*b)*c] = [a*b]*[c] = ([a]*[b])*[c]

2) se l’operazione * in A é commutativa, l’operazione indotta * in A/R é anch’essa commutativa.

Infatti, date 3 classi [a],[b],[c] si ha (sfruttando la proprietà commutativa valida in A):

[a]*[b] = [a*b] = [b*a] = [b]*[a]

3) se esiste l’elemento neutro eA rispetto all’operazione *, allora esiste anche l’elemento neutro nell’insieme delle classi A/R rispetto all’operazione indotta * ; inoltre tale elemento neutro é la classe [e]. Infatti per ogni classe [a] si ha:

[a]*[e] = [a*e] = [a] ; [e]*[a] = [e*a] = [a]

4) se un elemento aA é simmetrizzabile rispetto all’operazione * con simmetrico a’A, allora la classe [a] é simmetrizzabile nell’insieme delle classi A/R rispetto all’operazione indotta * ed il suo simmetrico é la classe [a’]. Infatti si ha :

[a]*[a’] = [a*a’] = [e] = elemento neutro di A/R; [a’]*[a] = [a’*a] = [e] = elemento neutro di A/R In particolare:

- se A é monoide rispetto all’operazione *, anche A/R é monoide rispetto all’operazione indotta * - se A é gruppo rispetto all’operazione *, anche A/R é gruppo rispetto all’operazione indotta * Inoltre se A è monoide (rispettivamente gruppo) commutativo anche A/R lo é.

Applichiamo le considerazioni precedenti all’insieme Z

delle classi di congruenza modulo m, in cui abbiamo definito le operazioni di somma e prodotto di classi, indotte dalle operazioni di somma e prodotto fra interi.

Vediamo quali proprietà hanno tali operazioni.

Essendo Z un gruppo commutativo rispetto all’operazione di somma (con elemento neutro 0 e con simmetrico di un elemento a uguale all’opposto –a) per le osservazioni precedenti si ottiene che l’insieme Z

delle classi di congruenza modulo m é un gruppo commutativo rispetto all’operazione di somma fra classi (l’elemento neutro sarà [0] e il simmetrico di una classe [a]

sarà la classe [-a]).

Invece essendo Z solo un monoide commutativo rispetto all’operazione di prodotto (con elemento neutro 1) per le osservazioni precedenti si ottiene che l’insieme Z

delle classi di congruenza modulo m é un monoide commutativo rispetto all’operazione di prodotto fra classi (l’elemento neutro sarà [1]).

Per quanto riguarda l’operazione di somma fra classi in Z

, possiamo notare che per calcolare il simmetrico (sempre rispetto alla somma) di una classe [a] scelta fra le classi {[0], [1],..., [m-1]}, vi é una regola pratica molto semplice:

- se [a] = [0], il suo simmetrico é [0] (l’elemento neutro ha come simmetrico sé stesso)

- se [a]  [0] (quindi se a=1,2...,m-1) allora il simmetrico di [a] é la classe [m-a] (infatti sommando [a] con [m-a] si ottiene [a]+[m-a] = [a+m-a] = [m] = [0] = elemento neutro, perché r=0 é il resto della divisione di m per m).

Per esempio in Z

il simmetrico di [48] é [100-48] = [52].

Abbiamo detto che rispetto all’operazione di prodotto di classi, l’insieme Z

é un monoide commutativo (con elemento neutro [1]), perché tale è Z rispetto al prodotto.

Tale monoide Z

non è un gruppo: possiamo infatti notare che [0] non é certamente simmetrizzabile rispetto al prodotto fra classi, in quanto non può esistere il simmetrico di [0], perché il prodotto di [0] per qualunque classe dà come risultato sempre [0] (quindi non si ottiene mai [1] che é l’elemento neutro).

Se esaminiamo per esempio la tavola operazionale del prodotto in Z

(vista in precedenza) si

verifica che gli unici elementi simmetrizzabili sono [1] e [3].

Resta da risolvere un problema generale: nel monoide Z

(rispetto all’operazione di prodotto fra classi) quali sono gli elementi simmetrizzabili e come si calcola il loro simmetrico (cioé il loro inverso) ?

Ricordiamo anche che l’insieme degli elementi simmetrizzabili del monoide Z

é un gruppo (indicato con Z

*) rispetto alla stessa operazione di prodotto fra classi (ed é ovviamente commutativo anch’esso).

Abbiamo già notato che [0] non é certamente simmetrizzabile rispetto al prodotto fra classi, dunque gli elementi simmetrizzabili nel monoide Z

sono da cercare fra le classi diverse da [0], cioé fra le classi [1],..., [m-1].

Il prossimo risultato caratterizza fra queste classi quali sono simmetrizzabili:

Teorema. Una classe [a] del monoide Z

, con il rappresentante a scelto fra 1,...,m-1, é simmetrizzabile rispetto al prodotto fra classi  il rappresentante a della classe é coprimo con il modulo m (ossia mcd(a,m)=1).

Dimostrazione:

(): Se [a] é simmetrizzabile, esiste il suo simmetrico [b] tale che [a][b]=[ab]=[1], dunque si ha la congruenza:

ab1 (mod m)

ossia m è un divisore della differenza (ab-1) dunque esiste un intero k tale che (ab-1)=mk, ossia:

1=ab-(mk)=ab+m(-k)

Si ottiene che 1 é combinazione lineare di a,m con coefficienti interi relativi b,-m, e ricordando che il mcd(a,m) é la minima combinazione lineare positiva di a,m (si ricava dalla dimostrazione del Teorema di esistenza del massimo comune divisore) si deduce che 1=mcd(a,m) e si ha la tesi.

(): Se 1=mcd(a,m), allora, per una proprietà del massimo comune divisore, 1 é combinazione lineare di a,m a con opportuni coefficienti interi relativi x,y

1=ax+my

Da ciò si ha ax-1=m(-y), dunque m é divisore della differenza (ax-1), ossia si ha la congruenza:

ax1 (mod m)

dunque in Z

sono uguali le classi [ax]=[1]

da cui [a][x]=[1]=elemento neutro, e si conclude che [a] é simmetrizzabile (con simmetrico [x]) cioé la tesi.

Il Teorema precedente risolve non solo il problema di caratterizzare quali sono gli elementi simmetrizzabili del monoide Z

rispetto al prodotto di classi, ma per ognuno di essi illustra un algoritmo per calcolare l’inverso (cioè il simmetrico):

1) data una classe [a][0] in Z

si calcola (con l’algoritmo Euclideo) il mcd(a,m) 2) se mcd(a.m)>1 allora si conclude che [a] non é simmetrizzabile

3) se mcd(a,m)=1, allora [a] è simmetrizzabile, ed il suo simmetrico è [x] dove x è il coefficiente di a nella rappresentazione di 1 come combinazione lineare di a,m a coefficienti interi relativi:

1 = ax+my  [a]

=[x]

Per il calcolo del coefficiente x (e quindi dell’inverso di [a]) si può usare egualmente l’algoritmo Euclideo delle divisioni successive.

Sappiamo che, dato un qualunque monoide A (rispetto ad una operazione *), il suo sottoinsieme A*, contenente gli elementi simmetrizzabili, è un gruppo rispetto alla stessa operazione.

In particolare, dato il monoide Z

={[0], [1], …., [m-1]} delle classi di congruenza modulo m

(rispetto all’operazione di prodotto di classi), abbiamo dimostrato che gli elementi simmetrizzabili

sono le classi con rappresentante a compreso fra 1,2,…..,m-1, tali che a,m siano coprimi.

Dunque il sottoinsieme degli elementi simmetrizzabile di Z

: Z

* = {[a] Z

/ a=1,2,….,m-1; a,m coprimi}

È un gruppo, rispetto all’operazione di prodotto di classi: ovviamente la sua cardinalità coincide con la funzione di Eulero (m) del modulo m:

 Z

* = (m) Esempio.

Dato il monoide Z

delle classi di congruenza modulo 9 rispetto all’operazione di prodotto di classi:

Z

= {[0],[1],[2],[3],[4],[5],[6],[7],[8]} (di cardinalità 9)

il gruppo degli elementi simmetrizzabile contiene le classi con rappresentante compreso fra 1 e 8 e coprimo con 9 ossia:

Z

*= {[1],[2],[4],[5],[7]} (di cardinalità (9)=6)

Ricordiamo i dettagli dell’algoritmo Euclideo delle divisioni successive (che, come detto, si può utilizzare anche per calcolare il simmetrico nel caso di un elemento simmetrizzabile del monoide Z

rispetto all’operazione di prodotto di classi).

Siano dati i numeri naturali a,b (con a>b): si effettua una prima divisione di a (dividendo) per b (divisore) ottenendo quoziente q

e resto r

, dove q

, r

sono interi 0, con r

<b; si effettuano poi successive divisioni con la regola seguente: effettuata la divisione numero k, se il resto è 0 l’algoritmo si arresta, mentre se il resto è >0 si effettua un’ulteriore divisione numero k+1, in cui il dividendo e il divisore sono rispettivamente il divisore e il resto della divisione numero k; l’ultimo resto non nullo è il mcd(a,b).

Schematizzando:

a=bq

+r

(q

0, 0<r

<b) b=r

q

+r

(q

0, 0<r

<r

) r

=r

q

+r

(q

0, 0<r

<r

) .

.

r

=r

q

+r

(q

0, 0<r

<r

) r

=mcd(a,b) r

=r

q

+r

(q

0, r

=0)

Parallelamente si possono calcolare i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by nel modo seguente:

si costruiscono le 2 successioni di numeri interi relativi

s

,s

,…..,s

; t

,t

,….,t

(dove n é il numero di divisioni dell’algoritmo Euclideo) ponendo

s

=1, s

=0, s

=s

-s

q

(per ogni i>1);

t

=0, t

=0, t

=t

-t

q

(per ogni i>1)

dove q

è il quoziente della divisione numero (i-1) nell’algoritmo Euclideo.

Basta poi porre x=s

,y=t

per avere i coefficienti x, y (x è il coefficiente di a; y quello di b).

Esempio.

Verifichiamo se [33] è simmetrizzabile nel monoide Z

(rispetto al prodotto di classi) e in caso affermativo calcoliamone il simmetrico.

Calcoliamo il mcd(88,33). Utilizzando l’algoritmo Euclideo si effettuano n=5 divisioni con i seguenti valori di quoziente e resto:

q

=2, r

=23; q

=1, r

=10; q

=2, r

=3; q

=3, r

=1; q

=3, r

=0

Si conclude che mcd(89,33)=r

=1, dunque [33] è simmetrizzabile in Z

.

Calcolando le successioni s

, t

si ottiene s

=-10, t

=27, dunque la rappresentazione di 1 come combinazione lineare di 89,33 è 1=89x+33y, con x= -10, y=27.

In particolare si ottiene che [33] è simmetrizzabile in Z

con simmetrico [27] (perché 27 è il coefficiente di 33 nella combinazione lineare).

Facendo in effetti i calcoli si ottiene [33][27]=[3327]=[891]=[1] (perché 1 è il resto della divisione

di 891 per il modulo 89).