Linear Diophantine Equations
A Diophantine equation is one we insist on solving in whole numbers
only — named for Diophantus of Alexandria. The simplest kind is linear:
ax + by = c,
where a, b, c are given integers and we want integer
x, y. Over the real numbers this is just a line with infinitely many
solutions. The twist — and the number theory — is the demand that x
and y land exactly on lattice points.
When is it solvable?
Every combination ax + by is a multiple of
\gcd(a, b) — that was the lesson of
Bézout's identity.
So the equation can only hold if c is itself such a multiple. That
condition is also sufficient:
ax + by = c has an integer solution if and only if
\gcd(a, b) divides c.
So 6x + 9y = 20 is hopeless (the left side is always a multiple of
3, and 3 \nmid 20), while
6x + 9y = 21 is fine.
Finding one solution
When d = \gcd(a,b) divides c, the
extended Euclidean algorithm
gives x_0, y_0 with ax_0 + by_0 = d. Scale
them by c/d to hit c:
a\Big(x_0\cdot \tfrac{c}{d}\Big) + b\Big(y_0\cdot \tfrac{c}{d}\Big) = c.
Finding all solutions
From one solution (x_0, y_0), every other is reached by sliding along
the line in integer steps. Writing d = \gcd(a,b):
x = x_0 + \frac{b}{d}\,t, \qquad y = y_0 - \frac{a}{d}\,t, \qquad t \in \mathbb{Z}.
The shifts b/d and -a/d are the smallest
whole steps that keep ax + by unchanged. Geometrically, the integer
solutions are evenly spaced lattice points marching along the line — and questions like "find
the positive solutions" become a matter of choosing the right range of
t. This same shape — a solvability condition plus a periodic family
of answers — reappears for
linear congruences.