Lesson 5 of 8 · Number Theory
Diophantine Equations
A Diophantine equation just means: solve for integers only. That single restriction changes everything — an equation with infinitely many real solutions might have none, one, or infinitely many integer solutions, and telling which requires nothing more exotic than gcd, which you already know from the previous lesson.
Mark your status for this lesson:
Learning objectives
- Determine whether ax + by = c has integer solutions, using gcd(a,b).
- Find one integer solution by search or back-substitution, and understand the general solution's structure.
- Count the positive-integer solutions of a linear Diophantine equation.
- Apply the Frobenius (Chicken McNugget) formula to find the largest unreachable value for two coprime denominations.
The core idea
The equation ax + by = c has an integer solution if and only if gcd(a,b) divides c — this is a direct consequence of Bezout's identity from the previous lesson. If a solution exists, there are infinitely many, spaced regularly apart; the interesting AMC-level questions are usually about finding one specific solution, or counting how many fall in a restricted range like "both positive."
Existence condition
ax + by = c has an integer solution ⟺ gcd(a,b) divides c
Check this before searching for a solution — if it fails, no amount of searching will find one.
General solution structure
Once one solution (x₀, y₀) is found, every other solution has the form x = x₀ + (b/g)t, y = y₀ − (a/g)t for integer t, where g = gcd(a,b). Solutions are evenly spaced — this is why "smallest positive solution" questions reduce to finding the right t.
Frobenius (Chicken McNugget) number
For coprime a, b: largest unreachable value = ab − a − b
Applies to nonnegative combinations only (like stamps or coins) — every value larger than ab−a−b can be made from nonnegative multiples of a and b, and this is provably the largest one that can't.
Worked example 1 — Checking existence
Problem
Does 6x + 9y = 13 have any integer solutions?
Key insight
Check whether gcd(6,9) divides 13 — no searching needed.
Solution
gcd(6,9) = 3, and 3 does not divide 13. No integer solutions exist — the left side is always a multiple of 3, but 13 is not.
Takeaway
Always check the gcd condition first — it can rule out a problem instantly, before wasting time searching.
Worked example 2 — Finding one solution
Problem
Find a solution in positive integers to 5x + 8y = 39.
Key insight
With small coefficients, direct search (trying small y and checking whether x comes out as a positive integer) is fast and reliable.
Solution
Trying y=3: 5x = 15 → x = 3. So (x, y) = (3, 3) works.
Takeaway
For AMC-scale numbers, a short organized search is usually faster than running the full extended Euclidean algorithm.
Worked example 3 — Counting positive solutions
Problem
How many pairs of positive integers (x, y) satisfy 2x + 3y = 24?
Key insight
For y to give a positive integer x, y must make (24 − 3y) both positive and even.
Solution
x = (24 − 3y)/2 must be a positive integer, so y must be even — trying y = 2, 4, 6: y=2 gives x=9, y=4 gives x=6, y=6 gives x=3. y=8 gives x=0 (not positive). 3 pairs.
Takeaway
Counting problems like this reduce to finding which values of one variable keep the other both positive and an integer — organize the search rather than guessing randomly.
Worked example 4 — The Frobenius number
Problem
Using only 4-cent and 9-cent stamps, what is the largest value that cannot be made?
Key insight
Since gcd(4,9) = 1, the Frobenius formula applies directly.
Solution
4(9) − 4 − 9 = 23.
Takeaway
This formula only applies when the two denominations are coprime — if gcd(a,b) > 1, most values aren't reachable at all, not just a finite list of exceptions.
Strategy notes
Always check gcd(a,b) | c before searching
This one check either rules out the problem instantly or confirms a solution exists — never start searching for a solution without it.
For small coefficients, organized search beats the extended Euclidean algorithm
When the numbers are small enough for AMC problems, trying successive small values of one variable and checking the other is usually faster than running the full back-substitution machinery.
Common mistakes
Assuming a solution exists without checking the gcd condition
Not every linear equation in two variables has integer solutions — the gcd condition is necessary, not just a technicality.
Forgetting that "positive" is a real restriction
A linear Diophantine equation with solutions has infinitely many overall, but often only a handful (or zero) with both variables positive. Always check the restriction the problem actually imposes.
Applying the Frobenius formula when gcd(a,b) ≠ 1
The ab − a − b formula requires a and b to be coprime. If they share a common factor, most integers aren't reachable at all — the formula simply doesn't apply.
Practice
20 questions across four difficulty tiers. Most want a single number. Two existence questions want a short "yes" or "no." Up to three tries per question before the solution is shown.