Solving Linear Diophantine Equations

What is a Diophantine equation?

A Diophantine equation requires integer solutions only. The linear Diophantine equation $ax + by = c$ has integer solutions if and only if $\gcd(a, b)$ divides $c$.

Step-by-step: Solve $7x + 11y = 1$

Step 1 — Check solvability. $\gcd(7, 11) = 1$, and $1$ divides $1$. ✓ Solutions exist.

Step 2 — Use the Extended Euclidean Algorithm to express $\gcd(7, 11) = 1$ as a combination of 7 and 11.

Run the Euclidean algorithm backward:

$11 = 7 \times 1 + 4$ → $4 = 11 - 7 \times 1$

$7 = 4 \times 1 + 3$ → $3 = 7 - 4 \times 1 = 7 - (11 - 7) = 2 \times 7 - 11$

$4 = 3 \times 1 + 1$ → $1 = 4 - 3 = (11 - 7) - (2 \times 7 - 11) = 2 \times 11 - 3 \times 7$

So $1 = (-3) \times 7 + 2 \times 11$, giving $7(-3) + 11(2) = 1$.

One particular solution: $x_0 = -3$, $y_0 = 2$.

Check: $7(-3) + 11(2) = -21 + 22 = 1$ ✓

Step 3 — Write the general solution. All integer solutions are:

$x = -3 + 11t, \quad y = 2 - 7t \quad (t \in \mathbb{Z})$

For $t = 0$: $(x, y) = (-3, 2)$. For $t = 1$: $(8, -5)$. For $t = -1$: $(-14, 9)$.

Check $t = 1$: $7(8) + 11(-5) = 56 - 55 = 1$ ✓

Why the general solution has that form

If $(x_0, y_0)$ is one solution, then $(x_0 + b/d \cdot t, \; y_0 - a/d \cdot t)$ gives all solutions, where $d = \gcd(a, b)$. The shifts $b/d$ and $-a/d$ ensure the equation stays balanced.

When there are no solutions

$6x + 4y = 5$: $\gcd(6, 4) = 2$, and 2 does not divide 5. No solutions exist — the left side is always even, but 5 is odd.

Try it in the visualization

Enter $a$, $b$, $c$. The lattice shows integer points $(x, y)$. The line $ax + by = c$ is drawn — solutions are the lattice points ON the line. The extended Euclidean algorithm steps are animated.