Matematica Discreta Lezione del giorno 14 aprile 2010

Matematica Discreta

Lezione del giorno 14 aprile 2010

Costruiremo ora delle particolari relazioni di equivalenza nell’insieme Z dei numeri interi relativi.

Congruenze aritmetiche

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 con moduli 0 particolari.

a) m=0: 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 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) 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, 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:

Teorema. Fissato il modulo 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 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.

Distinguiamo 2 casi:

I° caso: a>0. In questo caso dividiamo a per m: esistono interi q,r≥0 tali che a=mq+r, con r<m. Si ha a-r=mq, quindi 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 (*).

II° caso: a<0. In questo caso –a>0 e dividiamo (-a) per m: esistono interi q,r≥0 tali che (-a)=mq+r, con r<m. Distinguiamo 2 sottocasi:

I° sottocaso: r=0. In questo sottocaso si ha (-a)=mq quindi a-0=a=m(-q) cioè a≡0 (mod m), da cui [a]=[0], e dunque [a] coincide con una delle classi (*).

II° sottocaso: r>0. In questo sottocaso a-(m-r)=a-m+r=a-m-a-mq=m(-1-q) quindi a≡(m-r) (mod m) e da ciò si ricava [a]=[m-r]. Ma i valori possibili di r sono i numeri 1,2,….,m-1 (perché r>0), dunque i valori possibili di m-r sono i numeri m-1,m-2,…..,1 e si conclude che [a] coincide con una delle classi (*).

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 5, essa coinciderà con una di queste 5 classi.

Per esempio:

[22]=[?] : siamo nel I° caso (a>0) quindi si divide 22 per 6 e si prende il resto r=4, ottenendo [22]=[4]

[-30]=[?] : siamo nel II° caso (a<0) quindi si divide 30 per 6 e poiché il resto è 0 siamo nel I°

sottocaso, ossia si ha [-30]=[0]

[-31]=[?] : siamo nel II° caso (a<0) quindi si divide 31 per 6 e poiché il resto è 1 siamo nel II°

sottocaso, ossia [-31]=[m-r]=[6-1]=[5].

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.