Linear Diophantine Equations

You want to pay ₹100 using ₹12 notes and ₹8 notes. Is it possible? If yes, in how many ways?

Translated: does $12x + 8y = 100$ have solutions in positive integers?

This is a linear Diophantine equation — a linear equation where you demand integer solutions. The theory of when solutions exist, and how to find them all, comes entirely from GCD.

---

When does $ax + by = c$ have solutions?

Theorem. The equation $ax + by = c$ has integer solutions if and only if $\gcd(a, b) \mid c$.

Proof.

Necessity. If $(x_0, y_0)$ is a solution, then $\gcd(a,b)$ divides both $a$ and $b$, so it divides $ax_0 + by_0 = c$.

Sufficiency. By Bezout's Identity, $ax_1 + by_1 = \gcd(a,b)$ for some integers $x_1, y_1$. If $\gcd(a,b) \mid c$, write $c = \gcd(a,b) \cdot t$. Then $a(x_1 t) + b(y_1 t) = c$. $\blacksquare$

Consequence. If $\gcd(a,b) = 1$, then $ax + by = c$ always has solutions for any integer $c$.

---

All solutions from one

Theorem. If $(x_0, y_0)$ is one solution to $ax + by = c$, then every integer solution is:

$x = x_0 + \frac{b}{d}\,k, \qquad y = y_0 - \frac{a}{d}\,k \qquad (k \in \mathbb{Z})$

where $d = \gcd(a,b)$.

Proof. Suppose $(x, y)$ is another solution. Then:

$a(x - x_0) + b(y - y_0) = 0 \implies \frac{a}{d}(x-x_0) = -\frac{b}{d}(y-y_0)$

Since $\gcd(a/d, b/d) = 1$, Euclid's Lemma forces $\frac{b}{d} \mid (x - x_0)$. Write $x - x_0 = \frac{b}{d}k$. Back-substitute to get $y - y_0 = -\frac{a}{d}k$. $\blacksquare$

---

Worked examples

Example 1. Solve $7x + 11y = 1$.

By inspection: $7(-3) + 11(2) = -21 + 22 = 1$. Particular solution: $(x_0, y_0) = (-3, 2)$.

General solution: $x = -3 + 11k$, $y = 2 - 7k$, $k \in \mathbb{Z}$.

Example 2. Solve $6x + 10y = 14$.

$\gcd(6,10) = 2$ and $2 \mid 14$. ✓ Divide through: $3x + 5y = 7$.

Particular solution: $3(4) + 5(-1) = 7$. So $(x_0, y_0) = (4, -1)$.

General solution: $x = 4 + 5k$, $y = -1 - 3k$, $k \in \mathbb{Z}$.

Example 3. The ₹100 problem: $12x + 8y = 100$, positive integers.

$\gcd(12,8) = 4$ and $4 \mid 100$. ✓ Divide: $3x + 2y = 25$.

Particular solution: $x=1, y=11$ (check: $3+22=25$). ✓

General solution: $x = 1 + 2k$, $y = 11 - 3k$.

For $x > 0$: $1 + 2k > 0 \implies k \geq 0$. For $y > 0$: $11 - 3k > 0 \implies k \leq 3$.

So $k \in \{0, 1, 2, 3\}$ — exactly 4 solutions: $(1,11), (3,8), (5,5), (7,2)$.

---

Counting solutions in a range

A common JEE pattern: find the number of non-negative (or positive) integer solutions to $ax + by = c$.

The solutions form an arithmetic progression in $k$. Count the integers $k$ in the valid range.

General method:

1. Find $d = \gcd(a,b)$. Check $d \mid c$.
2. Divide through by $d$: $a'x + b'y = c'$ where $\gcd(a',b')=1$.
3. Find one particular solution $(x_0, y_0)$.
4. General: $x = x_0 + b'k$, $y = y_0 - a'k$.
5. Set constraints ($x \geq 0$, $y \geq 0$, etc.) and count valid $k$.

---

The Frobenius Number

Question. Given coprime positive integers $a$ and $b$, which positive integers cannot be expressed as $ax + by$ with $x, y \geq 0$?

Theorem (Sylvester-Frobenius). The largest integer that cannot be represented is:

$N = ab - a - b$

The number of non-representable positive integers is $\dfrac{(a-1)(b-1)}{2}$.

Proof of the formula. $c$ is representable iff $ax \equiv c \pmod b$ has a solution $x$ with $0 \leq x \leq (c/a)$. Work through the modular arithmetic: exactly $\lfloor c/b \rfloor + 1$ values of $c$ in each block of $b$ consecutive integers are representable once $c$ is large enough. The cutoff works out to $ab - a - b$. $\blacksquare$

Example. Denominations 3 and 7 (coprime): largest non-representable = $21 - 3 - 7 = 11$.

Check: 11 cannot be written as $3x + 7y$ with $x,y \geq 0$. (Try: $y=1$ gives $3x=4$, no; $y=0$ gives $3x=11$, no.) ✓

12 = 3×4 + 7×0 ✓. Every integer $\geq 12$ is representable.

Number of non-representable positive integers: $\frac{(3-1)(7-1)}{2} = 6$. They are: 1, 2, 4, 5, 8, 11.

---

Geometric interpretation

The equation $ax + by = c$ defines a line in the $xy$-plane. Integer solutions are lattice points — points with integer coordinates — on this line.

The general solution says: lattice points on a line are evenly spaced. The spacing vector is $(b/d, -a/d)$. If one lattice point exists, infinitely many do (running in both directions along the line).

If you restrict to positive integers, you're looking at lattice points in the first quadrant — a finite set.

---

Common mistakes

Mistake 1. Checking $\gcd(a,b) \mid c$ but forgetting to also verify the sign/range constraints when looking for positive solutions.

Mistake 2. Taking the general solution formula as $x = x_0 + bk$, $y = y_0 - ak$ without dividing by $d = \gcd(a,b)$ first. The correct step size is $b/d$, not $b$.

Mistake 3. Assuming the Frobenius formula $ab - a - b$ applies when $\gcd(a,b) \neq 1$. It doesn't — if $\gcd(a,b) = d > 1$, then only multiples of $d$ are representable at all; most integers are permanently excluded.

---

The connection between $ax + by = c$ and $ax \equiv c \pmod b$ is direct — one is just the other with $y$ playing the role of the "error." That bridge is built in GCD and Modular Arithmetic.