Matematica Discreta I Lezione del giorno 5 dicembre 2007 Teorema.

Matematica Discreta I

Lezione del giorno 5 dicembre 2007

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:

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

Comunque preso un rappresentante aZ la tesi è che [a] coincide con una delle classi (*).

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 si ha m-r>0 (perché r<m) ed m-r<m (perché r>0) dunque in totale 0<m-r<m. Inoltre 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 (m-r) sono i numeri 1,…,m-1, dunque [a] coincide con una delle classi (*).

Dimostriamo ora 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); dunque x≡y(mod m), ossia la differenza 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].