Linear Diophantine Equations
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 \(\$2.00\) from only nickels and quarters?
Let \(n\) be the number of nickels and let \(q\) be the number of quarters. Then a solution to this problem would satisfy the equation
\[5n+25q=200.\]
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.
Contents
Initial Observations
Returning to the example in the introduction...
How many ways are there to make \(\$2.00\) from only nickels and quarters?
As before, the goal is to find the non-negative integer solutions of
\[5n+25q=200.\]
Note that there is a common factor, \(5.\) Dividing out this common factor gives
\[n+5q=40.\]
The smallest possible value for either variable is \(0\), but \(n\) must be a multiple of \(5\). There are \(9\) non-negative multiples of \(5\) that are less than or equal to \(40\) (including \(0\)). Therefore, there are \(\color{red} 9\) ways to make \(\$2.00\) from only nickels and quarters. The ordered pairs \((n,q)\) are listed below:
\[\begin{array} &(0,8), &(5,7), &(10,6), &(15,5), &(20,4), &(25,3), &(30,2), &(35,1), &(40,0).\ _\square \end{array}\]
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 \(c\) be the number of packs of cans he purchases and let \(b\) be the number of packs of bottles he purchases. The goal is to find the non-negative solutions to
\[12c+8b=68.\]
First note that there is a common factor, \(4\). Dividing out this common factor gives
\[3c+2b=17.\]
\(17\) is not divisible by \(3\) nor \(2\), 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 \(5\) packs of cans. This gives
\[15+2b=17,\]
which leaves him with just enough money to purchase \(1\) pack of bottles. Now consider how this solution could be altered to find more solutions. Consider if he only bought \(4\) packs of cans:
\[12+2b=17.\]
This equation gives no integer solution for \(b\), so this is not possible. One can observe that the number of packs of cans must decrease in increments of \(2\). Meanwhile, the number of packs of bottles will increase in increments of \(3.\) The ordered-pair solutions \((c,b)\) are listed below:
\[\begin{array}{ccc} (5,1), & (3,4), & (1,7). \end{array}\]
Therefore, if Travis spends all his money, there are \(\color{red} 3\) ways he could purchase beverages for the party. \(_\square\)
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 \(x,y\in[-20,20]:\)
\[3x+5y=11?\]
One can see that the ordered pair \((2,1)\) is a solution. Then, the \(x\) value must increase/decrease by a multiple of \(5,\) and the \(y\) value will have a corresponding decrease/increase by a multiple of \(3.\) Since the \(x\) value increases/decreases faster, it is more constrained by the restriction that \(x,y\in [-20,20].\) The maximum value of \(x\) gives an ordered-pair solution of \((17, -8).\) The minimum value of \(x\) gives an ordered-pair solution of \((-18,13).\) In total, there are \(\frac{17-(-18)}{5}+1=\color{red} 8\) solutions subject to \(x,y\in[-20,20].\) \(_\square\)
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, \((3,2,1)\) and \((2,3,1) \) both count as one way.
Not all linear Diophantine equations have a solution.
Find the integer solutions to the equation
\[12x+21y=80.\]
There is no common factor for the entire equation, but the left side of the equation has a common factor of \(3:\)
\[3(4x+7y)=80.\]
Recall that \(x\) and \(y\) must be integers. This means that \((4x+7y)\) is also an integer. However, the equation implies that \(4x+7y=\frac{80}{3}.\) By contradiction, there are no integer solutions to the equation. \(_\square\)
Initial Solution to a Diophantine 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:
Bézout's Identity:
Let \(a\) and \(b\) be non-zero integers and let \(d=\gcd(a,b).\) Then there exist integers \(x\) and \(y\) that satisfy
\[ax+by=d.\]
Furthermore, there exist integers \(x\) and \(y\) that satisfy
\[ax+by=n\]
if and only if \(d\mid n.\)
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
\[14x+91y=53.\]
First, calculate \(\gcd(14,91)=7.\) Then, observe that \(7\nmid 53.\) Therefore, by Bézout's Identity, there are no integer solutions to the equation. \(_\square\)
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 \(ax+by=n:\)
- Use the Euclidean algorithm to compute \(\gcd(a,b)=d\), taking care to record all steps.
- Determine if \(d\mid n.\) 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 \(ax_i+by_i=d.\)
- The initial solution to the equation \(ax+by=n\) is the ordered pair \(\left(x_i\cdot \frac{n}{d},\ y_i\cdot \frac{n}{d}\right).\)
Find an initial integer solution to the equation
\[141x+34y=30.\]
Using the Euclidean algorithm, we have
\[\begin{align} 141 &= 4(34)+5 \\ 34 &= 6(5)+4 \\ 5 &= 1(4)+\color{red}{1}. \end{align}\]
Therefore \(\gcd(141,34)=1.\) Solutions exist because \(1\mid 30.\)
Reformat the equations from the Euclidean algorithm:
\[\begin{align} 5 &=141-4(34) \\ 4 &= 34-6(5) \\ 1 &= 5-1(4). \end{align}\]
Now use substitution to find a solution to the equation \(141x_i+34y_i=1:\)
\[\begin{align} 1 &= 5-1(4) \\ 1 &= 5-1\big[34-6(5)\big] \\ 1 &= 7(5)-1(34) \\ 1 &= 7\big[141-4(34)\big]-1(34) \\ 1 &= 7(141)-29(34). \end{align}\]
This gives \(x_i=7\) and \(y_i=-29\) as a solution to the equation \(141x_i+34y_i=1\).
Then an initial solution to the equation \(141x+34y=30\) is
\[\begin{align} x&=7 \cdot 30\\&=210\\\\ y&=-29 \cdot 30\\&=-870.\ _\square \end{align}\]
General Solution to Linear Diophantine Equations
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 \(ax+by=n,\) there exist infinitely many solutions.
If \(\left(x^*,y^*\right)\) is an integer solution of the Diophantine equation \( ax + by = n,\) then all integer solutions to the equation are of the form
\[ \left(x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)}\right) \]
for some integer \(m\).
We have
\[ \begin{align} a \left( x^* + m \frac{b}{\gcd(a,b)} \right) + b \left( y^* - m \frac{a}{\gcd(a,b)} \right) &= ax^* + by^* + \frac{ a b m}{\gcd(a,b)} - \frac{abm}{\gcd(a,b)} \\ &= ax^* + by^* \\ & = c, \end{align}\]
which shows these are indeed solutions to the Diophantine equation. Now, given any solution \( (x, y) \), we have
\[\begin{align} ax + by &= ax^* + by^* \\ a(x - x^*) &= -b(y - y^*) \\ \frac{a}{\gcd(a,b)} (x - x^*) &= - \frac{b}{\gcd(a,b)} (y-y^*) . \end{align}\]
Since \(\frac{a}{\gcd(a,b)}\) and \(\frac{b}{\gcd(a,b)}\) are relatively prime, there exists an integer \(m\) such that \(x-x^* = m \frac{b}{\gcd(a,b)} \) and \(y-y^* = -m \frac{a}{\gcd(a,b)},\) proving the theorem. \(_\square\)
Find all integer solutions to the equation
\[141x+34y=30.\]
From before, an initial solution is \(x^*=210,\ y^*=-870.\)
Then for any integer \(m,\) a solution is
\[ \left(x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)}\right) = \left(210+34m,\ -870-141m\right).\ _\square\]
In some applications, it may be of interest to find the positive (or non-negative) integer solutions of the Diophantine equation \( ax + by = c\). For these problems, we would like to find the integer values \(m\) such that the solutions
\[ x^* + m \frac{b}{\gcd(a,b)}, ~~ y^* - m \frac{a}{\gcd(a,b)} \]
are both positive (or both nonnegative).
Find all integers \(c\) such that the linear Diophantine equation \(52x + 39y = c\) has integer solutions, and for any such \(c,\) find all integer solutions to the equation.
In this example, \( \gcd(52,39) = 13.\) Then the linear Diophantine equation has a solution if and only if \(13\) divides \(c\). Thus, the values \(c\) such that the equation has integer solutions are the multiples of \(13\). Now, for any such \(c\), one solution to the Diophantine equation is \( (x^*,y^*) =\left( \frac{c}{13}, - \frac{c}{13} \right) \). Then, the above implies the integer solutions to the equation are
\[ (x,y) = \left( \frac{c}{13} + 3m, ~ - \frac{c}{13} - 4m \right) \]
for \(m\) integer. \(_\square\)
Find the positive integer solutions of the Diophantine equation \(4x + 7y = 97\).
We have \(\gcd(a,b) = \gcd(4,7)=1\) and \(1 = 4 \cdot 2 + 7 \cdot (-1)\). Then one solution is \(x^* = 2 \cdot 97\) and \(y^* = (-1) \cdot 97\), and all solutions are of the form
\[\left( x^* + m \frac{b}{\gcd(a,b)}, ~ y^* - m \frac{a}{\gcd(a,b)} \right)\] or \[ \left( 2 \cdot 97+ 7m, ~ -97 - 4m \right) \]
for \(m\) integer. Then we would like to find the integers satisfying \( 2 \cdot 97 + 7m > 0\) and \( -97 - 4m > 0\), or
\[ - \frac{ 2 \cdot 97}{7} < m < - \frac{97}{4} .\]
The integers \(m\) satisfying this equation are \(m=-27, -26, -25\), which gives the solutions \((5, 11), (12,7 ),\) and \((19,3)\). \(_\square\)
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 \(1+2-0.31=2.69\) 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.
Equations with more than 2 Variables
Now, consider the linear Diophantine equation in three variables \(ax + by + cz = d.\) Again by Bézout's Identity, as \(a\) and \(b\) range over all integer values, the set of values \(ax + by\) is equal to the set of multiples of \(\gcd(a,b).\) This shows that the Diophantine equation \(ax+by+cz=d\) has integer solutions if and only if \(\gcd(a,b)w+cz=d\) has integer solutions, for \(ax+by=\gcd(a,b)w.\) By the above reasoning, the second equation has integer solutions if and only if \( \gcd(a,b,c)\) divides \(d.\)
By continuing this argument, the linear Diophantine equation
\[a_1x_1 + a_2x_2 + \cdots + a_kx_k=d \]
has an integer solution \( (x_1, x_2, \ldots, x_k) \) if and only if \(\gcd(a_1,a_2, \ldots, a_k) \) divides \(d\).
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 \(n\) variables has \(n - 1\) integral parameters.
Consider 3 positive integers \(x, y,\) and \(z\) satisfying the following equation: \(28x+30y+31z=365\).
What is the value of \(x+y+z?\)
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 \(x=1, y=4\), and \(z=7\). This would give a solution \(x+y+z=12\).
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 \((x,y,z)=(1,4,7)\) and \((x,y,z)=(2,1,9)\). Then, \(x+y+z\) is always equal to \(12\).
Surprisingly, we can find the value of \(x+y+z\) without solving the above equation.
Indeed, because \(x,y,z\) are positive integers, we have
\[\begin{align} 28(x+y+z)=365-2y-3z &\le365-2\cdot1-3\cdot1\\&=360\\\\ x+y+z &\le\dfrac{360}{28}\\&=12\dfrac{6}{7}\\\\ 31(x+y+z)=365+3x+y &\ge365+3\cdot1+1\\&=369\\\\ x+y+z &\ge\dfrac{369}{31}\\&=11\dfrac{28}{31}. \end{align}\]
On the other hand, \(x+y+z\) is an integer, so \(x+y+z=12.\ _\square\)
Additional Topics
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, \(N,\) for which no non-negative solution exists to the equation \(a_1x_1+a_2x_2+\cdots+a_nx_n=N\) for some integer coefficients \(a_1, a_2, \cdots, a_n.\)
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.
