Linear Diophantine Equations (and Systems)

What this move does

The equation $a x + b y = c$ is a single equation with two unknowns, so its solutions are not pinned down: it is called a Diophantine equation, and we only want its integer solutions, that is, the lattice points on the line.

a x + b y = c has integer solutions ⟺ d ∣ c, d = (a, b)

When there are solutions, let $(x_{0}, y_{0})$ be one of them. Then all the solutions are

x = x_{0} + \frac{b}{d} t, y = y_{0} - \frac{a}{d} t (t any integer)

Find $d = (a, b)$ . If $d ∤ c$ , there are no integer solutions and you are done.
Find a particular solution $(x_{0}, y_{0})$ : with small numbers, by trying; with big ones, by running the Euclidean algorithm and working backwards.
Write down the general solution, then use what the problem asks for (positive integers, a certain range) to decide which values $t$ can take.

Predict first

How many integer solutions does $6 x + 9 y = 20$ have?

None at allExactly oneFinitely manyInfinitely many

Choose an answer first; then you can see the result.

Work through one

Example: find all positive integer solutions of 4x + 7y = 53

Step 1 / 5

First ask whether there are solutions
$(4, 7) = 1$ , and $1$ divides every number. There are solutions.

$d = (4, 7) = 1, 1 ∣ 53$
Find one particular solution
Jump one step to the right
You can jump left too
Keep the positive solutions

When you can't find a particular solution by trying

When the coefficients are big, let the Euclidean algorithm find one for you. First solve $a x + b y = d$ , then scale the whole solution up by $c / d$ .

Cut all the way down. The last line of the “Work backwards” column gives

37 \times 6 + 13 \times (- 17) = 1

. So one particular solution of

37 x + 13 y = 5

(30, - 85)

Systems: eliminate first

With three unknowns and two equations, eliminate one unknown first and you are back in the situation above.

Example (the “Hundred Fowls Problem”, from the ancient Chinese Zhang Qiujian Suanjing) A rooster costs $5$ coins, a hen costs $3$ coins, and $3$ chicks cost $1$ coin. With $100$ coins you buy $100$ birds. How many of each do you buy?

Let there be $x$ roosters, $y$ hens and $z$ chicks: $x + y + z = 100$ and $5 x + 3 y + \frac{z}{3} = 100$ . Multiply the second equation by $3$ and subtract the first to eliminate $z$ :

14 x + 8 y = 200 ⟺ 7 x + 4 y = 100.

A particular solution is $(0, 25)$ , the general solution is $x = 4 t$ , $y = 25 - 7 t$ , and then $z = 75 + 3 t$ . For none of the three to be negative, $t = 0, 1, 2, 3$ :

(x, y, z) = (0, 25, 75), (4, 18, 78), (8, 11, 81), (12, 4, 84) .

When it fails

Break it

Counterexample lab: remove one condition

Conclusion: $a x + b y = c$ has integer solutions

$6 x + 9 y = 21$ : $(6, 9) = 3$ and $3 ∣ 21$ . There is a lattice point on the line every $(3, - 2)$ .

Practice

Exercise 1Basic

How many positive integer solutions does $5 x + 3 y = 31$ have?

Exercise 2Basic

$15 x + 21 y = c$ has integer solutions, and $100 \leq c \leq 105$ . What can $c$ be?

Exercise 3Advanced

Write $100$ as “a positive multiple of $7$ ” plus “a positive multiple of $11$ ”: $100 = 7 x + 11 y$ with $x$ , $y$ positive integers. Find $x + y$ .

Exercise 4Challenge

There are only $5$ -cent and $8$ -cent stamps (as many of each as you like). What is the largest postage, in cents, that cannot be made?

What this move does

Work through one

Example: find all positive integer solutions of 4x + 7y = 53

When you can't find a particular solution by trying

Systems: eliminate first

When it fails

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

Forgetting to divide the step of the general solution by the gcd

Making x and y both increase in the general solution