Discrete Math · Undergraduate
Linear Diophantine Equations: Whole-Number Solutions of ax + by = c
Quick answer
A linear Diophantine equation ax + by = c asks for integer solutions, such as how many 5- and 7-dollar tickets total exactly 100 dollars. It has integer solutions exactly when gcd(a, b) divides c. The extended Euclidean algorithm finds one solution, and every other comes from stepping along the line: x = x₀ + (b/d)t, y = y₀ − (a/d)t, where d = gcd(a, b). Requiring x and y to be nonnegative then leaves only finitely many choices, here three.
What you'll learn
- Decide whether ax + by = c has integer solutions
- Find one solution with the extended Euclidean algorithm
- Write the general integer solution
- Count the solutions with x and y nonnegative
Equations that want whole numbers
Concert tickets cost and dollars, and a club spends exactly dollars. How many of each did it buy? The equation has infinitely many real solutions, but only whole numbers make sense. An equation with integer coefficients, solved in integers, is a linear Diophantine equation.
Existence. With , integer solutions exist exactly when .
All solutions. If is one solution, every solution is
- 5x + 7y = 100
Why the gcd decides everything
Every value of with integers is a multiple of , since divides both and . So if , there is no solution. Conversely, the extended Euclidean algorithm writes , and multiplying by gives a solution. The integer combinations of and are exactly the multiples of , no more and no less. Two solutions differ by a solution of , and those are the multiples of , which is why the solutions sit at equal steps along the line.
Worked examples
Common mistakes
Practice problems
-
Does have integer solutions? If so, find the general solution.
Answer
Yes: ,
Full solution
divides . Dividing by gives , with .
-
Find the general solution of .
Answer
,
Full solution
.
-
Does have integer solutions?
Answer
No
Full solution
does not divide .
-
Stamps cost and cents. Find all ways to pay exactly cents.
Answer
of cents and of cents
Full solution
Try : only leaves , a multiple of . The next solution, , makes negative.
-
How many nonnegative solutions does have?
Answer
Full solution
must make divisible by : , giving , , .
-
Explain why and in Example 1 differ by .
Answer
solves , so adding it keeps the total at .
Full solution
; with , this is the smallest such step.
-
Find one solution of .
Answer
,
Full solution
. The general solution is , .
-
A student writes the general solution of as , . What is missing?
Answer
The steps must be divided by : , .
Full solution
The student’s formula skips solutions such as .
Frequently asked questions
When does ax + by = c have integer solutions?
Exactly when d = gcd(a, b) divides c. For example, 4x + 6y = 7 has none, since 2 does not divide 7.
How do you find one solution?
Use the extended Euclidean algorithm to write d = ax' + by', then multiply by c/d.
What is the general solution?
If (x₀, y₀) is one solution, all solutions are x = x₀ + (b/d)t and y = y₀ − (a/d)t for integers t.
Why are there infinitely many integer solutions?
Adding b/d to x and subtracting a/d from y changes ax + by by a(b/d) − b(a/d) = 0, so the total stays c.
How do you count nonnegative solutions?
Write the general solution and find the integers t that make both x ≥ 0 and y ≥ 0.