♦ Algoritmo euclideo

(1)

♦

♦ Divisione in Z / M.C.D.

♦

♦ Algoritmo euclideo

♦

♦ Identità di Bezout

♦

♦ Equazioni diofantee lineari

♦

♦ Riconoscimento delle relazioni di equivalenza

simbolo indicante argomento trattato e discusso in classe ma non riportato in queste slides

Rosalba Barattero

ESERCITAZIONE N.5

3 novembre 2009

ESERCIZIO C 1.

M.C.D. con l'algoritmo euclideo e identità di Bezout

a)Calcolare il M.C.D. tra 88 e 34 con l’algoritmo di Euclide, e scrivere la corrispondente identità di Bezout.

b)Stabilire se 88x+34y=10 ha soluzioni intere e, in caso affermativo determinarle tutte.

a) L'algoritmo euclideo consiste in una sequenza di divisioni successive:

♦ Ricordiamo la D IVISIONE IN Z

Dati a e b interi, con b≠0, esistono e sono univocamente determinati due interi q ( quoziente) ed r ( resto) tali che

a=bq+r con 0≤r<|b|

Qua la richiesta è di trovare il M.C.D. tra due numeri positivi ! E se fossero uno o entrambi negativi ?

E’ unico M.C.D. (a,b) , con a, b∈Z ?

♦ M.C.D (a,b) è per def. d∈Z t.c.

i) d|a e d|b ( d divide a ossia d è divisore di a … ) ii) se d′|a e d′|b => d′|d

Se d gode delle proprietà i ) e ii) anche –d gode delle

stesse proprietà. Quindi nel caso di Z, ±d vanno bene

(2)

come M.C.D.. Quando si dice il M.C.D. si intende quello positivo !

Iniziamo dividendo il maggiore per il minore (ovvio !)

1. 88 = 34 ⋅ 2 + 20 2. 34 = 20 ⋅ 1 + 14

3. 20 = 14 ⋅ 1 + 6 4. 14 = 6 ⋅ 2 + 2 5. 6 = 2 ⋅ 3

L’algoritmo di Euclide afferma che l’ultimo resto non nullo è il M.C.D.(88,34). Abbiamo trovato M.C.D.(88,34)=2 . Questo succede perché il M.C.D. tra dividendo e divisore di una divisione euclidea è uguale al M.C.D. tra divisore e resto.

Così si ha: M.C.D.(88,34)=M.C.D.(34,20)=M.C.D. (20,14)

= M.C.D.(14,6) = M.C.D.( 6,2) = 2

♦ Teorema di Bezout

Se d= M.C.D. (a,b), allora esistono due interi m, n tali che d= am +bn.

poiché il resto è 20≠0 (minore di 34, come deve essere !),

procediamo dividendo il divisore 34 per il resto 20, e così via, fino ad avere resto nullo.

Sottolineiamo i resti ( per succes- siva utilità ).

Scriviamo dunque 2 come combinazione lineare di 88 e 34.

Alla tabella precedente affianchiamo a destra l’espressione dei resti:

1. 88 = 34 ⋅ 2 + 20 1r. 20 = 88 - 34 ⋅ 2 2. 34 = 20 ⋅ 1 + 14 2r. 14 = 34 - 20 ⋅ 1 3. 20 = 14 ⋅ 1 + 6 3r. 6 = 20 - 14 ⋅ 1 4. 14 = 6 ⋅ 2 + 2 4r. 2 = 14 - 6⋅2 5. 6 = 2 ⋅ 3

Partiamo dalla riga 4r.(quella in cui compare l’ultimo resto non nullo ), e sostituiamo a ritroso i resti:

2 =14 – 6⋅2

Risaliamo alla riga precedente, la 3r., che dice:6=20– 14 ⋅1, allora sostituiamo il 6 con (20 – 14 ⋅1).

= 14 – (20 – 14⋅1) ⋅2

Non effettuiamo il calcolo dentro la parentesi, ma togliamo la parentesi, all’interno della quale c’è una somma di numeri interi, che va moltiplicata per 2, quindi per la propr. distr.

dell’anello Z moltiplichiamo ogni addendo per 2.

= 14 – 20 ⋅2 + 14 ⋅2

Effettuiamo ora il raccoglimento a fattor comune. Come?

L’obiettivo è evidenziare i resti, per poterli

sostituire al passaggio successivo, quindi raccogliamo 14, resto che compare alla riga 2r.

= 14 (1+2) – 20 ⋅2

(3)

= 14⋅3 – 20⋅2

Ora ripetiamo il processo risalendo alla riga precedente2r., che dice: 14 = 34 – 20 ⋅ 1, allora sostituiamo il 14 con (34 – 20 ⋅ 1).

= (34 – 20 ⋅ 1) ⋅3 – 20⋅2 … procediamo come sopra = 34 ⋅3 – 20⋅3 – 20⋅2

Raccogliamo ora 20, resto che compare alla riga 1r.

= 34 ⋅3 – 20 ⋅5

Ora ripetiamo il processo risalendo alla riga precedente, 1r.: 20=88 – 34⋅2, allora sostituiamo 20 con (88 – 34⋅2).

= 34 ⋅3 – (88 – 34 ⋅ 2)⋅5

= 34 ⋅3 - 88⋅5 + 34 ⋅ 10 … come sopra = 34 ⋅13 - 88⋅5

Il processo è terminato e si è ottenuto 2= 34 ⋅13 - 88⋅5 che, riscriviamo così: 88(-5)+34(13) =2 .

C ONCLUSIONE . M.C.D.(88,34)=2 & 2 = 88(-5) + 34(13) il M.C.D. (88,34)=2, scritto come comb.lin. di 88 e 34.

Ho giustificato ogni passaggio, anche il più scontato, per mettere bene in evidenza le sostituzioni (′spontanee′) da farsi !

b)Stabilire se 88x+34y=10 ha soluzioni intere e, in caso affermativo determinarle tutte.

Geometricamente nel piano reale R ² l’equazione 88x+34y=10 rappresenta una retta, di cui stiamo cercando i punti a coordinate intere, se ci sono ! (Le equazioni diofantee lineari sono equazioni di I°grado a coefficienti in Z che vengono risolte in Z)

Da a) abbiamo trovato due interi x e y tali che 88x+34y=2 (*) La domanda è :stabilire se 88x+34y=10 ha soluzioni intere.

E’ facile rispondere! Basta moltiplicare per 5 ! Ma se non aves- simo trovato una soluzione intera di (*) ricordiamo che si ha:

♦ L'equazione ax+by=c, con a,b∈Z, c∈Z ^* ha soluzioni in Z ⇔ M.C.D. (a,b) divide c 2=M.C.D.(88,34) divide 10 ⇒ l’eq.

^ne

ha sol.

ⁿⁱ

intere

♦ Cerchiamo ora una soluzione dell’eq. data. In a)

abbiamo trovato l’identità di Bezout: 88(-5) + 34(13) = 2 Come detto, se moltiplichiamo l’uguaglianza per 5

troviamo:

R

∃ P(a,b)∈Z

²

su r ?

O 5/17

5/44

r

(4)

88(-5⋅5) + 34(13⋅5) = 2⋅5, che possiamo riscrivere così 88(-25) + 34(65) = 10. Questa uguaglianza ci dice che (-25,65) (x=-25, y=65) è soluzione di 88x+34y=10 !

Dunque procediamo così per le eq.

ⁿⁱ

diofantee:

Passo 1. Stabiliamo se l’equazione data ha sol.

ⁿⁱ

intere. Se sì :

Passo 2. troviamo prima con l'algoritmo di Euclide una soluzione di ax+by=d, con d=M.C.D. (a,b)

Discussione su metodi empirici di ricerca di una soluzione intera e sulla eventuale necessità di trovare ugualmente il M.C.D. per trovare tutte le soluzioni intere.

Passo 3. Scriviamo quindi l’identità di Bezout per d

[ 88(-5) + 34(13) = 2] e poi la moltiplichiamo per l’intero

d c [=

2 10 =5 ]

Passo 4. Per trovare tutte le soluzioni dobbiamo risolvere l’equazione omogenea associata 88x+34y=0.

E’ essenziale, per non perdere soluzioni, rendere i coef- ficienti coprimi ( primi fra loro), se non lo sono già ! Qui 88 e 34 non sono coprimi, infatti M.C.D.(88,34)=2.

Quindi si semplificano i coefficienti per 2, M.C.D., e si ricava l’equazione 44x+17y=0 equivalente a 88x+34y=0 , le cui infinite soluzioni sono (-17t, 44t) al variare di t in Z , o equivalentemente (17t, -44t) al variare di t in Z.

( Mnemonicamente: si ′incrociano′ i coeff.)

N.B. La mancata semplificazione porterebbe alle sol. ⁿⁱ (34u,-88u) al variare di u in Z . Così facendo andrebbe perduta la sol. ^ne (17,-44) ottenibile per u = ½ ∉ Z . E perché si ′incrociano′ i coeff. ? Lo abbiamo discusso la volta scorsa : 44x=-17y : 44 divide -17y, ma 44 è primo con 17 ( non hanno fattori a comune), allora 44 divide y=> y= 44 t e così x=-17 t .

Passo 5. Infine si somma la soluzione generale dell’omo- genea con la soluzione particolare e si determinano TUTTE le soluzioni di 88x+34y=10 :

(-17t,44t)+(-25,65) = (somma ordinata delle componenti)

= (-17t-25,44t+65) al variare di t∈Z.

(5)

ESERCIZIO 2.

Esercizio su M.C.D.

a) Provare , senza fare il calcolo che M.C.D.(2009,2039) è divisore di 600.

b) Trovare M.C.D. ( 2 ² ⋅ 3 ³ ⋅ 7, 14076) senza scomporre in fattori primi 14076 e senza calcolatrice !

a)

2039-2009=30

2039(1)+2009(-1)=30

l’eq. ^ne 2039x+2009y=30 ha sol. ⁿⁱ in Z d=M.C.D. (2009,2039) divide 30 d h =30 con h ∈Z

d(20h)= 600 d divide 600 ok !

b) 14076 : 2 = 7038

7038: 2 = 3519 :stop con 2!

3519: 3= 1173 1173: 3= 391

391:3 :non divisibile, stop con 3

(somma cifre non divisibile per 3) 391 : 7 :non divisibile!

=> M.C.D.( 2 ² ⋅3 ³ ⋅7, 14076)=2 ² ⋅ 3 ² = 36.

Basta utilizzare la regoletta della scuola media:

M.C.D. tra 2 numeri è il prodotto dei fattori comuni presi con il minimo esponente !

ESERCIZIO 3.

Relazioni di equivalenza

In ùxù si consideri la relazione (a,b)∼(c,d) ⇔ a+d=b+c.

Provare che ∼ è una relazione di equivalenza

a) Riflessiva: (a,b)∼(a,b) ∀ (a,b)∈ùxù

Verifichiamolo:

(a,b)∼(a,b) ⇔ a+b=b+a

Ma a+b=b+a è vera in ù per la proprietà commutati-

va dell'addizione e quindi è vero che (a,b)∼(a,b) per ogni (a,b)∈ùxù

Discussione su:

- significato di relazione di equivalenza

- esempio della relazione di uguaglianza su un insieme, della relazione di parallelismo

nell’insieme delle rette nel piano. La direzione:

caratteristica comune a rette parallele.

- ricerca elementi in relazione e non in relazione.

(6)

Simmetrica:(a,b)∼(c,d)⇒(c,d)∼(a,b) ∀(a,b),(c,d)∈ùxù Verifica:

Per la definizione di ∼ sappiamo che

(a,b)∼(c,d) ⇔ a+d=b+c

(c,d)∼(a,b) ⇔ c+b=d+a

Se proviamo l'implicazione di destra allora vale 'automa-

ticamente' l'implicazione di sinistra.

E ciò è vero perché

a+d=b+c ⇒ d+a=c+b (propr. comm. di ù )

⇒ c+b=d+a (propr.comm.dell'uguaglianza di ù ) Quindi (a,b)∼(c,d)⇒(c,d)∼(a,b).

c) Transitiva: se (a,b)∼(c,d) e (c,d)∼(e,f) allora (a,b)∼(e,f) ∀ (a,b), (c,d), (e,f) ∈ùxù

♦ Algoritmo euclideo

♦

♦ Divisione in Z / M.C.D.

♦

♦ Algoritmo euclideo

♦

♦ Identità di Bezout

♦

♦ Equazioni diofantee lineari

♦

♦ Riconoscimento delle relazioni di equivalenza

simbolo indicante argomento trattato e discusso in classe ma non riportato in queste slides

Rosalba Barattero

ESERCITAZIONE N.5

3 novembre 2009

ESERCIZIO C 1.

M.C.D. con l'algoritmo euclideo e identità di Bezout

a)Calcolare il M.C.D. tra 88 e 34 con l’algoritmo di Euclide, e scrivere la corrispondente identità di Bezout.

b)Stabilire se 88x+34y=10 ha soluzioni intere e, in caso affermativo determinarle tutte.

a) L'algoritmo euclideo consiste in una sequenza di divisioni successive:

♦ Ricordiamo la D IVISIONE IN Z

Dati a e b interi, con b≠0, esistono e sono univocamente determinati due interi q ( quoziente) ed r ( resto) tali che

a=bq+r con 0≤r<|b|

Qua la richiesta è di trovare il M.C.D. tra due numeri positivi ! E se fossero uno o entrambi negativi ?

E’ unico M.C.D. (a,b) , con a, b∈Z ?

♦ M.C.D (a,b) è per def. d∈Z t.c.

i) d|a e d|b ( d divide a ossia d è divisore di a … ) ii) se d′|a e d′|b => d′|d

Se d gode delle proprietà i ) e ii) anche –d gode delle

stesse proprietà. Quindi nel caso di Z, ±d vanno bene

come M.C.D.. Quando si dice il M.C.D. si intende quello positivo !

Iniziamo dividendo il maggiore per il minore (ovvio !)

1. 88 = 34 ⋅ 2 + 20 2. 34 = 20 ⋅ 1 + 14

3. 20 = 14 ⋅ 1 + 6 4. 14 = 6 ⋅ 2 + 2 5. 6 = 2 ⋅ 3

L’algoritmo di Euclide afferma che l’ultimo resto non nullo è il M.C.D.(88,34). Abbiamo trovato M.C.D.(88,34)=2 . Questo succede perché il M.C.D. tra dividendo e divisore di una divisione euclidea è uguale al M.C.D. tra divisore e resto.

Così si ha: M.C.D.(88,34)=M.C.D.(34,20)=M.C.D. (20,14)

= M.C.D.(14,6) = M.C.D.( 6,2) = 2

♦ Teorema di Bezout

Se d= M.C.D. (a,b), allora esistono due interi m, n tali che d= am +bn.

poiché il resto è 20≠0 (minore di 34, come deve essere !),

procediamo dividendo il divisore 34 per il resto 20, e così via, fino ad avere resto nullo.

Sottolineiamo i resti ( per succes- siva utilità ).

Scriviamo dunque 2 come combinazione lineare di 88 e 34.

Alla tabella precedente affianchiamo a destra l’espressione dei resti:

1. 88 = 34 ⋅ 2 + 20 1r. 20 = 88 - 34 ⋅ 2 2. 34 = 20 ⋅ 1 + 14 2r. 14 = 34 - 20 ⋅ 1 3. 20 = 14 ⋅ 1 + 6 3r. 6 = 20 - 14 ⋅ 1 4. 14 = 6 ⋅ 2 + 2 4r. 2 = 14 - 6⋅2 5. 6 = 2 ⋅ 3

Partiamo dalla riga 4r.(quella in cui compare l’ultimo resto non nullo ), e sostituiamo a ritroso i resti:

2 =14 – 6⋅2

Risaliamo alla riga precedente, la 3r., che dice:6=20– 14 ⋅1, allora sostituiamo il 6 con (20 – 14 ⋅1).

= 14 – (20 – 14⋅1) ⋅2

Non effettuiamo il calcolo dentro la parentesi, ma togliamo la parentesi, all’interno della quale c’è una somma di numeri interi, che va moltiplicata per 2, quindi per la propr. distr.

dell’anello Z moltiplichiamo ogni addendo per 2.

= 14 – 20 ⋅2 + 14 ⋅2

Effettuiamo ora il raccoglimento a fattor comune. Come?

L’obiettivo è evidenziare i resti, per poterli

sostituire al passaggio successivo, quindi raccogliamo 14, resto che compare alla riga 2r.

= 14 (1+2) – 20 ⋅2

= 14⋅3 – 20⋅2

Ora ripetiamo il processo risalendo alla riga precedente2r., che dice: 14 = 34 – 20 ⋅ 1, allora sostituiamo il 14 con (34 – 20 ⋅ 1).

= (34 – 20 ⋅ 1) ⋅3 – 20⋅2 … procediamo come sopra = 34 ⋅3 – 20⋅3 – 20⋅2

Raccogliamo ora 20, resto che compare alla riga 1r.

= 34 ⋅3 – 20 ⋅5

Ora ripetiamo il processo risalendo alla riga precedente, 1r.: 20=88 – 34⋅2, allora sostituiamo 20 con (88 – 34⋅2).

= 34 ⋅3 – (88 – 34 ⋅ 2)⋅5

= 34 ⋅3 - 88⋅5 + 34 ⋅ 10 … come sopra = 34 ⋅13 - 88⋅5

Il processo è terminato e si è ottenuto 2= 34 ⋅13 - 88⋅5 che, riscriviamo così: 88(-5)+34(13) =2 .

C ONCLUSIONE . M.C.D.(88,34)=2 & 2 = 88(-5) + 34(13) il M.C.D. (88,34)=2, scritto come comb.lin. di 88 e 34.

Ho giustificato ogni passaggio, anche il più scontato, per mettere bene in evidenza le sostituzioni (′spontanee′) da farsi !

b)Stabilire se 88x+34y=10 ha soluzioni intere e, in caso affermativo determinarle tutte.

Geometricamente nel piano reale R 2 l’equazione 88x+34y=10 rappresenta una retta, di cui stiamo cercando i punti a coordinate intere, se ci sono ! (Le equazioni diofantee lineari sono equazioni di I°grado a coefficienti in Z che vengono risolte in Z)

Da a) abbiamo trovato due interi x e y tali che 88x+34y=2 (*) La domanda è :stabilire se 88x+34y=10 ha soluzioni intere.

E’ facile rispondere! Basta moltiplicare per 5 ! Ma se non aves- simo trovato una soluzione intera di (*) ricordiamo che si ha:

♦ L'equazione ax+by=c, con a,b∈Z, c∈Z * ha soluzioni in Z ⇔ M.C.D. (a,b) divide c 2=M.C.D.(88,34) divide 10 ⇒ l’eq.

ha sol.

intere

♦ Cerchiamo ora una soluzione dell’eq. data. In a)

abbiamo trovato l’identità di Bezout: 88(-5) + 34(13) = 2 Come detto, se moltiplichiamo l’uguaglianza per 5

troviamo:

R

R

∃ P(a,b)∈Z

su r ?

Geometricamente nel piano reale R ² l’equazione 88x+34y=10 rappresenta una retta, di cui stiamo cercando i punti a coordinate intere, se ci sono ! (Le equazioni diofantee lineari sono equazioni di I°grado a coefficienti in Z che vengono risolte in Z)

♦ L'equazione ax+by=c, con a,b∈Z, c∈Z ^* ha soluzioni in Z ⇔ M.C.D. (a,b) divide c 2=M.C.D.(88,34) divide 10 ⇒ l’eq.

b) Trovare M.C.D. ( 2 ² ⋅ 3 ³ ⋅ 7, 14076) senza scomporre in fattori primi 14076 e senza calcolatrice !

l’eq. ^ne 2039x+2009y=30 ha sol. ⁿⁱ in Z d=M.C.D. (2009,2039) divide 30 d h =30 con h ∈Z

=> M.C.D.( 2 ² ⋅3 ³ ⋅7, 14076)=2 ² ⋅ 3 ² = 36.