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 55 and 77 dollars, and a club spends exactly 100100 dollars. How many of each did it buy? The equation 5x+7y=1005x + 7y = 100 has infinitely many real solutions, but only whole numbers make sense. An equation ax+by=cax + by = c with integer coefficients, solved in integers, is a linear Diophantine equation.

Existence. With d=gcd⁡(a,b)d = \gcd(a, b), integer solutions exist exactly when d∣cd \mid c.

All solutions. If (x0,y0)(x_0, y_0) is one solution, every solution is

x=x0+bdty=y0−adt(t∈Z)x = x_0 + \frac{b}{d}t \qquad y = y_0 - \frac{a}{d}t \qquad (t \in \mathbb{Z})
Whole-number points on 5x + 7y = 100 The line 5x + 7y = 100 in the first quadrant, from (0, 14.3) down to (20, 0). Three points on it have whole-number coordinates with x and y at least 0: (6, 10), (13, 5) and (20, 0). They are evenly spaced, 7 apart in x and 5 apart in y. 510152051015xy (6, 10) (13, 5) (20, 0)
  • 5x + 7y = 100
Whole-number points on 5x + 7y = 100

Why the gcd decides everything

Every value of ax+byax + by with integers x,yx, y is a multiple of dd, since dd divides both aa and bb. So if d∤cd \nmid c, there is no solution. Conversely, the extended Euclidean algorithm writes d=ax′+by′d = ax' + by', and multiplying by cd\tfrac{c}{d} gives a solution. The integer combinations of aa and bb are exactly the multiples of gcd⁡(a,b)\gcd(a, b), no more and no less. Two solutions differ by a solution of ax+by=0ax + by = 0, and those are the multiples of (bd,−ad)\left(\tfrac{b}{d}, -\tfrac{a}{d}\right), which is why the solutions sit at equal steps along the line.

Worked examples

Common mistakes

Practice problems

  1. Does 12x+18y=3012x + 18y = 30 have integer solutions? If so, find the general solution.

    Answer

    Yes: x=1+3tx = 1 + 3t, y=1−2ty = 1 - 2t

    Full solution

    gcd⁡=6\gcd = 6 divides 3030. Dividing by 66 gives 2x+3y=52x + 3y = 5, with x=y=1x = y = 1.

  2. Find the general solution of 3x+5y=13x + 5y = 1.

    Answer

    x=2+5tx = 2 + 5t, y=−1−3ty = -1 - 3t

    Full solution

    3⋅2+5⋅(−1)=13 \cdot 2 + 5 \cdot (-1) = 1.

  3. Does 6x+9y=206x + 9y = 20 have integer solutions?

    Answer

    No

    Full solution

    gcd⁡(6,9)=3\gcd(6, 9) = 3 does not divide 2020.

  4. Stamps cost 77 and 1111 cents. Find all ways to pay exactly 100100 cents.

    Answer

    88 of 77 cents and 44 of 1111 cents

    Full solution

    Try y=0,1,2,…y = 0, 1, 2, \ldots: only y=4y = 4 leaves 5656, a multiple of 77. The next solution, y=11y = 11, makes xx negative.

  5. How many nonnegative solutions does 3x+5y=403x + 5y = 40 have?

    Answer

    33

    Full solution

    yy must make 40−5y40 - 5y divisible by 33: y=2,5,8y = 2, 5, 8, giving (10,2)(10, 2), (5,5)(5, 5), (0,8)(0, 8).

  6. Explain why (13,5)(13, 5) and (6,10)(6, 10) in Example 1 differ by (7,−5)(7, -5).

    Answer

    (7,−5)(7, -5) solves 5x+7y=05x + 7y = 0, so adding it keeps the total at 100100.

    Full solution

    5⋅7+7⋅(−5)=05 \cdot 7 + 7 \cdot (-5) = 0; with d=1d = 1, this is the smallest such step.

  7. Find one solution of 21x+14y=3521x + 14y = 35.

    Answer

    x=1x = 1, y=1y = 1

    Full solution

    21+14=3521 + 14 = 35. The general solution is x=1+2tx = 1 + 2t, y=1−3ty = 1 - 3t.

  8. A student writes the general solution of 15x+6y=915x + 6y = 9 as x=3+6tx = 3 + 6t, y=−6−15ty = -6 - 15t. What is missing?

    Answer

    The steps must be divided by gcd⁡=3\gcd = 3: x=3+2tx = 3 + 2t, y=−6−5ty = -6 - 5t.

    Full solution

    The student’s formula skips solutions such as (5,−11)(5, -11).

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.