Prueba del principio de división euclidiana

El principio de la división euclidiana se demuestra de la siguiente manera:

Primero divide un número menor por un número mayor para obtener el primer resto, luego divide el número menor por el primer resto, obtén; el segundo resto; divida el primer resto por el segundo resto, obtenga el tercer resto.

De esta forma se divide el resto anterior por el último número uno a uno hasta que el resto sea 0. Entonces, el último divisor es el máximo común divisor buscado (si el último divisor es 1, entonces los dos números originales son primos relativos).

Por ejemplo, para encontrar el máximo común divisor de 1515 y 600, la primera vez: divide 1515 entre 600, y el cociente de 2 será 315; la segunda vez: divide 600 entre 315, y el el cociente de 1 será 285 la tercera vez: usa Dividir 285 entre 315, y el cociente de 1 será 30 la cuarta vez: divide 285 entre 30, y el cociente de 9 será 15; por 15, y el cociente de 2 será 0. El máximo común divisor de 1515 y 600 es 15.

La división euclidiana es un método para encontrar el máximo común divisor de dos números. Si desea encontrar el máximo común divisor de varios números, primero puede encontrar el máximo común divisor de dos números y luego encontrar el máximo común divisor de este máximo común divisor y el tercer número. Continúe de esta manera hasta el último número. El máximo común divisor final obtenido es el máximo común divisor de los números requeridos.

El método de división euclidiana se deriva del algoritmo euclidiano. El principio básico es el siguiente: si necesita el máximo común divisor de dos enteros positivos a y b (suponiendo agt; b, de hecho esto no afecta el algoritmo de solución), se puede expresar como la siguiente fórmula: a=b ×q r (1) donde , q representa el cociente obtenido al dividir a por b, y r representa el resto.