Caminar la recta a pasos de a y de b, y ver dónde se puede llegar
Cualquier número de la forma a·x + b·y, donde x e y son enteros. Nada de fracciones. La palabra “lineal” es sólo porque a y b aparecen elevados a la uno, multiplicados por un coeficiente y sumados.
Arrancás en el 0. Das x pasos de largo a y después y pasos de largo b. Donde caés es la combinación lineal. Un coeficiente negativo son los mismos pasos pero para el otro lado: eso es todo lo que aporta el permitir enteros negativos.
Si d divide a a y a b, entonces divide a a·x + b·y — todo el camino está hecho de bloques de largo d. Por eso todo destino posible es múltiplo del mcd(a, b): son los puntos cyan del eje. Movés x e y como quieras y nunca vas a caer entre dos de ellos.
Son dos cosas en una. Primero: existe un divisor común d de a y b que se puede escribir como d = ax + by. Segundo: ese d no es uno cualquiera, es el mejor posible — cada divisor común de a y b divide a d. Apretá solve y el botón te da un par (x, y) que aterriza exactamente ahí.
Acá está el detalle que cuesta ver: la inducción no es sobre a, ni sobre b, sino sobre la suma n = a + b. Los pares se ordenan por esa suma, y la hipótesis inductiva es: “el teorema ya vale para todos los pares cuya suma es 0, 1, …, n − 1”. Es inducción fuerte otra vez, igual que en el 1.5, sólo que lo que baja es la suma y no el número.El caso base es n = 0: si a + b = 0 con los dos no negativos, entonces a = b = 0, y sirve d = 0 con x = y = 0.
Que el enunciado no cambia si das vuelta a y b: como ax + by es lo mismo que by + ax, probar el teorema para el par (a, b) es exactamente lo mismo que probarlo para (b, a) — sólo cambian de nombre los coeficientes.Entonces Apostol se ahorra la mitad del trabajo: alcanza con demostrarlo suponiendo a ≥ b, porque si te tocara a < b los renombrás y caés en el caso ya probado. No es un paso matemático profundo: es literalmente “llamemos a al más grande”.
Con a ≥ b hay dos casos. Si b = 0, listo: a se divide a sí mismo y divide al 0, así que d = a con x = 1, y = 0.Si b ≥ 1, mirás el par (a − b, b). Su suma es (a − b) + b = a = n − b ≤ n − 1, y ahí está todo el truco: restar hizo bajar la suma, así que la hipótesis inductiva ya se le aplica. Te da un d divisor común de a − b y b, de la forma d = (a − b)x + by.Ese d divide a (a − b) y a b, así que divide a la suma (a − b) + b = a: ya es divisor común de a y b. Y en cuanto a la forma, se reacomoda solo: (a − b)x + by = ax − bx + by = ax + (y − x)b. Combinación lineal de a y b, como pedía el enunciado.
Esto es la demostración corriendo para a = 20, b = 12. En cada renglón se resta y se reordena para que el primero sea el más grande — la suma baja siempre, y por eso la cadena no puede ser infinita:(20, 12) suma 32(12, 8) suma 20(8, 4) suma 12(4, 4) suma 8(4, 0) suma 4 → b = 0, d = 4Después se desanda la cadena: cada vuelta atrás convierte los coeficientes con d = ax + (y − x)b. Para 12 y 20 el resultado es 12 · 2 + 20 · (−1) = 4, que es justo lo que te muestra el botón solve. Si esto te suena al algoritmo de Euclides, es porque es el algoritmo de Euclides, hecho con restas en vez de divisiones.
Falta ver que cada divisor común divide a d, y sale en un renglón: si e divide a a y a b, entonces divide a cualquier combinación lineal de los dos — en particular a ax + by, que es d. Eso es lo que ves en el eje de la página anterior: todos los divisores comunes son divisores del mcd, nunca aparece uno suelto.
Si d = ax + by es divisor común, entonces −d también lo es y también es combinación lineal: −d = a(−x) + b(−y). O sea que el teorema te da siempre dos candidatos, uno de cada signo. Por eso Apostol aclara: de esos dos, al no negativo se lo llama máximo común divisor, y se escribe mcd(a, b) o directamente (a, b).Dice “no negativo” y no “positivo” por un solo caso: a = b = 0, donde el único divisor común de la forma ax + by es el 0.Y cuando (a, b) = 1 se dice que a y b son primos entre sí — es la palabra de Apostol para lo mismo que se suele llamar coprimos. Probá a = 7 y b = 12: el retículo pasa a ser todos los enteros, porque con pasos de 7 y de 12 llegás a cualquier número. Ese caso — ax + by = 1 — es la palanca con la que después se prueba que si un primo divide a un producto, divide a alguno de los factores.
Caminar la recta a pasos de a y de b, y ver dónde se puede llegar
Cualquier número de la forma a·x + b·y, donde x e y son enteros. Nada de fracciones. La palabra “lineal” es sólo porque a y b aparecen elevados a la uno, multiplicados por un coeficiente y sumados.
Arrancás en el 0. Das x pasos de largo a y después y pasos de largo b. Donde caés es la combinación lineal. Un coeficiente negativo son los mismos pasos pero para el otro lado: eso es todo lo que aporta el permitir enteros negativos.
Si d divide a a y a b, entonces divide a a·x + b·y — todo el camino está hecho de bloques de largo d. Por eso todo destino posible es múltiplo del mcd(a, b): son los puntos cyan del eje. Movés x e y como quieras y nunca vas a caer entre dos de ellos.
Son dos cosas en una. Primero: existe un divisor común d de a y b que se puede escribir como d = ax + by. Segundo: ese d no es uno cualquiera, es el mejor posible — cada divisor común de a y b divide a d. Apretá solve y el botón te da un par (x, y) que aterriza exactamente ahí.
Acá está el detalle que cuesta ver: la inducción no es sobre a, ni sobre b, sino sobre la suma n = a + b. Los pares se ordenan por esa suma, y la hipótesis inductiva es: “el teorema ya vale para todos los pares cuya suma es 0, 1, …, n − 1”. Es inducción fuerte otra vez, igual que en el 1.5, sólo que lo que baja es la suma y no el número.El caso base es n = 0: si a + b = 0 con los dos no negativos, entonces a = b = 0, y sirve d = 0 con x = y = 0.
Que el enunciado no cambia si das vuelta a y b: como ax + by es lo mismo que by + ax, probar el teorema para el par (a, b) es exactamente lo mismo que probarlo para (b, a) — sólo cambian de nombre los coeficientes.Entonces Apostol se ahorra la mitad del trabajo: alcanza con demostrarlo suponiendo a ≥ b, porque si te tocara a < b los renombrás y caés en el caso ya probado. No es un paso matemático profundo: es literalmente “llamemos a al más grande”.
Con a ≥ b hay dos casos. Si b = 0, listo: a se divide a sí mismo y divide al 0, así que d = a con x = 1, y = 0.Si b ≥ 1, mirás el par (a − b, b). Su suma es (a − b) + b = a = n − b ≤ n − 1, y ahí está todo el truco: restar hizo bajar la suma, así que la hipótesis inductiva ya se le aplica. Te da un d divisor común de a − b y b, de la forma d = (a − b)x + by.Ese d divide a (a − b) y a b, así que divide a la suma (a − b) + b = a: ya es divisor común de a y b. Y en cuanto a la forma, se reacomoda solo: (a − b)x + by = ax − bx + by = ax + (y − x)b. Combinación lineal de a y b, como pedía el enunciado.
Esto es la demostración corriendo para a = 20, b = 12. En cada renglón se resta y se reordena para que el primero sea el más grande — la suma baja siempre, y por eso la cadena no puede ser infinita:(20, 12) suma 32(12, 8) suma 20(8, 4) suma 12(4, 4) suma 8(4, 0) suma 4 → b = 0, d = 4Después se desanda la cadena: cada vuelta atrás convierte los coeficientes con d = ax + (y − x)b. Para 12 y 20 el resultado es 12 · 2 + 20 · (−1) = 4, que es justo lo que te muestra el botón solve. Si esto te suena al algoritmo de Euclides, es porque es el algoritmo de Euclides, hecho con restas en vez de divisiones.
Falta ver que cada divisor común divide a d, y sale en un renglón: si e divide a a y a b, entonces divide a cualquier combinación lineal de los dos — en particular a ax + by, que es d. Eso es lo que ves en el eje de la página anterior: todos los divisores comunes son divisores del mcd, nunca aparece uno suelto.
Si d = ax + by es divisor común, entonces −d también lo es y también es combinación lineal: −d = a(−x) + b(−y). O sea que el teorema te da siempre dos candidatos, uno de cada signo. Por eso Apostol aclara: de esos dos, al no negativo se lo llama máximo común divisor, y se escribe mcd(a, b) o directamente (a, b).Dice “no negativo” y no “positivo” por un solo caso: a = b = 0, donde el único divisor común de la forma ax + by es el 0.Y cuando (a, b) = 1 se dice que a y b son primos entre sí — es la palabra de Apostol para lo mismo que se suele llamar coprimos. Probá a = 7 y b = 12: el retículo pasa a ser todos los enteros, porque con pasos de 7 y de 12 llegás a cualquier número. Ese caso — ax + by = 1 — es la palanca con la que después se prueba que si un primo divide a un producto, divide a alguno de los factores.
Visitá la versión desktop para ver la visualización interactiva 3D