Algoritmo d’Euclide

(1)

Algoritmo d’Euclide

Progetto Lauree Scientifiche

prof.Sandro Pistori

L.S.S: “G. Galilei”

30 Gennaio 2007

(2)

Algoritmo Euclideo

Prendiamo a, b interi con a, b > 0 e supponiamo 0 < a < b.

Dividiamo b per a, avremo che:

b = q

1

· a + r

₁

, con 0 ≤ r

1

≤ a.

Osserviamo che

1

se r

₁

= 0, allora b = q

₁

· a e abbiamo gi´ a che MCD(a, b) = a

2

altrimenti, preso un intero positivo d :

d divide sia a che b, allora divider´ a anche r

1

in quanto combinazione lineare di a e b; infatti r

1

= b − q · a viceversa, se d divide sia a che r

₁

, divider´ a anche b per la stessa propriet` a sopra.

Quindi possiamo concludere che MCD(a, b) =MCD(a, r

₁

), con il

vantaggio che r

1

< a < b.

(3)

Algoritmo Euclideo

Prendiamo a, b interi con a, b > 0 e supponiamo 0 < a < b.

Dividiamo b per a, avremo che:

b = q

1

· a + r

₁

, con 0 ≤ r

1

≤ a.

Osserviamo che

1

se r

₁

= 0, allora b = q

₁

· a e abbiamo gi´ a che MCD(a, b) = a

2

altrimenti, preso un intero positivo d :

d divide sia a che b, allora divider´ a anche r

1

in quanto combinazione lineare di a e b; infatti r

1

= b − q · a viceversa, se d divide sia a che r

₁

, divider´ a anche b per la stessa propriet` a sopra.

Quindi possiamo concludere che MCD(a, b) =MCD(a, r

₁

), con il

vantaggio che r

1

< a < b.

(4)

Algoritmo Euclideo

Prendiamo a, b interi con a, b > 0 e supponiamo 0 < a < b.

Dividiamo b per a, avremo che:

b = q

1

· a + r

₁

, con 0 ≤ r

1

≤ a.

Osserviamo che

1

se r

₁

= 0, allora b = q

₁

· a e abbiamo gi´ a che MCD(a, b) = a

2

altrimenti, preso un intero positivo d :

d divide sia a che b, allora divider´ a anche r

1

in quanto combinazione lineare di a e b; infatti r

1

= b − q · a viceversa, se d divide sia a che r

₁

, divider´ a anche b per la stessa propriet` a sopra.

Quindi possiamo concludere che MCD(a, b) =MCD(a, r

₁

), con il

vantaggio che r

1

< a < b.

(5)

Algoritmo Euclideo

Prendiamo a, b interi con a, b > 0 e supponiamo 0 < a < b.

Dividiamo b per a, avremo che:

b = q

1

· a + r

₁

, con 0 ≤ r

1

≤ a.

Osserviamo che

1

se r

₁

= 0, allora b = q

₁

· a e abbiamo gi´ a che MCD(a, b) = a

2

altrimenti, preso un intero positivo d :

d divide sia a che b, allora divider´ a anche r

1

in quanto combinazione lineare di a e b; infatti r

1

= b − q · a

viceversa, se d divide sia a che r

₁

, divider´ a anche b per la stessa propriet` a sopra.

Quindi possiamo concludere che MCD(a, b) =MCD(a, r

₁

), con il

vantaggio che r

1

< a < b.

(6)

Algoritmo Euclideo

Prendiamo a, b interi con a, b > 0 e supponiamo 0 < a < b.

Dividiamo b per a, avremo che:

b = q

1

· a + r

₁

, con 0 ≤ r

1

≤ a.

Osserviamo che

1

se r

₁

= 0, allora b = q

₁

· a e abbiamo gi´ a che MCD(a, b) = a

2

altrimenti, preso un intero positivo d :

d divide sia a che b, allora divider´ a anche r

1

in quanto combinazione lineare di a e b; infatti r

1

= b − q · a viceversa, se d divide sia a che r

1

, divider´ a anche b per la stessa propriet` a sopra.

Quindi possiamo concludere che MCD(a, b) =MCD(a, r

₁

), con il

vantaggio che r

1

< a < b.

(7)

Algoritmo Euclideo

Prendiamo a, b interi con a, b > 0 e supponiamo 0 < a < b.

Dividiamo b per a, avremo che:

b = q

1

· a + r

₁

, con 0 ≤ r

1

≤ a.

Osserviamo che

1

se r

₁

= 0, allora b = q

₁

· a e abbiamo gi´ a che MCD(a, b) = a

2

altrimenti, preso un intero positivo d :

d divide sia a che b, allora divider´ a anche r

1

in quanto combinazione lineare di a e b; infatti r

1

= b − q · a viceversa, se d divide sia a che r

1

, divider´ a anche b per la stessa propriet` a sopra.

Quindi possiamo concludere che MCD(a, b) =MCD(a, r

₁

), con il

vantaggio che r

1

< a < b.

(8)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(9)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(10)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(11)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(12)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(13)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(14)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(15)

Algoritmo Euclideo

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r

1

con r

1

< a:

a = q

2

· r

₁

+ r

2

, con 0 ≤ r

2

< r

1

dove

se r

₂

= 0, si ha che r

₁

divide a, quindi MCD(a, b) =MCD(a, r

₁

) = r

₁

;

altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a, b) =MCD(a, r

₁

) =MCD(r

₁

, r

₂

).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i -esima iterazione dove

r

i

− 1 = q

_i

+ 1 · r

i

+ r

i +1

, con 0 ≤ r

i +1

< r

i

e avremo che

se r

_i

= 0, allora MCD(a, b) = r

_{i −1}

;

altrimenti, continuiamo il procedimento

(16)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili. Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427 560 = 1 · 427 + 133 427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7

21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(17)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo. 1547 = 2 · 560 + 427

560 = 1 · 427 + 133 427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7

21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(18)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427

560 = 1 · 427 + 133 427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7

21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(19)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427 560 = 1 · 427 + 133

427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7

21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(20)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427 560 = 1 · 427 + 133 427 = 3 · 133 + 28

133 = 4 · 28 + 21

28 = 1 · 21 + 7

21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(21)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427 560 = 1 · 427 + 133 427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7

21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(22)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427 560 = 1 · 427 + 133 427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7

21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(23)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427 560 = 1 · 427 + 133 427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7 21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(24)

Algoritmo Euclideo

Poich´ e gli r

i

sono interi non negativi e la successione di resti ´ e decrescente, ad un certo punto ci dovremo fermare, cio´ e esister´ a un r

n

diverso da zero tale che r

n+1

= 0, allora il nostro MCD(a, b) sar´ a uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento ´ e vantaggioso perch´ e non dobbiamo

scomporre in fattori primi e si utilizzano divisioni sempre pi´ u facili.

Esempio: Calcolare (1547, 560) utilizzando l’Algoritmo Euclideo.

1547 = 2 · 560 + 427 560 = 1 · 427 + 133 427 = 3 · 133 + 28 133 = 4 · 28 + 21

28 = 1 · 21 + 7 21 = 3 · 7 + 0.

e quindi MCD(1547, 560) = 7.

(25)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(26)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(27)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(28)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(29)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(30)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

)

= (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(31)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(32)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.

Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(33)

Algoritmo Euclideo

Teorema di Euclide esteso (Formula di Bezout) Sia d = (a, b), a > b. Allora esistono u, v ∈ Z tali che

d = u · a + v · b

Proviamo ora a ricostruire u, v procedendo a ritroso nell’algoritmo euclideo: presi MCD(a, b) = r

_{i −1}

e u · a + v · b = r

_{i −1}

, possiamo scrivere

r

i −1

= r

i −3

–q

i −1

· r

_{i −2}

e andiamo sostituire il valore di r

_{i −2}

che si ricava dall’uguaglianza r

_{i −4}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −2}

⇒ r

_{i −2}

= q

_{i −2}

· r

_{i −3}

+ r

_{i −4}

r

_{i −1}

= r

_{i −3}

–q

_{i −1}

· (r

_{i −4}

–q

_{i −2}

· r

_{i −3}

) = (1 + q

_{i −1}

· q

_{i −2}

) · r

_{i −3}

–q

_{i −1}

· r

_{i −4}

Ora sostituiamo in questa equazione il valore di r

_{i −3}

che si ottiene

da r

_{i −5}

= q

_{i −3}

· r

_{i −4}

+ r

_{i −3}

e avremo r

_{i −1}

come espressione in r

_{i −3}

e r

i −4

.Quindi andremo a sostituire r

i −3

e continueremo questo

procedimento fino ad ottenere r

_{i −1}

come combinazione lineare dei

soli a e b.

(34)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560

da cui segue u = 21 e v = −58.

(35)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560

da cui segue u = 21 e v = −58.

(36)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560

da cui segue u = 21 e v = −58.

(37)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560

da cui segue u = 21 e v = −58.

(38)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560

da cui segue u = 21 e v = −58.

(39)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560

da cui segue u = 21 e v = −58.

(40)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560 da cui segue

u = 21 e v = −58.

(41)

Algoritmo Euclideo

Con i dati dell’esempio precedente:

7 = 28 − 1 · 21 = 28 − 1 · (133 − 4 · 28)

= 5 · 28 − 1 · 133 = 5(427 − 3 · 133) − 1 · 133

= 5 · 427 − 16 · 133 = 5 · 427 − 16(560 − 1 · 427)

= 21 · 427 − 16 · 560 = 21 · (1547 − 2 · 560) − 16 · 560

= 21 · 1547 − 58 · 560

da cui segue u = 21 e v = −58.

(42)

Algoritmo Euclideo

Gli elementi a di Z

n

che hanno inverso moltiplicativo sono tutti e soli quelli per cui (a, n) = 1.

a · x = 1(modn) se e solo se (a, n) = 1 Dim:

Sia d = (a, n). Se d > 1 non pu´ o esistere un b tale che

a · b = 1(modn) perch´ e si avrebbe che d divide (ab − 1) e quindi, siccome d divide a, d divide 1 che ´ e contraddittorio con l’assunzione d > 1.

Allora d = 1.

Suppongo, senza ledere, che a < n. Utilizzando l’Algoritmo Euclideo, sappiamo che esistono u, v tali che u · a + v · n = 1 e quindi l’inverso di a ´ e esattamente u dal momento che

u · a = 1 − v · n

(43)

Algoritmo Euclideo

Gli elementi a di Z

n

che hanno inverso moltiplicativo sono tutti e soli quelli per cui (a, n) = 1.

a · x = 1(modn) se e solo se (a, n) = 1

Dim:

Sia d = (a, n). Se d > 1 non pu´ o esistere un b tale che

a · b = 1(modn) perch´ e si avrebbe che d divide (ab − 1) e quindi, siccome d divide a, d divide 1 che ´ e contraddittorio con l’assunzione d > 1.

Allora d = 1.

Suppongo, senza ledere, che a < n. Utilizzando l’Algoritmo Euclideo, sappiamo che esistono u, v tali che u · a + v · n = 1 e quindi l’inverso di a ´ e esattamente u dal momento che

u · a = 1 − v · n

(44)

Algoritmo Euclideo

Gli elementi a di Z

n

che hanno inverso moltiplicativo sono tutti e soli quelli per cui (a, n) = 1.

a · x = 1(modn) se e solo se (a, n) = 1 Dim:

Sia d = (a, n). Se d > 1 non pu´ o esistere un b tale che

a · b = 1(modn) perch´ e si avrebbe che d divide (ab − 1) e quindi, siccome d divide a, d divide 1 che ´ e contraddittorio con l’assunzione d > 1.

Allora d = 1.

Suppongo, senza ledere, che a < n. Utilizzando l’Algoritmo Euclideo, sappiamo che esistono u, v tali che u · a + v · n = 1 e quindi l’inverso di a ´ e esattamente u dal momento che

u · a = 1 − v · n

(45)

Algoritmo Euclideo

Gli elementi a di Z

n

che hanno inverso moltiplicativo sono tutti e soli quelli per cui (a, n) = 1.

a · x = 1(modn) se e solo se (a, n) = 1 Dim:

Sia d = (a, n). Se d > 1 non pu´ o esistere un b tale che

a · b = 1(modn) perch´ e si avrebbe che d divide (ab − 1) e quindi, siccome d divide a, d divide 1 che ´ e contraddittorio con l’assunzione d > 1.

Allora d = 1.

Suppongo, senza ledere, che a < n. Utilizzando l’Algoritmo Euclideo, sappiamo che esistono u, v tali che u · a + v · n = 1 e quindi l’inverso di a ´ e esattamente u dal momento che

u · a = 1 − v · n

(46)

Algoritmo Euclideo

Gli elementi a di Z

n

che hanno inverso moltiplicativo sono tutti e soli quelli per cui (a, n) = 1.

a · x = 1(modn) se e solo se (a, n) = 1 Dim:

Sia d = (a, n). Se d > 1 non pu´ o esistere un b tale che

a · b = 1(modn) perch´ e si avrebbe che d divide (ab − 1) e quindi, siccome d divide a, d divide 1 che ´ e contraddittorio con l’assunzione d > 1.

Allora d = 1.

Suppongo, senza ledere, che a < n. Utilizzando l’Algoritmo Euclideo, sappiamo che esistono u, v tali che u · a + v · n = 1 e quindi l’inverso di a ´ e esattamente u dal momento che

u · a = 1 − v · n