Ecuaciones Diofantinas* Lineales
Solo números enteros, por favor.
Diofanto de Alejandría
¿Podemos resolver una ecuación usando solo números enteros?
ax + by = c
Es lineal porque las variables x y y no tienen exponentes como x2, etc.
Y se llaman Diofantinas por Diofanto, a quien le encantaba jugar con enteros.
*Las ecuaciones Diofantinas también se conocen como Diofánticas.
Ejemplo: Johana vendió algunos tazones en el mercado a $21 cada
uno y compró algunos jarrones a $15 cada uno para obtener una
ganancia de $33.
¿Cuántos tazones vendió y cuántos jarrones compró?
Lo escribimos como ecuación:
21x − 15y = 33
Intenta resolver esto tú mismo primero...
... OK, tengo esta solución:
21×3 − 15×2 = 33
Entonces, una solución es que Johana vendió 3 tazones y compró 2 jarrones.
Esa era una ecuación lineal diofántica.
Prueba un poco más tú mismo (usa los controles deslizantes):
¡Pero podemos quedarnos estancados!
Ejemplo: ¿Podría Johana haber obtenido una ganancia de $34?
21x − 15y = 34 ...?
Lo intenté pero no tuve éxito. Lo más cerca que estuve fue:
- 21×3 − 15×2 = 33, o
- 21×1 + 15×1 = 36
Pero no encontré nada entre 33 y 36.
¿Por qué ocurre eso?
Esto se debe a que:
15 = 3 × 5
21 = 3 × 7
no podemos evitar la parte "3 ×"
Observa también los múltiplos de 15 y 21 juntos:
Todas las diferencias son múltiplos de 3.
Entonces, en 21x − 15y = c solo podemos crear valores de c que sean múltiplos de 3.
Puede haber más de un factor en común, por lo que para asegurarnos de obtenerlos todos utilizamos el máximo factor común.
Pasos
Nos gusta seguir estos pasos:
- Simplificar y poner en forma estándar, es decir, ax + by = c
- Jugar con los valores de x e y por un rato, ¡puede que tengamos suerte!
- Encontrar el máximo común divisor de a y b, usando el algoritmo euclideano
- Si c no es múltiplo del máximo común divisor no hay solución.
- Seguir el algoritmo euclidiano al revés, sustituyendo a medida que avanzamos.
- Finalmente, es posible que necesitemos multiplicar todos los términos para que coincidan con el valor c original .
Un ejemplo ayudará:
Ejemplo: 66x + 27y = 9
Ya en forma estándar.
Usamos el algoritmo euclidiano para encontrar el máximo común divisor:
El máximo común divisor es 3. Y 9 es múltiplo de 3, así que podemos continuar.
Ahora usemos el algoritmo euclidiano al revés, pero comencemos reescribiendo cada paso así:
resto = 1(dividendo) − cociente(divisor)
y hacemos una sustitución hacia atrás con este patrón:
de este modo:
En forma ax + by = c, es decir:
−2(66) + 5(27) = 3
Pero queremos c=9, así que multiplicamos todos los términos por 3:
−6(66) + 15(27) = 9
Tenemos una solución: x = −6 y y = 15
Infinidad...
¡Pero hay más soluciones!
Volvamos al primer ejemplo:
Ejemplo: 21x − 15y = 33
Tenemos esta solución:
Pero al observar nuestra ilustración anterior, observa que en 105
la diferencia vuelve a ser cero
De hecho, 21×5 − 15×7 = 0, entonces podemos hacer esto:
¡Tenemos otra solución!
Es posible que Johana haya vendido 8 tazones y haya comprado 9 jarrones.
De hecho, podemos sumar cualquier múltiplo de 21×5 − 15×7 = 0 para obtener nuevas soluciones, infinitas de ellas:
Donde n = cualquier número entero.
El truco
¿Cómo encontramos la ecuación "igualada a cero"?
El truco consiste en usar a y b pero reducidos por el máximo factor común divisor de esta manera:
Entonces obtenemos esto:
Y para el ejemplo anterior:
Ejemplo más grande, hecho más rápido
Ejemplo: 1512x + 444y = 96
Ya está en forma estándar.
Usamos el algoritmo euclidiano para encontrar el máximo factor común, y también escribir en estilo "Residuo=":
El máximo factor común es 12. Y 96 es múltiplo de 12, así que podemos continuar.
Ahora haz una sustitución hacia atrás con este patrón:
De este modo:
En la forma ax + by = c, es decir:
1512(5) + 444(−17) = 12
Pero queremos c=96, así que multipliquemos todos los términos por 8:
1512(40) + 444(−136) = 96
Obtenemos esta solución: x = 40 e y = −136
Intenta encontrar tú mismo la solución completa.
Otros tipos
Existen otros tipos de ecuaciones diofánticas lineales como ax + by + cz = d.
Y hay muchos tipos de ecuaciones diofantinas para analizar y jugar con ellas.
¡Refuerza tu aprendizaje resolviendo los siguientes retos sobre este tema! (Nota: están en inglés).
