Este artículo ha sido promovido en Menéame. Si te ha gustado y quieres votarlo entra aquí y menéalo.
Motivación
Supongamos que nos encontramos el siguiente problema:
Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y otros grises, por 1200 €. Si los trajes negros valen 30 € más que los grises y ha comprado el mínimo posible de estos últimos, ¿cuántos trajes ha comprado de cada color?
Vamos a plantearlo:
La ecuación queda:
Haciendo cuentas nos queda lo siguiente:
Si estabais pensando que nos iba a quedar un sistema de ecuaciones sencillo de resolver estáis equivocados. Nos ha quedado una única ecuación con dos incógnitas. ¿Nos faltan datos? No. Podemos resolverla. Bienvenidos al maravilloso mundo de las ecuaciones diofánticas.
Ecuaciones diofánticas
Una ecuación diofántica es una ecuación algebraica en la que aparecen varias variables cuyas soluciones son números enteros. Es decir, resolver una ecuación diofántica consiste en determinar qué números enteros la cumplen. Su nombre lo toman del matemático Diofanto de Alejandría, quien, además de ser uno de los primeros en utilizar simbolismo en álgebra, se dedicó entre otras cosas al estudio de estas ecuaciones
Las ecuaciones diofánticas del tipo anterior se denominan ecuaciones diofánticas lineales. Este caso particular de este tipo de ecuaciones es el que vamos a aprender a resolver en este artículo. Más concretamente, vamos a mostrar (y demostrar) un método para calcular las soluciones enteras de la ecuación
con .
Existencia de soluciones
El primer resultado que vamos a ver y demostrar tiene que ver con la existencia de soluciones de estas ecuaciones. Vamos con él:
Teorema:
Una ecuación lineal diofántica de la forma
tiene solución entera
si y sólo si el máximo común divisor de
y
es un divisor de
.
Además, si llamamos
al
se tiene que una solución particular de dicha ecuación puede obtenerse de la siguiente forma:
siendo
.
Demostración:
1.- Comenzamos con la implicación de izquierda a derecha:
Si la ecuación
(1)
tiene solución entera, entonces existen tales que
Como es un divisor común de
y
, entonces
y
, con
.
Tenemos entonces lo siguiente:
Es decir, nos queda una expresión del tipo , con todos ellos números enteros. En consecuencia tanto
como
deben dividir a
, concluyendo así esta parte de la demostración.
2.- Vamos ahora con la implicación de derecha a izquierda, obteneidno como bonus el además:
Supongamos ahora que es un divisor de
. Entonces existe
tal que
. Por otra parte, por el teorema de Bezout existen
tales que
. Multiplicamos los dos miembros de esta igualdad por
:
De donde obtenemos
Con lo que hemos llegado a que y
son soluciones de la ecuación (1).
Entonces:
es una solución de la ecuación (1), que es lo que queríamos demostrar.
Lo que hemos conseguido hasta ahora es saber reconocer qué ecuaciones diofánticas lineales tienen soluciones y calcular una solución particular de las mismas. Pero queremos una solución general, es decir, todas las soluciones de las ecuaciones diofánticas lineales que se puedan resolver. A ello vamos en el siguiente punto.
Solución general de una ecuación diofántica lineal
Vamos a demostrar el siguiente teorema:
Teorema:
Si
es una solución particular de la ecuación
(1)
entonces todas las soluciones enteras
de la misma son de la forma:
(2)
con
, siendo
.
Demostración:
Si es solución de la ecuación (1), entonces se cumple que
. Pero entonces las expresiones de (2) también son solución de dicha ecuación:
Faltaría ver entonces que todas las soluciones de (1) son de la forma que hemos descrito en (2). A por ello vamos:
Partiendo de la solución particular anterior , supongamos que tenemos una solución
de la ecuación diofántica lineal (1). Tenemos entonces las dos ecuaciones siguientes:
Restamos las dos ecuaciones, obteniendo
Pasando el segundo sumando al otro miembro de la igualdad llegamos a
(3)
Dividimos ahora por :
Como y
son números enteros primos relativos (ya que al dividirlos entre su máximo común divisor les hemos quitado los factores que tuvieran en común en un principio), y
divide a
, debe cumplirse que
divida a
.
Esto nos lleva a que debe existir tal que:
De donde obtenemos que debe ser de la forma:
, con
Sustituyendo este valor de en la ecuación (3) llegamos, después de unos sencillos cálculos, a la expresión buscada para
:
Ejemplo práctico
Volvamos a nuestro amigo el de los trajes. Nos quedamos en la ecuación diofántica lineal siguiente:
Vamos a ver si somos capaces de encontrar cuántos trajes de cada color compró este señor.
Como es un divisor de
nuestra ecuación tiene soluciones. Para obtener
y
debemos utilizar el algoritmo de Euclides para el cálculo del máximo común divisor junto con la identidad de Bezout, citada anteriormente. En este caso se obtiene
por lo que y
.
Entonces la solución particular queda de la siguiente forma:
A partir de esto ya es sencillo encontrar todas las soluciones:
En principio estas expresiones nos dan todas las soluciones del problema, pero todavía no hemos terminado. Hay que tener en cuenta más cosas. Analizando los datos obtenidos sabemos que el número de trajes negros que ha comprado es , por lo que el número de trajes grises comprados es
.
Teniendo en cuenta que el número de trajes de cada tipo comprados por nuestro amigo debe ser positivo y menor que 12 se tiene lo siguiente:
Por tanto, los únicos valores posibles para son
.
Pero el enunciado también decía que ha comprado el mínimo número de trajes grises posibles. Probando con los valores anteriores esta condición se cumple para . En consecuencia el protagonista de nuestro problema compró
trajes grises y
trajes negros.
Fuente de la demostración:
- Álgebra y Matemáticas Discretas I, de Carmen Moreno Valencia.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com…
Valora en Bitacoras.com: Motivación Supongamos que nos encontramos el siguiente problema: Un hombre va a una tienda de ropa y compra 12 trajes, unos negros y otros grises, por 1200 €. Si los trajes negros valen 30 € más que los grises y ha compra…
[…] Cómo resolver ecuaciones diofánticasgaussianos.com/como-resolver-ecuaciones-diofanticas/ por tollendo hace pocos segundos […]
Intersante post. Aunque yo siempre había resuelto estos problemas derivando para hallar el mínimo.
muy buen post, y muy interesante también!
@ Alejandro
Pero esa función es lineal
Y pues hasta lo que se una recta no tiene máximos o mínimos XD
¿O me equivoco?
Saludos
Hola, me parece que la «recta» es de entradas enteras positivas, pues no puedes comprar trajes en cantidad negativa, luego está acotado inferiormente si nos damos cuenta.
Saludos.
Esta es una muestra más de lo cómodo que resulta la linealidad en matemáticas, por la generalidad de resultados que permite. Podrían darse también resultados para las soluciones de la ecuación lineal general
.
Espero que este excelente post nos conduzca, más pronto que tarde, a la joya de la corona: la reciprocidad cuadrática en la resolución de la ecuación cuadrática.
Muy buen trabajo quisiera que me envies el trabajo en formato .tex si es posible.
Muy interesante. Emmanuel, tienes que tener en cuenta que en la recta, y es el precio del traje gris y la x es el número de trajes negros. Esta es una recta que en el primer cuadrante está limitada por y = 100, x= 0 (el coste del traje gris sería de 100 y no habría comprado trajes negros y 12 grises) y y=0,x=40 (habría comprado 40 trajes negros). Además hay una recta que limita las x; x<=12 ya que el número total de trajes es 12, por lo que nunca podrá ser x mayor que este valor. Entonces se… Lee más »
Comprendo la metodología que se siguió para llegar a ese resultado de 2 trajes grises y 10 trajes negros, Cual es la diferencia entre el resultado obtenido mediante este método de solución de ecuaciones diofánticas en el cual se ha comprado el mínimo de trajes grises y algo simple como siguiendo la lógica (entendiendo como «mínimo» que no pudo haber comprado cero trajes grises) y decir el mínimo de trajes grises que compro son 1 y el numero de trajes negros 11??? que tiene malo esta respuesta? con una simple ecuación sacas cuanto costo cada uno de los trajes si… Lee más »
Allí dice:


Pero, debe ser:
Genial artículo!
Emmanuel, en el problema estaba implícito que el precio de cada traje también debe ser un número entero (ya que si no es así la ecuación que se acaba resolviendo no se podría tomar como diofántica, ya que sus soluciones podrían ser números no enteros). Igual lo tenía que haber especificado.
Sote, cierto. Lo cambio ahora. Gracias :).
Bueno ya aclarado ese punto ya veo la utilidad de este procedimiento
Saludos!
[…] 2 en Cómo resolver ecuaciones diofánticas […]
Hay un problema que me parece que puede estar relacionado con este tema, al menos en lo que se refiere a cantidades enteras. De todas formas es un ejemplo divertido…
«El dentista le prohibió a Juan comer más de 10 caramelos por día, pero además, si algún día come más de 7 caramelos, entonces los dos días siguientes no puede comer más de 5 caramelos por día.
Calcular cuál es el mayor número de caramelos que puede comer Juan durante 25 días seguidos obedeciendo las indicaciones del dentista.»
Perdón, hay algo que no entiendo: Debajo de la ecuación 3, en la segunda demostración, por que razón a/d debería dividir a (y0-y) dando como resultado un entero?
Si no me equivoco (y0-y)/(a/d) no tiene porque ser un entero. Corregidme por favor.
[…] 2 en Cómo resolver ecuaciones diofánticas […]
genial ya le entendi no encontraba ningun ejemplo que me ayudara a entender ya podre hacer mi tarea gracias gracias
alguien sabe donde puedo descargar la aritmetica de diofanto en español,cualquiera de los libros(o todos si se puede)
Fórmula y=100-2.5x
y=Precio Unitario Gris
x=Número de trajes Negros
(Mínimo trajes Grises, entonces máximo Negros)
x=11 y=decimal (no vale)
x=10 y=75
Respuesta
10 Negros a 105.00
02 Grises a 75.00
Soluciones totales incluyendo decimales
(originados por la fórmula)
NEGRO PU NEGRO GRIS PU GRIS TOTAL
1 127.50 11 97.50 1200
2 125.00 10 95.00 1200
3 122.50 9 92.50 1200
4 120.00 8 90.00 1200
5 117.50 7 87.50 1200
6 115.00 6 85.00 1200
7 112.50 5 82.50 1200
8 110.00 4 80.00 1200
9 107.50 3 77.50 1200
10 105.00 2 75.00 1200
11 102.50 1 72.50 1200
Negro(PU Negro)+Gris(PU Gris)=Total
1(127.50)+11(97.50)=1200
2(125.00)+10(95.00)=1200
3(122.50)+9(92.50)=1200
4(120.00)+8(90.00)=1200
5(117.50)+7(87.50)=1200
6(115.00)+6(85.00)=1200
7(112.50)+5(82.50)=1200
8(110.00)+4(80.00)=1200
9(107.50)+3(77.50)=1200
10(105.00)+2(75.00)=1200
11(102.50)+1(72.50)=1200
Nicolás: “El dentista le prohibió a Juan comer más de 10 caramelos por día, pero además, si algún día come más de 7 caramelos, entonces los dos días siguientes no puede comer más de 5 caramelos por día. Calcular cuál es el mayor número de caramelos que puede comer Juan durante 25 días seguidos obedeciendo las indicaciones del dentista.” Datos: Trabajando con los máximos Premisa 1: max 10 (pero con condiciones) Premisa 2: max 7 (sin condiciones) Premisa 3: 8-9-10 entonces 1-2-3-4-5 osea come 10 luego 5 cada día siguiente Solución: Los primeros 23 días come 7 x día (23×7=161… Lee más »
Si come 7 caramelos durante 24 días (7*24 = 168) y el último se zampa 10, comerá en total 178. Esto es sencillo al comparar: 7+7+7 = 21 con 10+5+5 = 20 Es decir, es mejor comer 7 caramelos todos los días antes que darse un atracón de 10 uno sólo (pues cada 3 días pierdes la oportunidad de comerte uno más). Todo esto siempre que darse el atracón no acarree consecuencias, como sucede con el último día… ¡Vamos, que el último día se zampa los 10 y se queda tan contento! Así, en total, 178 caramelos que se endosa… Lee más »
Cuidado con Iván, que es un zampao. terrible. jajajajaja.
Endosatelo PACIFIC!
[…] de Bézout, conocido como identidad de Bézout. Como ejemplo le propongo la entrada de gaussianos, Cómo resolver ecuaciones diofánticas, donde se ejemplifica a la perfección su uso en la solución de ecuaciones […]
Aunque ha pasado mucho tiempo desde que se publico esta entrada, me voy a atrever a lanzar una pregunta: que pasa cuando, en lugar de 2 variables (x e y) se tienen 3, 4, o mas, pero igualmente una unica expresion? Es decir, por ejemplo:
ax+by+cz=n
me encanta pero no pude enterder desde el principio porque alfa es igual a 1 y beta a -2
Lo mismo me ha pasado a mi, y es porque la entrada a la que te envía el enlace del algoritmo de euclides para calcular el mcd como combinación lineal está escrito con lenguaje de programación. Luego lo he buscado en google con lenguaje algebraico y así ,,, ya sí.
Esos resultados salen del algoritmo extendido de Euclides
El problema en sí no es diofantico, dado que no the dice que el precio tenga que ser in numero natural.
pero Maria que me dices mujer, si too el tiempo estuvo hablando del tal Diofanto …hasta mira el titulo
..que al loquillo de DiAmOnD porque vive corriendo se le alla olvidao decirlo …
.. pues que después lo dijo (comentario del 30/09/2009):
» Emmanuel, en el problema estaba implícito que el precio de cada traje también debe ser un número entero (ya que si no es así la ecuación que se acaba resolviendo no se podría tomar como diofántica, ya que sus soluciones podrían ser números no enteros). Igual lo tenía que haber especificado…»
El minimo de trajes que se pueden compar es uno
1200/12= 100€
100€- 30€=70€
Y=70€ X=102.7272…≈102.73€
1200-70= 1130€
1130/11= 102,7272…=102+72/99 MCM=99 1098/99+72/99=10170/99=1.130/11=102.7272…
Pero Como las ecuaciones diofanticas buscan los resultados en numeros enteros son 2 trajes grises.
Y=70×2=140
1200-140=1060
X=1060/10= 106
X=106. Y=70
El minimo de trajes que se pueden compar es uno
1200/12= 100€
100€- 30€=70€
Y=70€ X=1130/11
X≈102.73€
1200-70= 1130€
X=1130/11= 102,7272…=102+72/99 MCM=99
Pero Como las ecuaciones diofanticas buscan los resultados en numeros enteros son 2 trajes grises.
Y=70×2=140
1200-140=1060
X=1060/10= 106
X=106. Y=70
¿de dónde salió el 6=30-12*2?
Ahí lo dice:
«Para obtener \alpha y \beta debemos utilizar el algoritmo de Euclides para el cálculo del máximo común divisor junto con la identidad de Bezout, citada anteriormente»
ANTERIORMENTE significa que debes devolverte ( con papel y lápiz a la mano), a donde nombran al tal Bezout.
Entiendo que podía haber reducido la ecuación al principio a 5x+2y=200 y proceder igual, no?
Sí, se podría haber reducido al principio.
en un kiosco venden chcolates de 3 y 5 soles determinar la maxima cantidad d chocolates que sepuedan comprar con 112 soles
ayudaaaaaaaaaaa por faaaaaaaa
Yo honestamente no he entendido muy bien este artículo, no sé cómo se podría resolver tu problema usando las ecuaciones diofánticas. Yo lo hice por fuerza bruta: primero, determinamos la ecuación que hay que resolver, en este caso: Para obtener el número máximo de chocolates, yo definí una función de en la que podamos obtener sus valores a partir de (esto porque, si queremos obtener la mayor cantidad de chocolates posibles, obviamente debemos tener más chocolates del precio menor, y menos del precio mayor, por lo que tiene sentido comenzar sustituyendo por el menor número posible). La función quedaría así:… Lee más »
Cuando dije: «… vamos sustituyendo
por los números naturales…», en realidad quise decir «…vamos sustituyendo
por los números naturales…», y donde dije: «… y cada vez que obtengamos un número natural en
hacemos la suma…», quise decir: «… y cada vez que obtengamos un número natural en
hacemos la suma…».
si la ecuacion es negativa, por ejemplo: 4x-5y=34 como lo resuelvo? Gracias
Sean a, b ∈ Z distintos de cero, con d = (a, b), y sean enteros x, y tales que ax + by = d. Demuestra que (x, y) = 1.
Alguien que me ayude con este problema, llevo rato intentandolo
Un grupo de 17 monos almacenan sus plátanos en 11 pilas de igual medida y una doceava con 6 plátanos. Cuando ellos dividen los plátanos en 17 pilas no sobra ninguno, ¿cuál es el menos número de plátanos que pueden tener? Resolver con ecuaciones diofanticas.
[…] restar nuestras dos igualdades y así obtener y llegar a una ecuacion diofantina. Solucionar este tipo de ecuaciones no siempre es […]