Algoritmo euclideo delle divisioni successive

Il matematico greco Euclide (323 a.C. – 285 a.C.) è stato il più importante studioso della storia antica. Egli è noto per i suoi Elementi, un’importantissima opera costituita da 13 libri. Il matematico fu chiamato da Tolomeo I ad Alessandria d’Egitto per operare all’interno della più grande e famosa Biblioteca del mondo antico.

All’interno dei suoi Elementi, Euclide presenta due metodi per il calcolo del M.C.D. di due numeri. Uno di questi due metodi si basa sulle cosiddette “divisioni successive”,  grazie all’esistenza del seguente: 

Teorema (Elementi, VII libro). Siano a,bN, con a ≥ b e b ≠ 0 . Esistono e sono unici due numeri naturali q, detto quoziente, e r, detto resto, tali che:

a = bq + r

e 0 ≤ r < b.

Esempio. Se si considerano i numeri 19 e 5, esistono e sono unici i numeri 3 e 4 tali che:

19 = 3 · 5 + 4

L’algoritmo delle divisioni successive

Se r è il resto della divisione intera di due numeri a,bN, con a > b, allora:

  • se r = 0, si ha che MCD(a, b) = b;
  • se r ≠ 0, si ha che MCD(a, b) = MCD(b, r);

Quindi, per trovare il MCD(a, b) basta eseguire le divisioni finché il resto non sarà uguale a zero.

Esempio. Determinare MCD (72, 16).

72 : 16 = 4 resto 8

Quindi MCD(72, 16) = MCD(16, 8). Ma:

16 : 8 = 2 resto 0

Quindi MCD(72, 16) = 8.

Esercizi. Calcolare il M.C.D. delle seguenti coppie di numeri.

a)    21, 49 b)   76,57 c)    240, 160 d)   80, 78
e)    78, 12 f)     98, 42 g)    102, 18 h)   468, 624

Algoritmo euclideo delle divisioni successive

Print Friendly, PDF & Email



Condividi

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.