¿Qué es el método de reducción de fase? ¿Cuál es su principio?

La técnica de reducción de fases, o "método de eucración y división", se utiliza para encontrar el máximo común divisor. Dados dos enteros positivos a y b, divida a por b para obtener el cociente a0 y el resto r, escrito como la fórmula: a=a0b+r, 0≤rr>r1>r2>... gradualmente se vuelve más pequeño y todos son números enteros positivos, el máximo común divisor d de ayb se puede encontrar después de pasos finitos (puede ser 1). Este es el famoso método de división euclidiana, que en el extranjero se denomina algoritmo euclidiano. Ejemplo: Encuentre el máximo común divisor de 42897 y 18644: 42897=2×18644+5609, (i) 18644=3×5609+1817, (ii) 5609=3×1817+158, (iii) 1817=11×158 + 79, (iv) 158=2×79． Por lo tanto, el máximo común divisor de 42897 y 18644 = 79