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,b ∈ N, 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,b ∈ N, 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
