Ecuaciones Diofánticas Lineales

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

Estudiar en la plataforma interactiva

Modulo 6 · Combinatoria

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

Una ecuación diofántica lineal es:

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

📐 Teorema de Bézout

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

Todas las soluciones son:

x = 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 \times 3 + 8

2

Continuar

13 = 8 \times 1 + 5

3

Continuar

8 = 5 \times 1 + 3

4

Continuar

5 = 3 \times 1 + 2

5

Continuar

3 = 2 \times 1 + 1 \quad \Rightarrow \gcd = 1

6

Retroceder paso 1

1 = 3 - 1 \times 2

7

Sustituir 2 = 5 − 3

1 = 3 - (5 - 3) = 2 \times 3 - 1 \times 5

8

Sustituir 3 = 8 − 5

1 = 2(8-5) - 5 = 2 \times 8 - 3 \times 5

9

Sustituir 5 = 13 − 8

1 = 2 \times 8 - 3(13-8) = 5 \times 8 - 3 \times 13

10

Sustituir 8 = 47 − 3×13

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

$x_0 = 5, \; y_0 = -18$

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

Explorador Diofántico

Soluciones enteras de $3x + 5y = 1$

a

= 3

b

= 5

c

= 1

✅ Tiene solución (gcd = 1 divide a 1). Encontradas: 8

Concepto Clave

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

Problema: Las Monedas

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

Ver Solución

Como $\gcd(7, 11) = 1$ , el Teorema de Sylvester-Frobenius dice:

N = 7 \cdot 11 - 7 - 11 = 59