Linear Diophantine Equations
Just the integers, please.
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.
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):
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:
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:
- Simplify and put into standard form of ax + by = c
- Play with x and y values for a short while, we may get lucky!
- Find the Greatest Common Factor of a and b, using the Euclidean Algorithm
- If c is not a multiple of the Greatest Common Factor there is no solution
- Follow the Euclidean Algorithm backwards, substituting as we go
- Finally, we may need to multiply all terms to match the original c value
An example will help:
Example: 66x + 27y = 9
Already in standard form.
Euclidean Algorithm to find the Greatest Common Factor:
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)
and do backward substitution in this pattern:
like this:
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:
But looking at our previous illustration, notice that at 105 the difference becomes zero again?
In fact 21×5 − 15×7 = 0, so we can do this:
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:
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:
So we get this:
And for the previous example:
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:
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:
like this:
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.