Matematica Discreta Lezione del giorno 1 dicembre 2008

(1)

Matematica Discreta

Lezione del giorno 1 dicembre 2008

Se d è il massimo comune divisore dei numeri naturali a,b scriveremo d=mcd(a,b).

Ricordiamo che nel corso della dimostrazione del Teorema di esistenza del mcd(a,b) si è anche dimostrato che il mcd(a,b) è combinazione lineare dei numeri a,b con coefficienti interi relativi, dunque esistono 2 opportuni numeri interi relativi x,y tali che mcd(a,b)=ax+by.

Problemi:

1. Dati i numeri naturali a, b, come calcolare in modo efficiente il mcd(a,b) ?

2. Dati i numeri naturali a, b, come calcolare gli interi relativi x,y tali che mcd(a,b)=ax+by ? (notare che x,y non sono unici, perché per esempio ax+by=a(x+b)-b(y-a)=a(x+2b)+b(y-2a) etc…) La soluzione al Problema 1 è nell’Algoritmo Euclideo delle divisioni successive.

Premettiamo un risultato preliminare:

Teorema. Siano a,b numeri naturali e dividiamo a per b:

a=bq+r con q, r interi 0, ed r<b.

Allora:

1) se r>0 si ha mcd(a,b)=mcd(b,r) 2) se r=0 si ha mcd(a,b)=b

Dimostrazione:

1) Supponiamo r>0 e poniamo d=mcd(a,b). La tesi è che d=mcd(b,r).

Dimostriamo dapprima che r è divisore comune di a,b. Essendo d=mcd(a,b), sappiamo già che d a, db (quindi esistono numeri naturali c,v tali che a=dc, b=dv); essendo già vero che db , si deve solo dimostrare che dr: ma r=a-bq=dc-dvq=d(c-vq) quindi dr.

Resta poi da dimostrare che d è multiplo di ogni divisore comune z di b, r: ma in questo caso esistono numeri naturali f,g tali che b=zf, r=zg, da cui si ricava a=bq+r=zfq+zg=z(fq+g) ossia z a, quindi z è divisore comune di a, b. Ma per ipotesi d=mcd(a,b) quindi d è multiplo di tutti i divisori comuni di a, b, e si conclude in particolare che d è multiplo di z, come si voleva.

2) Supponiamo r=0 e dimostriamo la tesi mcd(a,b)=b. Ovviamente b è divisore sia di a (perché a=bq) che di b (perché (b=b1), dunque è divisore comune di a, b. Resta da verificare che b è multiplo di ogni divisore comune z di a, b: ma ciò è ovvio, perché, essendo z divisore di b, si ha che b è multiplo di z .

Algoritmo Euclideo delle divisioni successive:

L’algoritmo consiste in una successione di divisioni effettuate secondo le regole seguenti:

1) La prima divisione si ottiene dividendo a per b.

2) Data una generica divisione dell’algoritmo, la divisione successiva si effettua solo se il resto della precedente è>0, e nella divisione successiva il dividendo coincide con il divisore della divisione precedente, mentre il divisore coincide con il resto della divisione precedente.

3) L’algoritmo ha termine quando una divisione ha resto =0.

Schematizzando:

divisione 1 a=bq

1

+r

1

con q

1

,r

1

interi 0, r

1

<b (se r

1

>0) divisione 2 b=r

1

q

2

+r

2

con q

2

,r

2

interi 0, r

2

<r

1

(se r

2

>0) divisione 3 r

1

=r

2

q

3

+r

3

con q

3

,r

3

interi 0, r

3

<r

2

(se r

3

>0) divisione 4 r

2

=r

3

q

4

+r

4

con q

4

,r

4

interi 0, r

4

<r

3

………. etc.

(2)

Osserviamo che l’algoritmo ha termine dopo un numero finito di divisioni: se infatti per assurdo così non fosse, si otterrebbe una successione infinita di divisioni tutte con resto >0, ma, essendo i resti legati dalla relazione r

1

>r

2

>r

3

>r

4

>….., l’insieme di tutti questi resti sarebbe un insieme S di numeri naturali senza minimo, in contraddizione con l’Assioma del buon ordinamento.

Supponiamo dunque che l’algoritmo abbia termine dopo n divisioni con resto r

n

=0: dimostreremo che l’ultimo resto non nullo r

n-1

coincide con il mcd(a,b).

Schematizzando:

divisione 1 a=bq

1

+r

1

con q

1

,r

1

interi 0, r

1

<b (se r

1

>0) divisione 2 b=r

1

q

2

+r

2

con q

2

,r

2

interi 0, r

2

<r

1

(se r

2

>0) divisione 3 r

1

=r

2

q

3

+r

3

con q

3

,r

3

interi 0, r

3

<r

2

(se r

3

>0) divisione 4 r

2

=r

3

q

4

+r

4

con q

4

,r

4

interi 0, r

4

<r

3

. . . .

(se r

n-2

>0) divisione (n-1) r

n-3

=r

n-2

q

n-1

+r

n-1

con q

n-1

,r

n-1

interi 0, r

n-1

<r

n-2

(se r

n-1

>0) divisione n r

n-2

=r

n-1

q

n

+r

n

con q

n

,r

n

interi 0, r

n

=0

Se il resto r

n

=0 (quindi se l’algoritmo ha termine con la divisione n) affermiamo che r

n-1

=mcd(a,b).

Per dimostrare tale affermazione basta applicare la parte 1) del Teorema precedente alle prime (n-1) divisioni, ottenendo:

mcd(a,b)=mcd(b,r

1

)=mcd(r

1

,r

2

)=mcd(r

2

,r

3

)=…..=mcd(r

n-2

,r

n-1

)

e poi applicare la parte 2) dello stesso Teorema all’ultima divisione, ottenendo:

mcd(r

n-2

,r

n-1

)=r

n-1

per concludere che in effetti r

n-1

=mcd(a,b).

Esempio: calcoliamo mcd(371,98) con l’algoritmo delle divisioni successive.

Eseguiamo in tutto le seguenti 5 divisioni:

371=983+77 q

1

=3, r

1

=77 98=771+21 q

2

=1, r

2

=21 77=213+14 q

3

=3, r

3

=14 21=141+7 q

4

=1, r

4

=7 14=72+0 q

5

=2, r

5

=0 ottenendo alla fine 7=mcd(371,98).

Per risolvere il Problema 2, illustreremo ora un algoritmo (detto Algoritmo Euclideo esteso) per calcolare i coefficienti interi relativi x,y tali che mcd(a,b)=ax+by, basato sull’algoritmo euclideo delle divisioni successive.

Se n è il numero delle divisioni successive effettuate, costruiamo le seguenti 2 successioni di interi relativi, sfruttando i valori dei quozienti delle divisioni:

prima successione: s

0

,s

1

,s

2

, … , s

n

seconda successione: t

0

,t

1

,t

2

, … , t

n

dove si pone, nella prima successione:

s

0

=1, s

1

=0, e per ogni indice i=2,3, …, n s

i

=s

i-2

-s

i-1

q

i-1

e nella seconda successione:

t

0

=0, t

1

=1, e per ogni indice i=2,3, …, n t

i

=t

i-2

-t

i-1

q

i-1

(dove q

i-1

è il quoziente della divisione numero i-1).

(3)

Osserviamo che s

2

=s

0

-s

1

q

1

=1, t

2

=t

0

-t

1

q

1

=-q

1

, da cui as

2

+bt

2

=a-bq

1

=r

1

(si ricava dalla divisione 1);

inoltre s

3

=s

1

-s

2

q

2

=-q

2

, t

3

=t

1

-t

2

q

2

=-1+q

1

q

2

, da cui as

3

+bt

3

=-aq

2

+b(1+q

1

q

2

)=b-(a-bq

1

)q

2

=b-r

1

q

2

=r

2

(si ricava dalla divisione 2); con analoghi calcoli si ottiene in generale che as

j

+bt

j

=r

j-1

, e in particolare (per j=n) si ottiene as

n

+bt

n

=r

n-1

=mcd(a,b). Quindi i coefficienti cercati nella combinazione lineare sono x=s

n

, y=t

n

.

Esempio: riprendiamo l’esempio precedente mcd(371,98)=7, in cui sono state effettuate n=5 divisioni successive.

La costruzione delle successioni s

i

e t

i

porta ai seguenti valori:

s

0

=1, s

1

=0, s

2

=1, s

3

=-1, s

4

=4, s

5

= -5 t

0

=0, t

1

=1, t

2

=-4, t

3

=4, t

4

=-15, t

5

=19

da cui si ricava x=s

5

=-5, y=t

5

=19 e infine 7= mcd(371,98)=371•(-5)+98•19 .

Numeri primi

Sia a un qualunque numero naturale. Dall’eguaglianza a=a•1 segue che a,1 sono in ogni caso divisori di a (detti divisori banali di a).

Definiamo numero primo un numero naturale a>1 i cui unici divisori sono i divisori banali 1,a . Nota: osserviamo che, nella definizione di numero primo, il numero naturale 1 non è considerato primo. Il motivo di questa esclusione del numero 1 dai numeri primi sarà chiarito nella dimostrazione del “Teorema di fattorizzazione unica”.

Per verificare se un numero naturale a>1 è primo o non lo è, un test “ingenuo” (poco efficiente) consiste ovviamente nell’esaminare tutti i numeri naturali x compresi fra 2 e (a-1), e per ognuno di tali x testare se esso è divisore o no di a (cioè dividendo a per x e verificando se il resto è 0): se nessun valore x fra 2 ed (a-1) è divisore di a, si conclude che a non ha divisori non banali, quindi a è primo; se qualche valore x fra 2 ed (a-1) è divisore di a, si è trovato un divisore non banale di a, quindi a non è primo.