Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 37 · Diophantine Equations

Linear Diophantine Equations

Decide when ax + by = c has integer solutions, find all of them with the extended Euclidean algorithm, and solve coin and postage problems in Python.

A Diophantine equation is a polynomial equation where only integer solutions count. The simplest family is the linear one: a·x + b·y = c. It answers everyday questions. Can you pay exactly 47 cents with 6-cent and 15-cent stamps? How many ways can you mix 7-liter and 11-liter buckets to measure 5 liters? Which weights can a balance with two kinds of weights measure?

Over the real numbers such an equation always has infinitely many solutions. Over the integers it may have none, or infinitely many in a neat pattern. The key is the greatest common divisor, and the tool is the extended Euclidean algorithm.

When is there a solution?

Let g = gcd(a, b). The left side a·x + b·y is always a multiple of g, so if g does not divide c, there is no solution. Conversely, Bézout's identity says that g itself can be written as a·s + b·t for integers s, t; multiplying by c/g solves the equation. So:

a·x + b·y = c has an integer solution if and only if gcd(a, b) divides c.

The extended Euclidean algorithm finds s and t while computing the gcd.

Python Extended Euclid and Bézout coefficients

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each line prints a combination that equals the gcd, and True confirms the arithmetic. The Bézout coefficients are not unique; the algorithm returns one particular pair.

All solutions

Once one solution (x₀, y₀) is known, every other solution differs from it by a multiple of (b/g, -a/g):

x = x₀ + (b/g)·k, y = y₀ - (a/g)·k, for every integer k.

To see this, subtract two solutions: a·Δx + b·Δy = 0, so (a/g)·Δx = -(b/g)·Δy. Since a/g and b/g are coprime, Δx must be a multiple of b/g.

Python Solve a·x + b·y = c completely

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first equation has no solution because gcd(6, 15) = 3 does not divide 47. The second has solutions, listed for five values of k. Note that the result for 7x + 11y = 5 includes negative numbers, which matters for the next section.

Non-negative solutions: the coin problem

Real puzzles ask for non-negative x and y, such as how many 7-cent and 11-cent stamps give exactly 100 cents. We pick the range of k that keeps both coordinates non-negative.

Python Counting non-negative solutions

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the water-jug example a negative coefficient means "pour out". That is exactly how the classic puzzle is solved.

The Frobenius (coin) number

For coprime a and b, every integer larger than a·b - a - b can be written as a·x + b·y with non-negative x, y, and a·b - a - b itself cannot. This is the Frobenius number. For stamps of 6 and 7 cents the largest unreachable value is 6·7 - 6 - 7 = 29.

Python Largest unreachable amount

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The dynamic-programming scan and the formula agree for every coprime pair.

More than two unknowns

For a₁x₁ + ... + aₙxₙ = c the condition generalizes: a solution exists if and only if gcd(a₁, ..., aₙ) divides c. To find one, combine variables: solve a₁x₁ + a₂x₂ = g₂, then g₂y + a₃x₃ = g₃, and so on. Python's math.gcd accepts several arguments, which gives the gcd directly.

flowchart TD
    A["ax + by = c"] --> B["g = gcd(a, b)"]
    B --> C{"g divides c?"}
    C -->|no| D["no integer solutions"]
    C -->|yes| E["extended Euclid gives s, t"]
    E --> F["x0 = s*c/g, y0 = t*c/g"]
    F --> G["all solutions: x0 + (b/g)k, y0 - (a/g)k"]

Decision path for a linear Diophantine equation.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. When does 12x + 18y = c have integer solutions?

    gcd(12, 18) = 6, and a solution exists exactly when 6 divides c.
  2. 2. If (x0, y0) solves 5x + 8y = 1, which pair also solves it?

    Solutions step by (b/g, -a/g) = (8, -5) because 58 + 8(-5) = 0.
  3. 3. What is the largest amount that cannot be formed from 5 and 9 unit coins?

    5*9 - 5 - 9 = 31.
  4. 4. Why might the general solution contain negative values?

    The k-family covers all integer solutions. Pick the k that keeps both coordinates non-negative if the problem requires it.

Summary

  • ax + by = c is solvable in integers iff gcd(a, b) | c.
  • The extended Euclidean algorithm gives s, t with as + bt = g, so (sc/g, tc/g) is a solution.
  • All solutions are (x₀ + (b/g)k, y₀ - (a/g)k).
  • Restrict k to count non-negative solutions; coprime a, b have Frobenius number ab - a - b.
  • The same gcd criterion extends to many variables.

Next: Pythagorean Triples