Ecuaciones Diofánticas Lineales

Aprende a resolver ax + by = c solo con enteros.

Estudiar en la plataforma interactiva
Módulo 6 · Teoría de Números

¿De cuántas formas se pagan $2.100?

En la tienda del colegio te cobran $2.100 y solo tienes monedas de $200 y de $500, y el tendero no tiene vueltas. ¿Se puede pagar exacto? ¿De cuántas formas? Si usas xx monedas de $200 e yy de $500, necesitas 200x+500y=2 100200x + 500y = 2\,100, con xx e yy enteros: una ecuación diofántica.

Momento animado

Pagar $2.100 con monedas

Monedas de $200 y de $500, sin vueltas. Mira qué puntos de la recta sirven y cómo se salta de uno a otro.

1357911012345monedas de $200monedas de $500(3, 3)(8, 1)
la recta
Etapas

Etapa 1 de 4 · La recta

Con x monedas de $200 e y de $500 se pagan 200x + 500y pesos. Para pagar $2.100 exactos: 200x + 500y = 2.100, o sea 2x + 5y = 21. Sus puntos forman una recta.

¿Qué es una ecuación diofántica?

Una ecuación diofántica lineal es:

ax+by=c,x,y∈Zax + by = c, \quad x, y \in \mathbb{Z}

Teorema de Bézout

ax+by=cax + by = c tiene solución entera si y solo si gcd⁡(a,b)∣c\gcd(a, b) \mid c.

Todas las soluciones son:

x=x0+bdt,y=y0−adt,t∈Zx = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t, \quad t \in \mathbb{Z}

Concepto Clave

"gcd(a,b) | c ⟺ ax + by = c tiene solución. Si no divide, puedes parar inmediatamente."

Euclides Extendido

Ejemplo: 47x + 13y = 1

1

Euclides (ida)

47=13×3+847 = 13 \times 3 + 8
2

Continuar

13=8×1+513 = 8 \times 1 + 5
3

Continuar

8=5×1+38 = 5 \times 1 + 3
4

Continuar

5=3×1+25 = 3 \times 1 + 2
5

Continuar

3=2×1+1⇒gcd⁡=13 = 2 \times 1 + 1 \quad \Rightarrow \gcd = 1
6

Retroceder paso 1

1=3−1×21 = 3 - 1 \times 2
7

Sustituir 2 = 5 − 3

1=3−(5−3)=2×3−1×51 = 3 - (5 - 3) = 2 \times 3 - 1 \times 5
8

Sustituir 3 = 8 − 5

1=2(8−5)−5=2×8−3×51 = 2(8-5) - 5 = 2 \times 8 - 3 \times 5
9

Sustituir 5 = 13 − 8

1=2×8−3(13−8)=5×8−3×131 = 2 \times 8 - 3(13-8) = 5 \times 8 - 3 \times 13
10

Sustituir 8 = 47 − 3×13

1=5(47−3×13)−3×13=5×47−18×131 = 5(47 - 3 \times 13) - 3 \times 13 = 5 \times 47 - 18 \times 13

x0=5,  y0=−18x_0 = 5, \; y_0 = -18

Verificación: 47(5)+13(−18)=147(5) + 13(-18) = 1 ✓

Laboratorio

Explorador diofántico

Soluciones enteras de 3x+5y=13x + 5y = 1: los puntos rojos.

  • La recta (puntos reales)
  • Soluciones enteras

Una solución: x0=2,  y0=−1x_0 = 2,\; y_0 = -1

a = 3
b = 5
c = 1

mcd(3, 5) = 1 divide a 1: hay infinitas soluciones y en la ventana se ven 5. De una a la siguiente, x cambia en b/d = 5 e y en −a/d = −3.

Concepto Clave

"El Euclides Extendido te da los coeficientes de Bézout gratis. Practícalo hasta que sea automático."

Problemas: Las Monedas

El Teorema del Cambio de Frobenius

Solo hay monedas de 7 y 11 pesos. ¿Cuál es la mayor cantidad que no se puede pagar?

Práctica · Contar soluciones
¿De cuántas formas se pueden pagar exactamente $2.100 con monedas de $200 y de $500 (sin vueltas)?
Práctica · ¿Tiene solución?
¿Tiene soluciones enteras la ecuación 6x+9y=206x + 9y = 20?
Argumentación · Todas las soluciones
Si (3,3)(3, 3) es una solución de 2x+5y=212x + 5y = 21, ¿cuáles son todas las soluciones enteras?