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 e b due numeri naturali, con a maggiore o uguale a b e b diverso da zero. Esistono e sono unici due numeri naturali q, detto quoziente, e r, detto resto, tali che:

a = qb + r

e con r maggiore o uguale a zero e r strettamente minore di b.

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

19 = 3 x 5 + 4