Una ecuación diofántica lineal pide números enteros, no simplemente números reales. Comparamos la teoría con 18x + 12y = 72, desde el algoritmo de Euclides hasta todas las soluciones. No buscamos una pareja afortunada mediante tanteos: construimos un procedimiento completo y después imponemos las restricciones del problema.
Abrir el laboratorio: introduce a, b y c y sigue todos los pasos
1. Ecuación inicial
| Parte teórica | Ejemplo práctico |
|---|---|
La forma es ax + by = c, con a, b, c ∈ ℤ. Buscamos x, y ∈ ℤ. | 18x + 12y = 72 |
Para el procedimiento principal suponemos a, b ≠ 0. Los coeficientes nulos se tratan al final. | a = 18, b = 12, c = 72 |
2. Cálculo del máximo común divisor
Aplicamos el algoritmo de Euclides: cada división produce un resto menor que el divisor.
| Parte teórica | Ejemplo práctico |
|---|---|
Calculamos d = MCD(|a|,|b|) mediante divisiones sucesivas. | 18 = 12×1 + 6 |
| Dividimos el divisor anterior entre el resto hasta obtener resto cero. | 12 = 6×2 + 0 |
| El último resto distinto de cero es el MCD, tomado positivo. | d = 6 |
3. Comprobación de la existencia de soluciones
| Parte teórica | Ejemplo práctico |
|---|---|
Existen soluciones enteras si y solo si d ∣ c: el MCD divide al término independiente. | 6 ∣ 72 |
Si el MCD no divide a c, no existe ninguna pareja entera. Si lo divide, continuamos. | 72/6 = 12 |
¿Por qué es necesario? Todo ax + by es múltiplo del MCD. ¿Por qué es suficiente? La identidad de Bézout, que construiremos a continuación, produce una solución siempre que c/d sea entero.
4. Euclides extendido e identidad de Bézout
Retroceder por las divisiones significa reescribir los restos como combinaciones de los coeficientes iniciales.
| Parte teórica | Ejemplo práctico |
|---|---|
| Despejamos el último resto no nulo y sustituimos hacia atrás los restos anteriores cuando haga falta. | 6 = 18 - 12 |
Obtenemos dos enteros u, v tales que au + bv = d: es la identidad de Bézout. | 18(1) + 12(-1) = 6 |
Los coeficientes de la combinación obtenida son u y v. | u = 1, v = -1 |
5. Cálculo de una solución particular
Transformamos la identidad de Bézout en la ecuación original multiplicando todo por el mismo número.
| Parte teórica | Ejemplo práctico |
|---|---|
Partimos de au + bv = d. | 18(1) + 12(-1) = 6 |
El multiplicador es m = c/d. | 72/6 = 12 |
Multiplicamos toda la identidad: a(um) + b(vm) = c. | 18(12) + 12(-12) = 72 |
Por tanto, x₀ = u(c/d) e y₀ = v(c/d). | x₀ = 12, y₀ = -12 |
La pareja (12,-12) es correcta aunque una coordenada sea negativa: por ahora buscamos soluciones en ℤ. La no negatividad será un requisito adicional.
6. Demostración de la fórmula general
| Parte teórica | Ejemplo práctico |
|---|---|
| Escribimos la ecuación original. | 18x + 12y = 72 |
| Escribimos la ecuación que satisface la solución particular. | 18(12) + 12(-12) = 72 |
| Restamos miembro a miembro. | 18(x - 12) + 12(y + 12) = 0 |
| Pasamos el segundo término a la derecha. | 18(x - 12) = -12(y + 12) |
Dividimos ambos miembros entre d. | 3(x - 12) = -2(y + 12) |
Tomamos a′ = a/d y b′ = b/d. Son coprimos. De a′(x - x₀) = -b′(y - y₀), por el lema de Euclides, se obtiene b′ ∣ (x - x₀).
Por tanto existe un entero k tal que x - x₀ = b′k. Al sustituir y simplificar, obtenemos y - y₀ = -a′k.
x = x₀ + (b/d)ky = y₀ - (a/d)kk ∈ ℤ
Hemos demostrado que toda solución tiene esta forma. Recíprocamente, al sustituir en la ecuación, los términos con k se cancelan: cada entero k da una solución. No falta ninguna.
7. Aplicación de la fórmula general
| Parte teórica | Ejemplo práctico |
|---|---|
Primera coordenada: x = x₀ + (b/d)k. | x = 12 + (12/6)k |
Segunda coordenada: y = y₀ - (a/d)k. | y = -12 - (18/6)k |
Simplificamos y recordamos que k puede ser cualquier entero. | x = 12 + 2k; y = -12 - 3k; k ∈ ℤ |
Las fórmulas describen infinitas soluciones enteras, incluidas las de coordenadas negativas. Otra solución particular puede dar fórmulas con aspecto distinto, pero representan la misma familia tras desplazar el parámetro.
8. Búsqueda de soluciones no negativas
Si el problema exige cantidades no negativas, imponemos ambas condiciones, no solo una.
| Parte teórica | Ejemplo práctico |
|---|---|
Imponemos x₀ + (b/d)k ≥ 0. | 12 + 2k ≥ 0 ⇒ k ≥ -6 |
Imponemos y₀ - (a/d)k ≥ 0. | -12 - 3k ≥ 0 ⇒ k ≤ -4 |
Intersecamos los intervalos y tomamos únicamente los valores enteros de k. | -6 ≤ k ≤ -4 |
En general, una restricción tiene la forma q + tk ≥ m, con m = 0 para cantidades no negativas y m = 1 para cantidades enteras estrictamente positivas.
- Si
t > 0:k ≥ ⌈(m - q)/t⌉. - Si
t < 0:k ≤ ⌊(m - q)/t⌋; al dividir entre un número negativo cambia el sentido de la desigualdad. - Si
t = 0, comprobamos directamente siq ≥ m.
⌈ ⌉ y ⌊ ⌋ indican redondeo hacia arriba y hacia abajo, respectivamente. Un intervalo vacío significa que no hay soluciones admisibles; con coeficientes de signos opuestos el intervalo puede ser ilimitado.
9. Cálculo de las soluciones
En el ejemplo k ∈ {-6,-5,-4}. Sustituimos cada valor en ambas fórmulas.
| k | x = 12 + 2k | y = -12 - 3k |
|---|---|---|
| -6 | 0 | 6 |
| -5 | 2 | 3 |
| -4 | 4 | 0 |
Las tres soluciones no negativas son (0,6), (2,3), (4,0). Comprobación: 18×0 + 12×6 = 72, 18×2 + 12×3 = 72, 18×4 + 12×0 = 72.
Si exigimos x ≥ 1 e y ≥ 1, solo queda (2,3). «Enteras», «no negativas» y «estrictamente positivas» son tres requisitos distintos.
10. Resumen del método
| Fase | Parte teórica | Ejemplo práctico |
|---|---|---|
| Ecuación | ax + by = c | 18x + 12y = 72 |
| MCD | d = MCD(|a|,|b|) | d = 6 |
| Existencia | d ∣ c | 6 ∣ 72 |
| Bézout | au + bv = d | 18 - 12 = 6 |
| Multiplicador | m = c/d | m = 12 |
| Solución particular | x₀ = um, y₀ = vm | (12,-12) |
| Fórmula general: x | x = x₀ + (b/d)k | x = 12 + 2k |
| Fórmula general: y | y = y₀ - (a/d)k | y = -12 - 3k |
| Restricciones | x, y ≥ 0 | -6 ≤ k ≤ -4 |
| Soluciones | k ∈ ℤ | (0,6), (2,3), (4,0) |
11. Dos tareas distintas, también con números mayores
- Euclides extendido encuentra una solución particular sin tanteos.
- La fórmula general produce todas las demás soluciones variando el parámetro entero
k.
Para 252x + 198y = 900, las divisiones son 252 = 198×1 + 54, 198 = 54×3 + 36, 54 = 36×1 + 18, 36 = 18×2 + 0. El MCD es 18.
Al retroceder obtenemos 18 = 4×252 - 5×198. Multiplicamos por 900/18 = 50: una solución particular es (200,-250). La familia es x = 200 + 11k, y = -250 - 14k.
La no negatividad impone k ≥ -18 y k ≤ -18. Por tanto k = -18 y la única pareja no negativa es (2,2). En el laboratorio puedes cargar este ejemplo y ver cada sustitución hacia atrás.
12. Imposibilidades, signos y coeficientes nulos
Ninguna solución entera: 18x + 12y = 73 es imposible porque 6 no divide a 73. Ninguna solución no negativa: 6x + 10y = 2 tiene la familia x = 2 + 5k, y = -1 - 3k, pero exige simultáneamente k ≥ 0 y k ≤ -1.
Coeficientes negativos: Euclides se aplica a los valores absolutos. Si |a|u′ + |b|v′ = d, basta restablecer los signos en los coeficientes de Bézout para obtener au + bv = d. La fórmula general y las restricciones siguen siendo válidas.
- Si
a = 0yb ≠ 0, hace falta quebdivida ac:y = c/bqueda fijado yxes libre. - Si
b = 0ya ≠ 0, análogamentex = c/aqueda fijado eyes libre. - Si
a = b = 0yc ≠ 0, no existen soluciones. Si tambiénc = 0, cualquier pareja entera es solución:x = s,y = t, con dos parámetros independientes.
El laboratorio utiliza aritmética entera exacta, sin redondear los coeficientes. Acepta hasta 80 cifras para cada uno de los tres parámetros y distingue las fórmulas completas de la tabla, que muestra como máximo 25 soluciones por página.
Abrir el laboratorio: introduce a, b y c y sigue todos los pasos