Matematica Discreta Lezione dei giorno 22 marzo 2012

Matematica Discreta

Lezione dei giorno 22 marzo 2012

Le classi di equivalenza hanno una importante proprietà:

Teorema. Sia definita nell’insieme A una relazione di equivalenza R.

Le diverse classi di equivalenza formano una partizione dell’insieme A.

Dimostrazione:

Dimostriamo le proprietà che caratterizzano una partizione di A

1) Le classi di equivalenza sono sottoinsiemi non vuoti di A: questo è già stato notato prima, sfruttando la proprietà riflessiva (la classe rappresentata da a contiene almeno l’elemento a)

2) Date 2 generiche classi diverse [a]≠[b], esse sono disgiunte, ossia hanno intersezione vuota: per assurdo supponiamo che abbiano un elemento in comune x; dunque xRa (perché x [a]) e anche xRb (perché x[b]). Ma allora da aRx segue xRa (per la simmetrica) e da aRx e xRb segue aRb (per la transitiva). Infine da aRb segue, per il teorema precedente, l’eguaglianza [a]=[b], contraddizione.

3) L’unione di tutte le classi di equivalenza è uguale all’insieme A: ciò è ovvio, perché preso un generico elemento aA, tale elemento appartiene ad almeno una classe di equivalenza (per esempio alla classe [a], sempre per la proprietà riflessiva).

Esempio: nell’esempio della lezione precedente si sono ottenute 2 diverse classi di equivalenza {numeri naturali pari} e {numeri naturali dispari}, e in effetti esse costituiscono una partizione di N, come affermato dal Teorema.

Congruenze aritmetiche

Esamineremo alcune particolari relazioni di equivalenza definite nell’insieme Z dei numeri interi relativi (cioè positivi, negativi e lo 0).

Estendiamo dapprima i concetti di divisore e di multiplo dall’insieme N dei numeri naturali all’insieme Z dei numeri interi relativi: se a,bZ diremo che a è divisore di b (o che b è multiplo di a) e scriveremo ab , se esiste un cZ tale che ac=b.

Per esempio (-3)15 perché esiste –5Z tale che (-3)(-5)=15.

Osservazioni:

1) Per ogni aZ si ha 1a per l’identità 1a = a 2) Per ogni aZ si ha a0 per l’identità a0 = 0

3) L’unico aZ tale che 0a è a = 0 (in quanto se 0a esiste un cZ tale che 0c = a da cui a = 0).

Fissiamo un intero relativo mZ (detto modulo) e definiamo una particolare relazione nell’insieme Z mediante il predicato P(x,y)=”m(x-y)”. Dunque un numero intero relativo a è associato (in tale relazione) ad un numero intero relativo b quando m è divisore della differenza (a-b), o equivalentemente quando la differenza (a-b) è un multiplo di m.

Tale relazione è detta congruenza aritmetica modulo m, e se un intero relativo a è associato (in tale relazione) ad un intero relativo b, diremo che a è congruo b modulo m e scriveremo:

a≡b (mod m)

Per esempio: 12≡2 (mod 5) perché 5 è divisore della differenza (12-2)=10;-16≡5 (mod -7) perché -7

è divisore della differenza -16-5=-21.

Teorema. Fissato un qualunque intero relativo mZ, la relazione di congruenza modulo m è una relazione di equivalenza.

Dimostrazione:

Proprietà riflessiva: per ogni aZ si ha a≡a (mod m) perché a-a=0=m0 è multiplo di m.

Proprietà simmetrica: per ogni a,bZ se a≡b (mod m) allora si ha b≡a (mod m) perché se a-b=mk con kZ, allora b-a=-(a-b)=m(-k) con (-k)Z.

Proprietà transitiva: per ogni a,b,cZ se a≡b (mod m) e se b≡c (mod m) allora si ha a≡c (mod m) perché se a-b=mk, b-c=mh con k,hZ, allora a-c=(b+mk)-(b-mh)=m(h+k) con (h+k)Z.

Notiamo che se a≡b (mod m) allora esiste cZ tale che (a-b)=mc, da cui (a-b)=(-m)(-c) quindi si ha anche a≡b (mod -m); viceversa se a≡b (mod -m) allora si ha anche (con ragionamenti analoghi) che a≡b (mod m). Dunque la relazione di congruenza modulo m coincide con la relazione di congruenza modulo –m, da cui si deduce che possiamo limitarci a studiare le congruenze con modulo non negativo.

Quindi supporremo d’ora in poi che il modulo m sia sempre 0 . Studiamo alcuni casi particolari con moduli 0

a) il caso del modulo m=0: in tale caso si ha a≡b (mod 0) se (a-b) è multiplo di 0, quindi se esiste cZ tale che a-b=0c=0 ossia se a=b. Dunque la relazione di congruenza modulo 0 coincide con la relazione di eguaglianza: ogni classe di equivalenza contiene un solo elemento (il rappresentante della classe) e si ottengono infinite classi.

b) il caso del modulo m=1: si ha a≡b (mod 1) se (a-b) è multiplo di 1, ma ciò è sempre vero (ogni xZ è multiplo di 1 per l’identità x =1x) . Dunque nella congruenza modulo 1 tutti gli interi relativi sono congrui fra loro: esiste allora un’unica classe di equivalenza, coincidente con l’intero insieme Z.

Avendo studiato in dettaglio tali casi particolari, ci limiteremo a studiare solo i casi rimanenti:

quindi supporremo sempre d’ora in poi che il modulo m sia >1.

Cercheremo di risolvere i seguenti problemi relativi alla relazione di congruenza modulo m:

1) Fissato il rappresentante aZ, quali sono i numeri interi relativi contenuti nella classe [a] ? 2) Quante sono le diverse classi di equivalenza ?

Per quanto riguarda il problema 1), se scegliamo ad arbitrio un rappresentante aZ, dalla teoria delle classi di equivalenza sappiamo che la classe di congruenza [a] rappresentata da a è definita come segue:

[a] = { xZ / x≡a (mod m) } = { xZ / m è divisore di x-a } = { xZ / x-a=mk con kZ }=

= { xZ / x=a+mk con kZ }.

Dunque gli elementi di [a] sono della forma x=a+mk con k che varia in Z: al variare del parametro k fra tutti gli interi relativi, si ottengono tutti gli elementi della classe [a] (che sono dunque infiniti numeri interi relativi).

Possiamo calcolare qualche elemento di [a] facendo assumere al coefficiente k alcuni particolari valori interi relativi (k=0,1,-1,2,-2,…..): [a] = {a , a+m , a-m , a+2m , a-2m ,….}

Esempio: nella congruenza modulo m=9, la classe [5] rappresentata da a=5 contiene i numeri della

forma x=5+9k, con k che varia in Z: [5] = { 5, 14, -4, 23, -13, ….}.

Per quanto riguarda il problema 2), abbiamo visto che ogni classe di congruenza modulo m contiene infiniti numeri interi relativi, e conosciamo la struttura che hanno i numeri di ogni classe, ma quante sono in tutto le distinte classi di congruenza modulo m ?

Esaminiamo prima un esempi particolare.

Esempio. Studiamo le classi di congruenza modulo m=3.

Costruiamo una di tali classi, fissando per esempio il rappresentante a=5:

[5] = { xZ / x≡5 (mod 3) } = { xZ / x=5+3k con kZ } = {5, 8, 2, 11, -1, …}

Se vogliamo costruire una classe di congruenza diversa da [5], dobbiamo scegliere un rappresentante che non sia congruo 5 modulo 3 (perché sappiamo da un Teorema precedente che se aRb allora [a]=[b]). Possiamo per esempio scegliere a=9 (la differenza 9-5=4 non è multiplo di m=3):

[9] = { xZ / x≡9 (mod 3) } = { xZ / x=9+3k con kZ } = {9, 12, 6, 15, 3, …}

Se vogliamo costruire una classe di equivalenza diversa dalle 2 classi già costruite, dobbiamo scegliere un rappresentante a che non sia congruo 5 modulo 3 e che non sia congruo 9 modulo 3.

Possiamo per esempio scegliere a=-2 (le differenze -2-5=-2, -2-9=-11 non sono multipli di m=3):

[-2] = { xZ / x≡-2 (mod 3) } = { xZ / x=-2+3k con kZ } = {-2, 1, -5, 4, -8, …}

A questo punto, anche facendo diversi tentativi, ci accorgiamo di non riuscire a costruire una classe di equivalenza diversa dalle 3 già costruite, perché non riusciamo a trovare un rappresentante a che non sia congruo 5 modulo 3, che non sia congruo 9 modulo 3, e che non sia congruo -2 modulo 3.

Da questo ragionamento un po’ empirico, possiamo concludere che le classi di congruenza distinte modulo 3 sono:

[5], [9], [-2]

ossia le classi sono in numero di 3, cioè in numero uguale al modulo.

Il prossimo teorema dimostrerà che ciò non è casuale.

Premettiamo però una generalizzazione dell’algoritmo della divisione, che abbiamo dimostrato già valido per una coppia di numeri naturali a,b, ma che estenderemo anche al caso in cui il primo numero a è <0.

Teorema (Algoritmo della divisione generalizzato).

Dati comunque i numeri interi non nulli a,b tali che sia b>0, esistono (e sono unici) due numeri interi relativi q,r (detti quoziente e resto) tali che a=bq+r, con r0 ed r<b.

(notare che non si pretende più che il quoziente q sia 0).

Dimostrazione:

Se a>0 la tesi è ovvia, perché si tratta dell’algoritmo della divisione per numeri naturali, già dimostrato in precedenza. Quindi supponiamo a<0.

Essendo a<0 si ha (–a)>0, dunque possiamo applicare l’algoritmo della divisione per numeri naturali, dividendo il numero –a>0 per il numero b>0 e trovando quoziente q

e resto r

(interi 0) tali che (-a)=bq

+r

con r

<b. Distinguiamo 2 casi possibili:

I° caso: r

=0. In questo caso si ha (-a)=bq

quindi a=(-bq

)=b(-q

)+0 e basta porre q=-q

, r=0, per ottenere l’esistenza di q,r e quindi la tesi.

II° caso: r

>0. In questo caso si ha a= -bq

-r

= -bq

-b+b-r

= b(-q

-1)+b-r

e basta porre q=-q

-1, r=b-r

, per ottenere l’esistenza di q,r e quindi la tesi (notare che la proprietà r<b è soddisfatta perché r

>0).

L’unicità del quoziente q e del resto r si dimostra con metodi simili a quelli utilizzati nell’algoritmo della divisione per i numeri naturali.

Nel prossimo Teorema dimostreremo quali e quante sono le classi di congruenza distinte modulo

m>1.

Teorema. Fissato il modulo intero m>1, le seguenti classi di congruenza modulo m:

[0], [1], ………., [m-1] (*)

sono tutte distinte ed esauriscono tutte le classi di congruenza modulo m. In particolare vi sono dunque esattamente m distinte classi di congruenza modulo m.

Dimostrazione:

La tesi richiede la dimostrazione di 2 affermazioni:

a) le classi (*) sono tutte le classi di congruenza modulo m.

b) le classi (*) sono distinte

Dimostriamo la a): comunque preso un rappresentante aZ la tesi è che [a] coincide con una delle classi (*). Se a è uno dei numeri 0,1,….,m-1, non c’è niente da dimostrare. Sia dunque a diverso da 0,1,….,m-1.

Possiamo applicare l’algoritmo della divisione generalizzato ai numeri a,m, trovando quoziente q e resto r (interi relativi) tali che a=mq+r, con r0 ed r<m.

Si ha allora a-r=mq, ossia a≡r (mod m) e da ciò si ricava [a]=[r].

Ma i valori possibili del resto r sono i numeri 0,1,…,m-1, dunque [a] coincide con una delle classi (*), come volevamo dimostrare nella a).

Dimostriamo la b): la tesi è che le classi (*) sono distinte. Se per assurdo 2 di tali classi coincidessero, si avrebbe [x] = [y], con 0≤x,y≤m-1, e con xy (per esempio sia x>y: nel caso opposto x<y si ragiona in modo analogo). Da [x]=[y] seguirebbe x≡y(mod m), ossia x-y sarebbe un multiplo di m, cioè x-y=kt con k intero; ma x-y>0 (perché x>y) ed inoltre x-y<m (perché x<m) e ciò implicherebbe k>0 e k<1, contraddizione perché k è intero.

Esempio: consideriamo il modulo m=6. Per il Teorema precedente vi sono 6 distinte classi di congruenza modulo 6 ed esse sono [0], [1], [2], [3], [4], [5]. Se prendiamo una qualunque classe di congruenza modulo 6, essa coinciderà con una di queste 6 classi.

Nell’esempio precedente in cui abbiamo studiato empiricamente le classi di congruenza modulo 3, trovando le 3 classi:

[5], [9], [-2]

possiamo notare che [5]=[2], [9]=[0], [-2]=[1]

dunque le 3 classi di congruenza distinte modulo 3 sono:

[0], [1], [2]

coerentemente con l’ultimo teorema dimostrato.