A Diophantine equation is a polynomial equation whose solutions are restricted to integers. These types of equations are named after the ancient Greek mathematician Diophantus. A linear Diophantine equation is a first-degree equation of this type. Diophantine equations are important when a problem requires a solution in whole amounts.
How many ways are there to make from only nickels and quarters?
Let be the number of nickels and let be the number of quarters. Then a solution to this problem would satisfy the equation
However, this is a bit different from simply solving an equation because
- there is more than one solution to account for;
- the solutions are restricted by the fact that they must be non-negative integers.
The study of problems that require integer solutions is often referred to as Diophantine analysis. Although the practical applications of Diophantine analysis have been somewhat limited in the past, this kind of analysis has become much more important in the digital age. Diophantine analysis is very important in the study of public-key cryptography, for example.
Returning to the example in the introduction...
How many ways are there to make from only nickels and quarters?
As before, the goal is to find the non-negative integer solutions of
Note that there is a common factor, Dividing out this common factor gives
The smallest possible value for either variable is , but must be a multiple of . There are non-negative multiples of that are less than or equal to (including ). Therefore, there are ways to make from only nickels and quarters. The ordered pairs are listed below:
The solutions to a Diophantine equation aren't always simple multiples.
Travis is purchasing beverages for an upcoming party. He has $68 to spend. He can purchase packs of cans for $12, or smaller packs of bottles for $8.00. How many ways are there for him to purchase beverages if he spends all of his money?
Let be the number of packs of cans he purchases and let be the number of packs of bottles he purchases. The goal is to find the non-negative solutions to
First note that there is a common factor, . Dividing out this common factor gives
is not divisible by nor , so he must purchase some combination of cans and bottles. Begin by finding a solution in which he purchases the maximum number of cans. He could purchase at most packs of cans. This gives
which leaves him with just enough money to purchase pack of bottles. Now consider how this solution could be altered to find more solutions. Consider if he only bought packs of cans:
This equation gives no integer solution for , so this is not possible. One can observe that the number of packs of cans must decrease in increments of . Meanwhile, the number of packs of bottles will increase in increments of The ordered-pair solutions are listed below:
Therefore, if Travis spends all his money, there are ways he could purchase beverages for the party.
In many practical problems, solutions will be limited to non-negative integers. However, this is not necessarily true for all problems.
Find how many integer solutions there are to the following equation subject to
One can see that the ordered pair is a solution. Then, the value must increase/decrease by a multiple of and the value will have a corresponding decrease/increase by a multiple of Since the value increases/decreases faster, it is more constrained by the restriction that The maximum value of gives an ordered-pair solution of The minimum value of gives an ordered-pair solution of In total, there are solutions subject to
Jack, Charlie, and Andrew went on an egg hunt today, each of them carrying one basket. 300 eggs were hidden at the beginning of the day. At the end of the day, the numbers of eggs in each of the boys' baskets are three consecutive integers.
In how many ways could this happen?
Clarification: Order doesn't matter. For example, in the order of Charlie, Andrew, and Jack, and both count as one way.
Not all linear Diophantine equations have a solution.
Find the integer solutions to the equation
There is no common factor for the entire equation, but the left side of the equation has a common factor of
Recall that and must be integers. This means that is also an integer. However, the equation implies that By contradiction, there are no integer solutions to the equation.
You may have observed from the examples above that finding solutions to linear Diophantine equations involves finding an initial solution, and then altering that solution in some way to find the remaining solutions. The process of finding this initial solution isn't always as straightforward as the examples above. Fortunately, there is a formal process to finding an initial solution.
First, it is important to recognize when solutions exist. Recall the previous example in which there were no solutions. There was a common factor between the coefficients of the variables, but the constant term was not divisible by this factor. This observation is generalized with the Bézout's identity:
Let and be non-zero integers and let Then there exist integers and that satisfy
Furthermore, there exist integers and that satisfy
if and only if
One can determine if solutions exist or not by calculating the GCD of the coefficients of the variables, and then determining if the constant term can be divided by that GCD.
Find all integers solutions to the equation
First, calculate Then, observe that Therefore, by Bézout's Identity, there are no integer solutions to the equation.
If solutions do exist, then there is an efficient method to find an initial solution. The Euclidean algorithm gives both the GCD of the coefficients and an initial solution.
Method for computing the initial solution to a linear Diophantine equation in 2 variables
Given an equation
- Use the Euclidean algorithm to compute , taking care to record all steps.
- Determine if If not, then there are no solutions.
- Reformat the equations from the Euclidean algorithm.
- Using substitution, go through the steps of the Euclidean algorithm to find a solution to the equation
- The initial solution to the equation is the ordered pair
Find an initial integer solution to the equation
Using the Euclidean algorithm, we have
Therefore Solutions exist because
Reformat the equations from the Euclidean algorithm:
Now use substitution to find a solution to the equation
This gives and as a solution to the equation .
Then an initial solution to the equation is
In the example above, an initial solution was found to a linear Diophantine equation. This is just one solution of the equation, however. When integer solutions exist to an equation there exist infinitely many solutions.
If is an integer solution of the Diophantine equation then all integer solutions to the equation are of the form
for some integer .
which shows these are indeed solutions to the Diophantine equation. Now, given any solution , we have
Since and are relatively prime, there exists an integer such that and proving the theorem.
Find all integer solutions to the equation
From before, an initial solution is
Then for any integer a solution is
In some applications, it may be of interest to find the positive (or non-negative) integer solutions of the Diophantine equation . For these problems, we would like to find the integer values such that the solutions
are both positive (or both nonnegative).
Find all integers such that the linear Diophantine equation has integer solutions, and for any such find all integer solutions to the equation.
In this example, Then the linear Diophantine equation has a solution if and only if divides . Thus, the values such that the equation has integer solutions are the multiples of . Now, for any such , one solution to the Diophantine equation is . Then, the above implies the integer solutions to the equation are
Find the positive integer solutions of the Diophantine equation .
We have and . Then one solution is and , and all solutions are of the form
for integer. Then we would like to find the integers satisfying and , or
The integers satisfying this equation are , which gives the solutions and .
An ice cream shop sells 3 flavored scoops: lime, vanilla, and strawberry. Each customer may choose to buy single, double, or triple scoops, and no one orders repeated flavor on the same cone.
For the single scoop, the lime flavor costs 1 dollar each, vanilla 1.5 dollars each, and strawberry 2 dollars each. For double scoops, each order will get a discount of 31 cents off for any combination. For example, the double scoops of lime and strawberry flavors will cost dollars. Finally, for the triple scoops of 3 flavors, it will be discounted to 3.79 dollars.
At the end of the day, 63 lime, 61 vanilla, and 56 strawberry scoops are sold, and the shopkeeper collects 249.75 dollars in total from customers for these sales.
How many customers bought the ice cream? Assume each ice cream is sold to a different person.
Now, consider the linear Diophantine equation in three variables Again by Bézout's Identity, as and range over all integer values, the set of values is equal to the set of multiples of This shows that the Diophantine equation has integer solutions if and only if has integer solutions, for By the above reasoning, the second equation has integer solutions if and only if divides
By continuing this argument, the linear Diophantine equation
has an integer solution if and only if divides .
As seen above, a general solution to a linear Diophantine equation with two variables has one integral parameter. In general, if it exists, a solution to an equation with variables has integral parameters.
Consider 3 positive integers and satisfying the following equation: .
What is the value of
First, looking closely at the equation, we can notice that the coefficients are the number of days in the months and the right-hand side of the equation is the number of days in a year.
February is the month with 28 days. There are 4 months in the year with 30 days and 7 months consisting of 31 days.
Hence we get a solution , and . This would give a solution .
But, can we find another positive integer solution? By using trial and error method, we can easily prove that all positive integer solutions of the above equation are and . Then, is always equal to .
Surprisingly, we can find the value of without solving the above equation.
Indeed, because are positive integers, we have
On the other hand, is an integer, so
If your aim is to solve linear congruences rather than equations, then you should check out the Chinese remainder theorem.
The Chicken McNugget problem is a specific linear Diophantine problem in which the goal is to find the largest integer, for which no non-negative solution exists to the equation for some integer coefficients
The problem of finding the number of ways a set of integers can sum to a certain integer can be solved with a stars and bars approach.