Cómo demostrar por inducción que el máximo común divisor de dos números es una combinación lineal de esos números

Answer 1

Definición: El máximo común divisor (mcd) de a y b, denotado por (a, b), es el mayor divisor común de los enteros ay b.

Teorema: si [math] a, b [/ math] son ​​enteros distintos de cero, entonces su mcd es una combinación lineal de [math] a [/ math] y [math] b [/ math], es decir, existen números enteros [ matemática] s [/ matemática] y [matemática] t [/ matemática] tal que [matemática] sa + tb = (a, b) [/ matemática].

Prueba: Sea [math] d [/ math] el número entero menos positivo que es una combinación lineal de a y b. Escribimos [math] d = sa + tb [/ math], donde syt son enteros. (1)

Primero tenemos que demostrar que [matemáticas] d | a [/ matemáticas]. Por el algoritmo de división tenemos [matemáticas] a = dq + r [/ matemáticas], donde 0 ≤ r <d.

De esto y (1) se deduce que [matemáticas] r = a – q (sa + tb) = a (1 – qs) + b (-qt) [/ matemáticas].

Esto muestra que r es una combinación lineal de a y b. Como 0 ≤ r <d, y d es la combinación lineal menos positiva de a y b, concluimos que r = 0 y, por lo tanto, d | a.

De manera similar, podemos mostrar que d | si. Hemos demostrado que d es un divisor común de a y b. Ahora mostramos que d es el máximo divisor común de a y b. Suponga lo contrario que [matemáticas] (a, b) = D [/ matemáticas] y [matemáticas] D> d [/ matemáticas]. Desde D | a, D | b, y [matemáticas] d = sa + tb [/ matemáticas], se deduce que D | d, por lo tanto D ≤ d. Obtenemos una contradicción. Entonces, [math] d [/ math] es el máximo común divisor de a y by esto concluye la prueba.