Matematica Discreta II Lezione del giorno 15 ottobre 2007 Per ogni intero xZ esiste un unico intero t=0,1,…..,m-1 tale che [x]=[t] in Z

Matematica Discreta II

Lezione del giorno 15 ottobre 2007

Per ogni intero xZ esiste un unico intero t=0,1,…..,m-1 tale che [x]=[t] in Zm, ossia tale che xt (mod m): tale unico intero t è detto riduzione modulo m di x ed è indicato con xmodm.

Per calcolare xmodm vi è un algoritmo efficiente, che comporta il calcolo di una divisione (e al più una differenza):

- se x=0,1,….,m-1 allora ovviamente xmodm=x; se invece x0,1,……,m-1:

- se x>0 , dividendo x per m si ha x=mq+r, con q,r interi ≥0, r<m, da cui x-r=mq, xr (mod m), r=xmodm (perché r=0,1,…..,m-1)

- se x<0 allora dividendo -x per m si ha -x=mq+r, con q,r interi ≥0, r<m, da cui:

- se r=0 allora x0 (mod m), 0=xmodm

- se r>0 allora x-(m-r)=m(-1-q), x(m-r) (mod m), m-r=xmodm (perché m-r=0,1,…,m-1) Esempi:

18mod7=4, (-28)mod7=0, -30mod7=7-2=5

Se identifichiamo ogni classe di Zm con l’intero che la rappresenta, si ha Zm = {0, 1,……, m-1} e le operazioni di somma e prodotto in Zm sono definite riducendo i risultati modulo m:

x,yZm x+y=(x+y)modm, x∙y=(x∙y)modm

Ciò é particolarmente utile se si devono immettere in un computer gli elementi di Zm per operare calcoli algebrici su di essi.

L’insieme Zm rispetto alla somma di classi eredita, come visto in generale, le proprietà della somma in Z, quindi è un gruppo (commutativo) in cui l’elemento neutro è [0], e il simmetrico (opposto) di ogni elemento [x] è [-x].

Anche rispetto al prodotto di classi Zm eredita le proprietà dell’analoga operazione di prodotto in Z, quindi è un monoide (commutativo) in cui l’elemento neutro è [1]: resta il problema di determinare quali elementi di Zm siano simmetrizzabili rispetto al prodotto.

Notiamo che [0] in ogni caso non lo è, in quanto per ogni [y] si ha [0]∙[y]=[0][1].

Ricordiamo che, dati 2 numeri naturali a,b, il loro massimo comune divisore è il numero naturale d=mcd(a,b) che è divisore comune di a,b e che è multiplo di ogni altro divisore comune di a,b.

Se d=mcd(a,b) allora d è combinazione lineare di a,b, cioè esistono 2 coefficienti interi relativi a’,b’ tali che d=aa’+bb’.

Il mcd(a,b) si può calcolare con l’algoritmo Euclideo delle divisioni successive, che permette anche di calcolare i coefficienti interi relativi a’, b’ tali che mcd(a,b)=aa’+bb’.

Due numeri naturali a,b sono detti coprimi se mcd(a,b)=1.

Se 1 è combinazione lineare di a,b, allora si può concludere che a,b sono coprimi.

Teorema. Un elemento [x]Zm , [x][0], è invertibile in Zm rispetto al prodotto di classi  x,m sono coprimi.

Dimostrazione.

(): Per ipotesi supponiamo che esista il simmetrico [y] di [x] tale che [1]=[x][y]=[xy], da cui xy1 (mod m), xy-1=mk con k intero relativo, 1=xy+m(-k) e si ha la tesi, per quanto premesso.

(): Se x.m sono coprimi allora 1=xx’+mm’ con x’,m’ interi relativi, da cui xx’1 (mod m), [1]=[xx’]=[x][x’], ossia [x] è simmetrizzabile con simmetrico [x’].

Da notare che nella dimostrazione del teorema, se x,m sono coprimi, si indica un algoritmo per il calcolo del simmetrico di [x] in Zm. Basta, con l’algoritmo Euclideo delle divisioni successive

trovare i coefficienti interi relativi x’, m’ tali che 1=xx’+mm’: il simmetrico di [x] è [x’] (se si vuole un rappresentante del simmetrico compreso fra 0,1,….,m-1 basta sostituire x’ con la sua riduzione x’mod m).