Permette di calcolare il massimo comun divisore di due numeri

interi positivi a e b senza doverli scomporre in fattori primi.

Supponiamo che b sia il maggiore dei due numeri e cominciamo

col dividere b per a scrivendo:

                                 

Se r₁ = 0 allora a divide b e il massimo comun divisore tra a e b

è dato proprio da a. Supponiamo che r₁ sia non nullo.

Ogni divisore comune di a e r₁ dividerà anche b, essendo b una

combinazione lineare di a e r₁. Viceversa si ha che r₁ = b - q₁a  e

quindi ogni divisore comune di a e b dividerà anche r₁.

Ne segue che il massimo comun divisore di a e b è anche il

massimo comun divisore di a e r₁. Dividiamo ora per r₁:

                               

Se r₂ = 0 allora M.C.D.(a, b) = M.C.D.(a, r₁) = r₁, altrimenti:

M.C.D.(a, b) = M.C.D.(a, r₁) = M.C.D.(r₁, r₂).

Continuando in questo modo, siccome r_i continua a decrescere,

dovremo raggiungere il punto in cui il resto è 0. Se r_m è l’ultimo

resto diverso da 0, allora r_m sarà il massimo comun divisore tra a e b.