Matematica Discreta Lezione del giorno 22 aprile 2009

Matematica Discreta

Lezione del giorno 22 aprile 2009

Nella lezione precedente abbiamo osservato che se un insieme A é dotato di operazione , e se in A é anche definita una relazione di equivalenza R compatibile con l’operazione  (nel senso che, dati gli elementi a,b,c,d in A, da aRc, bRd segue sempre (a*b)R(c*d)) allora l’insieme A/R delle classi di equivalenza è anch’esso dotato di un’operazione (indicata con lo stesso simbolo *) che é definita nel modo seguente: date 2 classi di equivalenza [a],[b] (come operandi) si pone

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

(dove ovviamente per calcolare il risultato a*b si usa l’operazione * dell’insieme A).

Dimostriamo che, considerata nell’insieme Z dei numeri interi relativi la relazione di congruenza modulo m (dove m, detto modulo é un intero >1 fissato), le usuali operazioni aritmetiche di somma e prodotto fra numeri interi relativi sono entrambe compatibili con la relazione di congruenza modulo m:

compatibilità della 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 opportuni 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à del 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).

Indicheremo con il simbolo Z

l’insieme delle classi di congruenza modulo m: ricordiamo che tale insieme contiene le m classi distinte

Z

= {[0], [1],..., [m-1]}

La compatibilità di somma e prodotto di interi con la relazione di congruenza modulo m permette dunque di definire 2 analoghe operazioni di somma e prodotto di classi nell’insieme Z

:

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

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 A/R delle classi di equivalenza sia definita un’analoga operazione * 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 * 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 * 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 * e 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 * 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’analoga operazione *

- se A é gruppo rispetto all’operazione *, anche A/R é gruppo rispetto all’analoga operazione * 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.

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

, ricordiamo che, date 2 classi di congruenza [a],[b] scelte fra le classi {[0], [1],..., [m-1]}, la somma [a]+[b] delle 2 classi é la classe [a+b]: se il rappresentante a+b fosse >m-1, possiamo scegliere per la classe [a+b] un rappresentante fra i numeri 0,1,...,m-1 con un algoritmo già visto (si prende il resto r della divisione di a+b per il modulo m).

Per esempio, in Z

si ha:

[2]+[4] = [2+4] = [6];

[5]+[7] = [5+7] = [12] =[4] (perché r=4 é il resto della divisione di 12 per il modulo 8) Per quanto riguarda 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 [2] é [8-2] = [6].

Poiché siamo nella simbologia additiva, il simmetrico della classe [a] é anche chiamato opposto di [a] e indicato con il simbolo –[a].

Per esempio in Z

, come visto sopra, si ha -[2] = [6].

Esempio. Costruiamo per esempio la tavola dell’operazione di somma fra classi del gruppo commutativo Z

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

Si ottiene la seguente tavola 4x4:

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

[0]

[1]

[2]

[3]

(notare che le righe e le colonne sono una semplice rotazione ciclica delle 4 classi [0], [1], [2], [3], e ciò avviene per ogni Z

rispetto alla somma di classi).

Come previsto la tavola é un quadrato latino (essendo quella dell’operazione di un gruppo).

Rispetto all’operazione di prodotto di classi, l’insieme Z

é un monoide commutativo (con elemento neutro [1]).

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

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

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

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

Ricordiamo che il prodotto [a][b] di 2 classi [a], [b] (scelte fra [0], [1],..., [m-1]) é la classe [ab]:

se il rappresentante ab fosse >m-1, possiamo scegliere per la classe [ab] un rappresentante fra i numeri 0,1,...,m-1 con un algoritmo ricordato sopra (si prende il resto r della divisione di a b per il modulo m).

Esempio. Costruiamo per esempio la tavola dell’operazione di prodotto fra classi del monoide commutativo Z

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

Si ottiene la seguente tavola 4x4:

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

[0]

[1]

[2]

[3]

Possiamo notare che si tratta appunto di un monoide e non di un gruppo: infatti gli elementi simmetrizzabili sono solo l’elemento neutro [1] (con simmetrico [1]) e l’elemento [3] (con simmetrico [3]); invece gli elementi [0], [2] non hanno simmetrico (non esiste un elemento di Z

che moltiplicato per uno di essi dia come risultato l’elemento neutro [1]).

Poiché siamo nella simbologia moltiplicativa, il simmetrico della classe [a] (se essa é simmetrizzabile) é anche chiamato inverso di [a] e indicato con il simbolo [a]

.

Per esempio in Z

, come visto sopra, si ha [3]

= [3].

Invece in Z

, per esempio, [5] é simmetrizzabile ed il suo simmetrico é [2] (perché [5][2]=

[10]=[1]) dunque in Z

si ha [5]

=[2].

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

Per trovare gli elementi simmetrizzabili nel monoide Z

possiamo prima di tutto notare che [0] non é certamente simmetrizzabile rispetto al prodotto fra classi: non può esistere il simmetrico [x] di [0]

perché il prodotto di [0] per qualunque classe dà come risultato sempre [0] (mai [1] che é l’elemento neutro).

Dunque i 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 inverso [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) [0] [0] [0] [0]

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

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

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

Si ottiene che 1 é combinazione lineare di a,m a 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 inverso [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 inverso è [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.