¿En qué se dividen las etapas?

La sustitución y división, también llamada algoritmo euclidiano, es un algoritmo para encontrar el máximo común divisor de dos números enteros positivos. Es el algoritmo más antiguo conocido, que data de hace 3.000 años.

Supongamos que los dos números son a y b (a > B), los pasos para encontrar el máximo común divisor (A, B) de A y B son los siguientes: divide A entre B para obtener A ÷ B = Q...r1 (0 ≤ r1). Si r1=0, entonces (a, b) = b; si r1≠0, entonces divida por r1 para obtener b ÷ r1 = q...r2 (0 ≤ R2). Si r2=0, entonces (a, b)=r1, si R2 \. El último dividendo es el resto del dividendo y el divisor es (a, b).

Por ejemplo: a=25, b=15, A/B = 1...10, B/10 = 1...5, 10/5 = 2...