Linear Diophantine Equations

Just the integers, please.

diophantus
Diophantus of Alexandria

Can we solve an equation like this using only integers?

ax + by = c

It is Linear because the variables x and y have no exponents such as x2 etc.

And it is Diophantine because of Diophantus who loved playing with integers.

bowl

Example: Sam sold some bowls at the market at $21 each, and bought some vases at $15 each for a profit of $33.

How many bowls and how many vases?

As an equation:

21x − 15y = 33

Try solving this yourself first ...

 

... OK, I got this solution:

21×3 − 15×2 = 33

So a solution is that Sam sold 3 bowls and bought 2 vases.

That was a Linear Diophantine Equation.

Try some more yourself (use the sliders):

images/dio-linear.js

But we can get stuck!

Example: Could Sam have made $34 profit?

21x − 15y = 34 ...?

I tried but had no success. The closest I got was:

  • 21×3 − 15×2 = 33, or
  • 21×1 + 15×1 = 36

But nothing between 33 and 36

Why is that? Because:

15 = 3 × 5
21 = 3 × 7

we can't escape the "3 ×"

Also have a look at multiples of 15 and 21 together:

multiples of 15 and 21
All differences are a multiple of 3

So in 21x − 15y = c we can only create c values that are a multiple of 3.

There may be more than one factor in common, so to make sure we get them all we  use the Greatest Common Factor.

Steps

We like using these steps:

An example will help:

Example: 66x + 27y = 9

Already in standard form.

Euclidean Algorithm to find the Greatest Common Factor:

Start with: 66/27 = 2 R 12
Set a=b=27 and b=r=12: 27/12 = 2 R 3
Set a=b=12 and b=r=3: 12/3 = 4 R 0

Greatest Common Factor is 3. And 9 is a multiple of 3 so we are good to continue.

Euclidean Algorithm backwards, but let's start by re-writing each step as

remainder = 1(dividend) − quotient(divisor)

66/27 = 2 R 12 → 12 = 1(66) − 2(27)
27/12 = 2 R 3 → 3 = 1(27) − 2(12)
12/3 = 4 R 0 → (ignore the last step)

and do backward substitution in this pattern:

substitution method

like this:

Start with: 3 = 1(27) − 2(12)
12 = 1(66) − 2(27), so: 3 = 1(27) − 2(1(66) − 2(27))
Simplify: 3 = 5(27) − 2(66)

In ax + by = c form that is:

−2(66) + 5(27) = 3

But we want c=9, so just multiply all terms by 3:

−6(66) + 15(27) = 9

We have a solution: x = −6 and y = 15

Infinity...

But there are more solutions!

Let's go back to the first example:

Example: 21x − 15y = 33

We got this solution:

21×3 − 15×2 = 33

But looking at our previous illustration, notice that at 105 the difference becomes zero again?

multiples of 15 and 21

In fact 21×5 − 15×7 = 0, so we can do this:

Our solution:21×3 − 15×2 = 33
Our "equals zero" equation:21×5 − 15×7 = 0
Add the two equations and get this21×8 − 15×9 = 33

We have another solution!

Sam may have sold 8 bowls and bought 9 vases.

In fact we can add any multiple of 21×5 − 15×7 = 0 to come up with new solutions, infinitely many of them:

21×(3+5n) − 15×(2+7n) = 33

Where n = any integer.

The Trick

How do we find the "equals zero" equation?

The trick is to use a and b but reduced by the Greatest Common Factor like this:

abgcf − bagcf = 0

So we get this:

A solution:21×3 − 15×2 = 33
"equals zero" equation:21×153 − 15×213 = 0
Simplifies to:21×5 − 15×7 = 0
Giving a full solution set:21×(3+5n) − 15×(2+7n) = 33

And for the previous example:

A solution:66×(−6) + 27×15 = 9
"equals zero" equation:66273 − 27×663 = 0
Simplifies to:66×9 − 27×22 = 0
Giving a full solution set:66×(−6+9n) + 27×(15−22n) = 9

Bigger Example, Done Faster

Example: 1512x + 444y = 96

Already in standard form.

Euclidean Algorithm to find the Greatest Common Factor, and also write in "Remainder =" style:

Euclidean Algorithm   In "Remainder =" style
1512/444 = 3 R 180 180 = 1(1512) − 3(444)
444/180 = 2 R 84 84 = 1(444) − 2(180)
180/84 = 2 R 12 12 = 1(180) − 2(84)
84/12 = 7 R 0 (not needed)

Greatest Common Factor is 12. And 96 is a multiple of 12 so we are good to continue.

Now do backward substitution in this pattern:

substitution method

like this:

Start with: 12 = 1(180) − 2(84)
84 = 1(444) − 2(180), so: 12 = 1(180) − 2(1(444) − 2(180))
Simplify: 12 = 5(180) − 2(444)
180 = 1(1512) − 3(444), so: 12 = 5(1(1512) − 3(444)) − 2(444)
Simplify: 12 = 5(1512) − 17(444)

In ax + by = c form that is:

1512(5) + 444(−17) = 12

But we want c=96, so let's multiply all terms by 8:

1512(40) + 444(−136) = 96

We get this solution: x = 40 and y = −136

Try to work out the full solution set yourself.

Other Types

There are other types of Linear Diophantine Equations such as ax + by + cz = d.

And there are many types of Diophantine Equations to play with as well.