¿Podrían ayudarme con el siguiente problema: "suponga que a y b son enteros positivos arbitrarios, tales que a < b, para demostrar la siguiente...

¿Qué significa ser el "MCD" = Máximo Común Divisor? Que es divisor y que es el máximo de todos los divisores comunes. Llamémoslo m.

m = mcd(a, b)

Que sea divisor de a y también de b quiere decir que existen c y d enteros positivos tales que:

a = m*c (m es divisor de a, es un factor… m divide a "a" y el resultado de dividir es c)

b = m*d (m es divisor de b, es un factor… m divide a "b" y el resultado de dividir es d)

Que m sea el máximo implica que c y d no tienen divisores comunes (salvo el 1), que son coprimos, que mcd(c, d) = 1.

¿Cuánto es b-a?

Pues b-a = m*d - m*c = m*(d-c)

Es decir, que m seguro que divide a la resta. Y divide a "b" también, luego es divisor común de b y de "b-a".

Solamente falta probar que es el máximo.

¿Podría no ser el máximo? Si no fuese el máximo querría decir que hay algún primo en la descomposición de b y de "b-a" que no está incluido en m.

Es decir,

b=m*d

b-a = m*(d-c)

Para que m no sea el máximo, los números d y "d-c" deberían tener un factor común, un divisor común, distinto del 1. Llamémoslo f.

Esto significaría otros dos números, g y h tales que:

d = f*g

d-c = f*h

Sustituyendo d en la segunda:

(f*g) - c = f*h

Y esto último implicaría

c = f*g - f*h = f*(g-h)

Y antes teníamos

d = f*g

Esto quiere decir que tanto c como d comparten un factor común f … pero, atención, antes dije que c y d eran coprimos, así que no pueden tener c y d un factor común distinto de 1. Y, por tanto, la última suposición que hice, que m no fuese el máximo factor de b y b-a, que era lo mismo que existiese un f distinto de 1, no es cierto. Por tanto, m además de divisor también es el máximo. Con esto concluye la demostración de que

mcd ( a, b ) = mcd ( b, b-a )

Para más datos, esto ya lo había deducido un griego muy listo llamado Euclides hace más de 2200 años. Y si cambias la b, que es el número más grande, por el más pequeño también se cumple, es decir, mcd(a, b) = mcd (a, b-a)

Y como b-a tiene que ser siempre más pequeño que b, esa igualdad lo que hace es pasar de dos números, a y b, a otros màs pequeños. Y si esto se repite tendremos otra pareja de números más pequeños, luego mas pequeños… Este proceso iterativo es lo que se llama Algoritmo de Euclides por restas sucesivas.

Se deja como ejercicio probar la otra parte del problema, que se hace casi casi casi igual. La lógica desde luego es la misma… Probar que

mcd(a, b) = mcd(b, b+a)

Y si haces una practica con el Algoritmo de Euclides ya sería el ejercicio completo.

¿Qué apostamos a que quien hizo la pregunta no va a escribir aquí lo que le he pedido? Y eso que casi solo hay que copiar y pegar, es cosa de menos de 1 minuto… Pues no, que nada, que eso no he visto que lo haga nadie de los que preguntan. Ni siquuera preguntar algo que no entendieron de mi respuesta. Me pregunto si sirve de algo… Sí, preguntador, va por ti, no te hagas el despistado. Por supuesto, si otro quiere decir algo que lo diga, que no se si tendré malas pulgas o mal carácter, de boquilla, pero dar collejas o cachetadas a alguien por Internet todavía no lo he hecho, ni lo volveré a hacer xD xD