Cómo entender por qué el algoritmo de Euclides para GCD es verdadero

Answer 1

No puedes probar nada con un ejemplo; necesitas una idea general que funcione para cualquier caso. Sin embargo, un ejemplo específico es a menudo una excelente manera de ilustrar una idea más general y ganar intuición. Si el ejemplo es lo suficientemente “general”, entonces la prueba real debe quedar clara a través del ejemplo. Euclides a menudo escribe pruebas de esta manera, a través de la ilustración de un ejemplo general.

Euclides afirma que el mayor número que divide a A y B, donde A> B, es el mismo que el mayor número que divide a B y AB.
Considere A = 30 y B = 9
En este caso, Euclides afirma que gcd (30, 9) = gcd (9, 21).
¿Por qué esto es tan?
Primero tenga en cuenta que si un número divide tanto 30 como 9, entonces también divide 30-9. (Esta parte necesita ser probada en general para dos números cualquiera, no tan difícil).

Entonces, cualquier número que divida tanto 30 como 9, también divide 9 y 21. Esto es cierto para cualquier número, así que seguramente es cierto para el número más grande que divide 30 y 9.
Ahora sabemos que el número más grande (llámelo B) que divide 30 y 9 también divide 9 y 21.
Lo único que queda por mostrar es que no hay un número mayor que B que divida 9 y 21. Una vez que hacemos esto, sabemos que B es el número más grande que divide 21 y 9.
Con este fin, tenga en cuenta que si hubiera un número mayor que B que dividiera (30-21) y 21, ese número también dividiría 30 y 21. (Esta parte debe demostrarse en general para dos números cualquiera, no tan difícil) )

Por lo tanto, el mcd (30,21) = mcd (30-21, 21) = mcd (9, 21).

Answer 2

Intuitivamente (es decir, no tan estrictamente formulado), es así.

Supongamos que [matemáticas] b> a [/ matemáticas]. Esto significa que puede representar [matemática] b = q * a + r [/ matemática] para no [cero] matemática q [/ matemática] y [matemática] r

Este algoritmo encuentra un denominador común. ¿Cómo podemos ver que es el máximo común denominador?

Si [math] d [/ math] es el MCD de [math] a [/ math] y [math] r [/ math], significa [math] a = c * d [/ math] y [math ] r = e * d [/ math], donde [math] c [/ math] y [math] e [/ math] son ​​números primos (no tienen divisores comunes). Esto significa que [matemáticas] b = q * c * d + e * d = d * (q * c + e) ​​[/ matemáticas]. Entonces, si [matemática] b [/ matemática] comparte un divisor mayor que [matemática] d [/ matemática] con [matemática] a [/ matemática], debe ser un múltiplo de [matemática] d [/ matemática], y significa que [math] q * c + e [/ math] y [math] c [/ math] tienen un divisor común. Supongamos que es [matemática] f> 1 [/ matemática] tal que [matemática] c = f * g [/ matemática]. Eso significa [matemáticas] q * c + e = q * f * g + e = f * (q * g + h) [/ matemáticas] para algunas [matemáticas] h [/ matemáticas]. Esta última afirmación requiere que [math] e [/ math] tenga un factor común con [math] c [/ math], lo que contradice el resultado de que son primos.

Answer 3

Supongamos que b> a y mcd (a, b) es algún número k. Entonces, por definición, b / k es un número entero y también lo es a / k. b / k – a / k también es un entero ya que es la diferencia entre dos enteros. a / k y (ba) / k son ambos enteros, por lo que k es un divisor de a y (ba).

Ahora considere a / k y b / k. Estos dos enteros son coprimos (si no lo fueran, k no sería el mcd de ayb). Supongamos que (ba) / k y a / k comparten un factor común j. Entonces, su suma (ba) / k + a / k = b / k también debe ser divisible por j. Como sabíamos que a / k y b / k son coprimos, esta suposición era incorrecta y (ba) / k y a / k no comparten factores comunes.

Como k es un divisor de a y ba y a / k y (ba) / k no comparten factores comunes, k debe ser el mcd de ay ba.

Answer 4

Tenga en cuenta que cualquier divisor común de [matemática] a [/ matemática] y [matemática] b [/ matemática] debe ser algún número [matemática] d [/ matemática] de modo que existan enteros positivos [matemática] a ‘[/ matemática] y [matemática] b ‘[/ matemática] tal que [matemática] a = d \ veces a’ [/ matemática] y [matemática] b = d \ veces b ‘[/ matemática].

Ahora, echemos un vistazo a [math] (ba) [/ math]. Podemos reescribir esto como [math] (d \ times b ‘- d \ times a’) = d \ times (b ‘- a’) [/ math], lo que significa que [math] d [/ math] también debe ser un divisor de [matemáticas] b [/ matemáticas] y [matemáticas] a [/ matemáticas]. Esto es válido para cualquier divisor común de [math] a [/ math] y [math] b [/ math], por lo que también debe ser válido para el máximo divisor común.

Si observamos los dos números [matemática] a, b [/ matemática] y la comparamos con los dos números [matemática] ba, a [/ matemática], en el segundo caso, el mayor de los dos números será menor que para [matemáticas] a, b [/ matemáticas]. Esto significa que convertimos [matemáticas] a, b [/ matemáticas] en dos números con los mismos divisores comunes, pero que son más pequeños. Solo podemos repetir este proceso un número limitado de veces antes de que uno de nuestros dos números se convierta en 0. Cada número entero es un divisor de 0, por lo que el otro número que nos queda debe ser el máximo común divisor de 0 y en sí mismo, y a través del proceso utilizamos, eso significa que debe ser el máximo divisor común de todas las parejas de números que encontramos en el camino.