Algoritmo di Euclide - teorema di Bezout

Algoritmo di Euclide

MCD (300, 18)

1. Vedo se 18 divide perfettamente 300.
2. 300 = 18 · 16 + 12.
3. Cerca il MCD tra 18 e 12.

MCD (18, 12)

18 = 1 · 12 + 6

= MCD (12, 6) = 6

12 = 2 · 6 + 0

Sono a, b ∈ N⁺ con a ≥ b

1. Repeat
2. r := a mod b
3. if r = 0 then
4. return b
5. else
6. a := b
7. b := r
8. endif
9. forever

Notiamo che l'iterazione "2" può essere ripetuta.

a_i, b_i, r_i = valori di a, b, r all’iterazione i-ma

(dopo aver ripetuto "i" volte la riga i-ma)

a₁ = a, b₁ = b, r₁ = a mod b

a₂ = b₁, b₂ = r₁, r₂ = a₂ mod b₂

a_i = b_i-1, b_i = r_i-1, r_i = a_i mod b_i

...

a_i-2 b_i-2 r_i-2

a_i-1 b_i-1 r_i-1

a_i b_i r_i

Algoritmo di Euclide

MCD (300, 18)

1. Vedo se 18 divide perfettamente 300.
2. 300 = 18 · 16 + 12.
3. Cerca il MCD tra 18 e 12.
4. MCD (18, 12): 18 = 1 · 12 + 6
5. = MCD (12, 6) = 6
6. 12 = 2 · 6 + 0

Sono a, b ∈ N⁺ con a ≥ b

1. Repeat
2. r := a mod b
3. if r = 0 then
4. return b /* b è il MCD */
5. else
6. a := b
7. b := r
8. endif
9. forever

Notiamo che l'iterazione "2" può essere ripetuta.

a_i, b_i, r_i = valori di a, b, r all'iterazione i-ma

(dopo aver ripetuto "i" volte la riga i-ma)

a₁ = a, b₁ = b, r₁ = a mod b

a₂ = b₁, b₂ = r₁, r₂ = a₂ mod b₂

a_i = b_i-1, b_i = r_i-1, r_i = a_i mod b_i

a_i = b_i-1 = r_i-2

r_i = a_i mod b_i

= a_i mod r_i-1

..._i che l'algoritmo deve terminare

I divisori di a_i e b_i sono gli stessi dei divisori comuni di a_i-1 b_i-1.

C_i = divisori comuni a_i e b_i

C_i-1 = divisori comuni a_i-1 e b_i-1

Lemma

Lemma: ∀ i ≥ 2, C_i = C_i-1

(⊆) Se c ∈ C_i, ossia c | b_i-1 c | r_i-1, vogliamo dimostrare c | a_i-1.

Abbiamo a_i-1 = q b_i-1 + r_i-1

= q b_i + bi

= qmc + nc (∃ m, n)

= (qm+n)c

c | a_i-1 => c ∈ C_i-1

∀ i ≥ 2, C_i = C_i-1

(⊇) Se c ∈ C_i-1, ossia c | a_i-1 c | a_i, vogliamo dimostrare c | a_i, c | b_i.

a_i-1 = q b_i-1 + r_i-1

= q b_i-1 + b_i

b_i = a_i-1 - q b_i-1 = m c - qnc

= (m - qn)c (∃ m, n)

c | b_i

Esempi di MCD

MCD (88, 55) = 11

= MCD (55, 33)

= MCD (33, 22)

= MCD (22, 11)

= MCD (89, 55) = 1

= MCD (55, 34)

= MCD (34, 21)

= MCD (21, 13)

= MCD (13, 8)

= MCD (8, 5)

= MCD (5, 3)

= MCD (3, 2)

= MCD (2, 1)

88 = 1.55 + 33

55 = 1.33 + 22

33 = 1.22 + 11

22 = 2.11 + 0

89 = 1.55 + 34

55 = 1.34 + 21

34 = 1.21 + 13

21 = 1.13 + 8

13 = 1.8 + 5

8 = 1.5 + 3

5 = 1.3 + 2

3 = 1.2 + 1

2 = 2.1 + 0

r_i < r_i−1

r_i ≤ r_i−1 − 1

Dimostrazione

Dimostrazione:

a_i b_i r_i

a_i+1 b_i+1 r_i+1

a_i+2 b_i+2 r_i+2

r_i+2 < r_i/2

1. r_i+2 < r_i+1
2. r_i+2 = r_i − q r_i+1 ≤ r_i − r_i+1

q_i+2 = q b_i+2 + r_i+2

r_i+2 ≤ r_i− r_i+1

(1) + (2) = 2 r_i+2 < r_i+1 + r_i − r_i+1