Escribe los coeficientes de la ecuación diofántica lineal ax + by = c. La ecuación de abajo está conectada con las casillas, así que también puedes cambiar los números directamente en ella. Cambia «Soluciones que buscas» para quedarte solo con las soluciones enteras positivas.
Índice
-
Qué puedes hacer en esta página
-
¿Para qué sirve este cálculo?
-
Cómo usar
-
Fórmulas y gráficas
-
Símbolos y términos
-
Conviene saber antes de empezar
-
Cómo calcularlo en Excel
-
Cómo calcularlo en Hojas de cálculo de Google
-
Cómo calcularlo en Python
-
Cómo escribirla en LaTeX y otros lenguajes de fórmulas (para copiar y pegar)
-
Cómo pedirle el cálculo a ChatGPT
-
Las ventajas de DataChef
-
Funciones relacionadas
-
Lista de calculadoras de NumberChef
Qué puedes hacer en esta página
- Escribe los coeficientes enteros \(a,\ b,\ c\) y obtienes los pares de números enteros \(x,\ y\) que cumplen \(ax + by = c\) (las soluciones enteras)
- Si \(c\) no es múltiplo del máximo común divisor de \(a\) y \(b\), no hay soluciones enteras. La página lo comprueba y explica por qué
- Puedes seguir fila a fila la tabla de divisiones del algoritmo de Euclides y la tabla que recorre los restos al revés para construir una solución particular
- La respuesta no es un solo par: obtienes la solución general \(x = x_0 + \dfrac{b}{g}t,\ y = y_0 - \dfrac{a}{g}t\) (con \(t\) entero) y una tabla de soluciones para distintos valores de \(t\)
- Puedes quedarte solo con las soluciones positivas o solo con las no negativas. Así resuelves directamente problemas como «¿cuántas entradas de 50 € y de 80 € suman exactamente 1000 €?»
¿Para qué sirve este cálculo?
Comprar solo entradas de 50 € y de 80 € por exactamente 1000 €, pesar algo con solo dos tipos de pesas o conseguir una longitud exacta con piezas de medidas fijas: problemas así, de «combinar cosas de tamaño fijo para llegar justo a un objetivo», son exactamente el problema de hallar las soluciones enteras de \(ax + by = c\).
No se puede comprar un número negativo de entradas, así que en la práctica la respuesta llega después de quedarse con las soluciones enteras positivas.
Si solo tienes cajas de 6 y de 10, que puedas empaquetar un pedido de exactamente \(c\) unidades depende de que \(6x + 10y = c\) tenga una solución con enteros de 0 en adelante. El MCD de 6 y 10 es 2, así que un pedido de un número impar de unidades no se puede empaquetar justo, combines las cajas como las combines.
En el envasado de alimentos o de piezas, saber qué cantidades se pueden formar te dice qué pedidos puedes aceptar y qué tamaños de caja te conviene tener.
El famoso acertijo de medir exactamente 4 litros con solo un recipiente de 5 litros y otro de 3 litros corresponde a las soluciones enteras de \(5x + 3y = 4\) (\(x\) e \(y\) cuentan, con signo, cuántas veces se llena o se vacía cada recipiente). Como \(\gcd(5\,;\,3) = 1\), la ecuación te dice de antemano que con estos dos recipientes se puede medir cualquier número entero de litros.
Es la misma matemática que usas en un laboratorio o en la cocina cuando te preguntas: «¿puedo medir lo que necesito solo con lo que tengo?».
El cifrado RSA, que protege la banca online y las compras por internet, obtiene el valor \(d\) de la clave privada a partir del valor \(e\) de la clave pública resolviendo la ecuación diofántica lineal \(e d + \varphi k = 1\) (\(\varphi\) es un entero que depende de la clave). La herramienta que se usa es el mismo algoritmo de Euclides extendido de esta página.
Este procedimiento la resuelve al instante incluso con números de cientos de cifras, y esa es una de las cosas que hacen que el cifrado sea práctico.
Supón que el producto A usa \(a\) kg de material por unidad y el producto B usa \(b\) kg, y quieres gastar exactamente los \(c\) kg que tienes. Ese plan es el problema de hallar soluciones de \(ax + by = c\) con enteros de 0 en adelante. No se puede fabricar medio producto, así que la respuesta tiene que ser un número entero.
La rama que estudia los problemas de planificación cuyas respuestas tienen que ser enteras se llama programación entera. Se usa en planes de producción, cuadrantes de turnos, rutas de reparto y mucho más.
Fórmulas y gráficas
Símbolos y términos
Símbolos
| \(a,\ b\) | a, be | Los coeficientes que multiplican a \(x\) y a \(y\). Por tradición, para los números fijos se usan las primeras letras del alfabeto, \(a,\ b,\ c\). En esta página los dos son enteros. |
| \(c\) | ce | El término independiente, en el lado derecho de la ecuación (la c viene de «constante»). Es el total que quieres conseguir, y que sea o no múltiplo del MCD decide si hay soluciones. |
| \(x,\ y\) | equis, i griega | Las incógnitas que se buscan. La costumbre de usar las últimas letras del alfabeto para las incógnitas se atribuye a Descartes. En esta página solo cuentan como respuesta los valores enteros. |
| \(\gcd(a\,;\,b)\) | máximo común divisor de a y b | El máximo común divisor de \(a\) y \(b\). gcd son las iniciales del inglés greatest common divisor; en los libros de texto españoles se escribe MCD(a, b) o m.c.d.(a, b), y en teoría de números a veces solo \((a\,;\,b)\). |
| \(g\) | ge | Forma abreviada de escribir el máximo común divisor \(\gcd(a\,;\,b)\) (de greatest, «máximo» en inglés). Acorta las fórmulas, como \(\dfrac{b}{g}\) y \(\dfrac{a}{g}\) en la solución general. |
| \(x_0,\ y_0\) | x sub cero, y sub cero | La solución particular, es decir, la primera solución entera que se encuentra. El 0 pequeño la marca como punto de partida, «la solución número 0». Todas las soluciones enteras se escriben a partir de ella. |
| \(x_1,\ y_1\) | x sub uno, y sub uno | El par de enteros que se obtiene recorriendo al revés el algoritmo de Euclides. Cumple \(a x_1 + b y_1 = g\). Si lo multiplicas por \(\dfrac{c}{g}\), obtienes la solución particular \((x_0\,;\,y_0)\). |
| \(t\) | te | Una variable que puede ser cualquier entero (un parámetro). Permite describir con una sola fórmula todas las soluciones enteras. Cada entero que pongas en \(t\) da otra solución entera. |
| \(m\) | eme | El entero que indica cuántas veces cabe \(g\) en \(c\). Para los enteros se suelen usar letras como \(m\), \(n\) y \(k\); la \(m\) recuerda a «múltiplo». Hay soluciones enteras cuando se puede escribir \(c = g \times m\), y solo entonces. |
| \(q\) | cu | El cociente de una división (la q viene del inglés quotient). En la tabla del algoritmo de Euclides es el \(2\) de \(13 = 5 \times 2 + 3\). |
| \(r\) | erre | El resto de una división (la r de «resto»). En la tabla del algoritmo de Euclides es el \(3\) de \(13 = 5 \times 2 + 3\). El algoritmo se detiene cuando este resto llega a 0. |
| \(\geq\) | mayor o igual que | El signo de desigualdad que indica «el lado izquierdo es mayor o igual que el derecho». \(x \geq 1\) quiere decir que \(x\) vale 1 o más. Su pareja, \(\leq\), quiere decir «menor o igual que». |
Términos
| ecuación diofántica lineal | Una ecuación de primer grado con dos incógnitas pero una sola ecuación, como \(ax + by = c\). En los números reales, todos los puntos de la recta son solución, así que la solución no es única. Aunque te quedes solo con las soluciones enteras, normalmente hay infinitas. Es el tipo más sencillo de ecuación diofántica. |
| ecuación diofántica | Nombre de las ecuaciones cuyas respuestas tienen que ser números enteros. Viene de Diofanto, un matemático de la antigua Grecia. La ecuación diofántica lineal de esta página es la más básica. |
| solución entera | Una solución de la ecuación en la que \(x\) e \(y\) son números enteros. En problemas con cantidades que no se pueden partir, como entradas, objetos o personas, solo tienen sentido las soluciones enteras. |
| solución particular | El primer par que se encuentra entre las infinitas soluciones enteras. Vale cualquiera. A partir de él, la solución general describe todas las soluciones. |
| solución general | Todas las soluciones enteras escritas en una sola fórmula con un entero \(t\). Cada entero que pongas en \(t\) da otra solución. |
| máximo común divisor (MCD) | El mayor entero positivo que divide a cada uno de dos o más números enteros. En una ecuación diofántica lineal, este valor decide si hay soluciones y a qué distancia están unas de otras. |
| algoritmo de Euclides | Forma de hallar el máximo común divisor dividiendo el número mayor entre el menor y cambiando el par por el divisor y el resto, una y otra vez. El divisor del paso en que el resto llega a 0 es el MCD. Aparece en los «Elementos» de Euclides, hacia el siglo III a. C., y se suele decir que es el algoritmo más antiguo del mundo. |
| algoritmo de Euclides extendido | Forma de escribir el máximo común divisor como \(a x_1 + b y_1\) sustituyendo de abajo arriba las igualdades de las divisiones del algoritmo de Euclides. Sirve para construir una solución particular de una ecuación diofántica lineal. |
| identidad de Bézout | El teorema que dice que siempre existen enteros \(x_1,\ y_1\) con \(a x_1 + b y_1 = \gcd(a\,;\,b)\). Lleva el nombre del matemático francés Bézout. Es la razón de que una ecuación diofántica lineal se pueda resolver. |
| primos entre sí | Dos números enteros son primos entre sí (o coprimos) cuando su máximo común divisor es 1. Por ejemplo, 3 y 4 son primos entre sí. \(\dfrac{a}{g}\) y \(\dfrac{b}{g}\) son siempre primos entre sí, y por eso las soluciones están a intervalos regulares. |
| múltiplo | Número que se obtiene multiplicando un número entero por otro entero. Los múltiplos de \(10\) son \(\dots,\ -20,\ -10,\ 0,\ 10,\ 20,\ \dots\). El cero y los negativos también cuentan como múltiplos. |
| resto | Lo que sobra cuando una división entera no es exacta. \(13 \div 5\) tiene cociente \(2\) y resto \(3\). El algoritmo de Euclides trabaja solo con estos restos. |
| cociente | En la división entera, el número entero de veces que cabe el divisor. En \(13 = 5 \times 2 + 3\), el cociente es \(2\). |
| punto reticular | Un punto del plano cuyas coordenadas \(x\) e \(y\) son las dos enteras, como las esquinas de los cuadros de una hoja cuadriculada. Las soluciones enteras de una ecuación diofántica lineal son exactamente los puntos reticulares de la recta \(ax + by = c\). |
| parámetro | Una variable que puedes cambiar libremente y que sirve para escribir todo un conjunto de soluciones en una sola fórmula. En esta página, el parámetro es \(t\). |
| coeficiente | El número que va delante de una letra. En \(3x\), el coeficiente es \(3\). Cuando no hay ningún número escrito, como en \(x\), el coeficiente es 1. |
| inecuación | Una desigualdad con incógnitas, que compara el tamaño de dos valores, como \(t \geq 0\). Sirve para quedarse con las soluciones enteras positivas. |
Conviene saber antes de empezar
Esto es lo que te ayuda a usar el cálculo de esta página entendiendo lo que hace, no solo pulsando el botón.
Si te atascas, repasar estos temas es el camino más corto.
| División con resto (3.º-4.º de Primaria, 8-10 años) |
|
| Divisores, múltiplos y MCD (5.º-6.º de Primaria y 1.º de ESO, 10-13 años) |
|
| Expresiones algebraicas y ecuaciones de primer grado (1.º-2.º de ESO, 12-14 años) |
|
| Ecuaciones lineales con dos incógnitas y su gráfica (2.º-3.º de ESO, 13-15 años) |
|
| Inecuaciones (3.º-4.º de ESO, 14-16 años) |
|
| Operaciones con fracciones (5.º de Primaria-1.º de ESO, 10-13 años) |
|
Cómo calcularlo en Excel
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| Término independiente c | 1000 |
| MCD g | =M.C.D(B1;B2) |
| Resto de c ÷ g | =RESIDUO(B3;B4) |
| ¿Hay soluciones enteras? | =SI(B5=0;"Hay soluciones";"No hay soluciones") |
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| x1 del algoritmo de Euclides | -3 |
| y1 del algoritmo de Euclides | 2 |
| a×x1 + b×y1 | =B1*B3+B2*B4 |
| MCD g | =M.C.D(B1;B2) |
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| Término independiente c | 1000 |
| MCD g | =M.C.D(B1;B2) |
| Solución particular x0 | 4 |
| Solución particular y0 | 10 |
| Entero t | 1 |
| x = x0 + (b/g)×t | =B5+(B2/B4)*B7 |
| y = y0 − (a/g)×t | =B6-(B1/B4)*B7 |
| Comprobación a×x + b×y | =B1*B8+B2*B9 |
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| MCD g | =M.C.D(B1;B2) |
| Solución particular x0 | 4 |
| Solución particular y0 | 10 |
| Límite inferior de t (de x ≥ 1) | =-ENTERO((B4-1)/(B2/B3)) |
| Límite superior de t (de y ≥ 1) | =ENTERO((B5-1)/(B1/B3)) |
| Número de soluciones enteras positivas | =MAX(0;B7-B6+1) |
La primera tabla usa el ejemplo 50x + 80y = 1000. El MCD es 10 y 1000 ÷ 10 da resto 0, así que muestra «Hay soluciones». Si cambias 1000 por 1001, pasa a «No hay soluciones».
La segunda tabla comprueba que x1 = −3 e y1 = 2, obtenidos recorriendo al revés el algoritmo de Euclides, cumplen de verdad la identidad de Bézout: 50×(−3) + 80×2 = 10, que coincide con el MCD.
La tercera tabla saca una solución de la solución general. Con t = 1 obtienes x = 12 e y = 5, y la fila de comprobación vuelve a dar 1000. Prueba con otros enteros en t.
La cuarta tabla se queda con las soluciones enteras positivas. El límite inferior de t es 0 y el superior es 1, así que hay 2 soluciones enteras positivas (t = 0 y t = 1). Estas dos fórmulas son para el caso en que a y b son los dos positivos. Con un coeficiente negativo, el sentido de la inecuación cambia, así que ten cuidado.
Cómo calcularlo en Hojas de cálculo de Google
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| Término independiente c | 1000 |
| MCD g | =M.C.D(B1;B2) |
| Resto de c ÷ g | =RESIDUO(B3;B4) |
| ¿Hay soluciones enteras? | =SI(B5=0;"Hay soluciones";"No hay soluciones") |
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| x1 del algoritmo de Euclides | -3 |
| y1 del algoritmo de Euclides | 2 |
| a×x1 + b×y1 | =B1*B3+B2*B4 |
| MCD g | =M.C.D(B1;B2) |
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| Término independiente c | 1000 |
| MCD g | =M.C.D(B1;B2) |
| Solución particular x0 | 4 |
| Solución particular y0 | 10 |
| Entero t | 1 |
| x = x0 + (b/g)×t | =B5+(B2/B4)*B7 |
| y = y0 − (a/g)×t | =B6-(B1/B4)*B7 |
| Comprobación a×x + b×y | =B1*B8+B2*B9 |
| Coeficiente a de x | 50 |
| Coeficiente b de y | 80 |
| MCD g | =M.C.D(B1;B2) |
| Solución particular x0 | 4 |
| Solución particular y0 | 10 |
| Límite inferior de t (de x ≥ 1) | =-ENTERO((B4-1)/(B2/B3)) |
| Límite superior de t (de y ≥ 1) | =ENTERO((B5-1)/(B1/B3)) |
| Número de soluciones enteras positivas | =MAX(0;B7-B6+1) |
Cómo calcularlo en Python
from math import gcd
# coeficientes de ax + by = c (enteros)
a, b, c = 50, 80, 1000
def extended_gcd(x, y):
# algoritmo de Euclides extendido: devuelve el mcd y s, t con x*s + y*t = mcd
if y == 0:
return x, 1, 0
g, s, t = extended_gcd(y, x % y)
return g, t, s - (x // y) * t
g = gcd(a, b)
if c % g != 0:
print(f"{c} no es múltiplo de {g}, así que no hay soluciones enteras")
else:
_, s, t = extended_gcd(a, b)
x0, y0 = s * (c // g), t * (c // g) # solución particular (una solución entera)
step_x, step_y = b // g, a // g # paso de x y paso de y
# desplaza hasta que x sea el menor valor de 0 en adelante, para una solución más fácil de leer
n = x0 // step_x
x0, y0 = x0 - n * step_x, y0 + n * step_y
print(f"Solución particular: (x, y) = ({x0}, {y0})")
print(f"Solución general: x = {x0} + {step_x}t, y = {y0} - {step_y}t (con t entero)")
for k in range(-2, 3):
print(f" t = {k:2}: (x, y) = ({x0 + step_x * k}, {y0 - step_y * k})")
# quedarse solo con las soluciones enteras positivas (x >= 1 e y >= 1)
t_low = -((1 - x0) // -step_x)
t_high = (y0 - 1) // step_y
print("Soluciones enteras positivas:", [(x0 + step_x * k, y0 - step_y * k)
for k in range(t_low, t_high + 1)])
Cómo escribirla en LaTeX y otros lenguajes de fórmulas (para copiar y pegar)
c = gcd(a, b) × m
c = \gcd(a, b) \times m
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>c</mi>
<mo>=</mo>
<mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>×</mo>
<mi>m</mi>
</mrow>
</math>
c = gcd(a, b) * m
Mod[c, GCD[a, b]] == 0
irem(c, igcd(a, b)) = 0;
mod(c, gcd(a, b)) == 0
c = gcd(a,b) × m
a·x₁ + b·y₁ = gcd(a, b)
a x_1 + b y_1 = \gcd(a, b)
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>a</mi><msub><mi>x</mi><mn>1</mn></msub>
<mo>+</mo>
<mi>b</mi><msub><mi>y</mi><mn>1</mn></msub>
<mo>=</mo>
<mi>gcd</mi><mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
</mrow>
</math>
a*x_1 + b*y_1 = gcd(a, b)
ExtendedGCD[a, b]
igcdex(a, b, x1, y1);
[g, x1, y1] = gcd(a, b);
a x_1 + b y_1 = gcd(a,b)
x = x₀ + (b/g)t, y = y₀ − (a/g)t
x = x_0 + \frac{b}{g} t, \quad y = y_0 - \frac{a}{g} t
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>x</mi><mo>=</mo><msub><mi>x</mi><mn>0</mn></msub>
<mo>+</mo>
<mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>,</mo><mspace width="1em"/>
<mi>y</mi><mo>=</mo><msub><mi>y</mi><mn>0</mn></msub>
<mo>−</mo>
<mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
</mrow>
</math>
x = x_0 + (b/g)t, y = y_0 - (a/g)t
Solve[a x + b y == c, {x, y}, Integers]
isolve(a*x + b*y = c);
S = solve(a*x + b*y == c, [x y], 'Integer', true);
x = x_0 + (b/g)t, y = y_0 - (a/g)t
x₀ + (b/g)t ≥ 1, y₀ − (a/g)t ≥ 1
x_0 + \frac{b}{g} t \geq 1, \quad y_0 - \frac{a}{g} t \geq 1
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<msub><mi>x</mi><mn>0</mn></msub>
<mo>+</mo>
<mfrac><mi>b</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>≥</mo><mn>1</mn>
<mo>,</mo><mspace width="1em"/>
<msub><mi>y</mi><mn>0</mn></msub>
<mo>−</mo>
<mfrac><mi>a</mi><mi>g</mi></mfrac><mi>t</mi>
<mo>≥</mo><mn>1</mn>
</mrow>
</math>
x_0 + (b/g)t >= 1 and y_0 - (a/g)t >= 1
Solve[a x + b y == c && x >= 1 && y >= 1, {x, y}, Integers]
isolve({a*x + b*y = c, x >= 1, y >= 1});
S = solve([a*x + b*y == c, x >= 1, y >= 1], [x y], 'Integer', true);
x_0 + (b/g)t ≥ 1, y_0 − (a/g)t ≥ 1
Cómo pedirle el cálculo a ChatGPT
Eres un asistente de cálculo de teoría de números (propiedades de los números enteros). Haz el siguiente cálculo ejecutando de verdad código de Python y basa tu respuesta solo en los números del resultado de la ejecución (no respondas calculando de cabeza ni a ojo). Halla las soluciones enteras de la ecuación diofántica lineal 50x + 80y = 1000. Muestra lo siguiente: 1. El máximo común divisor de 50 y 80, y si 1000 es múltiplo de él 2. Las divisiones del algoritmo de Euclides (hasta que el resto sea 0) y los x1, y1 con 50×x1 + 80×y1 = MCD que se obtienen recorriéndolas al revés 3. Una solución particular (x0, y0) y la solución general x = x0 + (b/g)t, y = y0 − (a/g)t 4. Todas las soluciones enteras en las que x e y valen 1 o más En Python, usa math.gcd y el algoritmo de Euclides extendido para calcular con exactitud, y muestra las fórmulas que has usado y los números del resultado de la ejecución.
Cómo usar
-
1Introduce los datosEscribe en las casillas los números con los que quieres calcular
-
2CalculaPulsa el botón «Calcular»
-
3Consulta el resultadoEl resultado aparece al instante. En la misma página tienes también la idea del cálculo y la explicación de la fórmula
Las ventajas de DataChef
Sin conocimientos técnicos: fácil e intuitivo
Sin necesidad de dar datos personales
Los archivos se borran automáticamente tras la descarga
Sin necesidad de atribución
Sin necesidad de pedir permiso