Calculadora de ecuaciones diofánticas lineales — soluciones enteras de ax + by = c

Cómo funciona

ax + by = c tiene soluciones enteras ⇔ g = mcd(a, b) divide a c · Euclides extendido: as + bt = g · solución particular x₀ = s·(c/g), y₀ = t·(c/g) · solución general: x = x₀ + (b/g)k, y = y₀ − (a/g)k, k ∈ ℤ

Una ecuación diofántica lineal busca soluciones enteras de ax + by = c. Toda combinación entera de a y b es múltiplo de su mcd, así que hay solución exactamente cuando mcd(a, b) divide a c. El algoritmo de Euclides extendido escribe el mcd como as + bt, y al multiplicar por c/g se obtiene una solución; todas las demás difieren en múltiplos de (b/g, −a/g). La calculadora desplaza la solución particular para que x₀ sea el menor valor no negativo y cuenta las soluciones con x e y positivos (Rosen, Elementary Number Theory, §3.7).

Ejemplo resuelto

15x + 21y = 39: el algoritmo de Euclides da 21 = 1 × 15 + 6, 15 = 2 × 6 + 3, 6 = 2 × 3 + 0, así que mcd = 3, que divide a 39. Sustituyendo hacia atrás, 15·3 + 21·(−2) = 3. Multiplicando por 13: x = 39, y = −26, y desplazando al menor x no negativo: (4, −1), ya que 15·4 + 21·(−1) = 39. Solución general: x = 4 + 7k, y = −1 − 5k. Ninguna solución tiene x e y positivos a la vez.

Fuentes: Wolfram MathWorld — Diophantine Equation (linear) · Wikipedia — Bézout’s identity

Preguntas frecuentes