Systems of linear Diophantine equations are systems of linear equations in which the solutions are required to be integers.
These systems can be tackled initially using similar techniques to those found in linear equations over the real numbers, using elementary methods such as elimination and substitution or more advanced methods from linear algebra. One major difference is that a single linear Diophantine equation does not always have integer solutions, even though it always has real solutions: for example, the linear Diophantine equation has no integer solutions (the left side is even and the right side is odd), but it has infinitely many solutions over the real numbers, of the form .
The general strategy is to reduce the multiple equations to one equation, and then to solve that equation parametrically using techniques from the wiki on single linear Diophantine equations. More specifically, the strategy is as follows:
Strategy for Solving Systems of Linear Diophantine Equations:
- Turn the problem into one involving a system of Diophantine equations (if it is a word problem).
- Proceed as in a general linear system: eliminate variables via substitution, adding/subtracting multiples of equations, or some more formal versions of these techniques using matrices. Obtain a single linear equation in some number of variables.
- Find the general parametric solution of that equation using standard number theory techniques.
- Substitute that solution back into the other equations to solve for the remaining variables.
- If the problem specifies restrictions on the solutions (for instance, most commonly all of the unknowns must be nonnegative integers), find the values of the parameters that lead to solutions satisfying those restrictions.
The following examples demonstrate this process in action:
The following example has no restrictions with respect to the values the variables can take other than that they must be integers:
Find all integer solutions to the system of equations
Eliminate one variable, say . Since from the second equation, substituting in the first equation gives So , and substituting back in the equation gives so the solutions are of the form , for any integer.
Manipulate equations to eliminate one variable, say . Multiply the first equation by 11 and multiply the second equation by 6, and then add to get Since is a solution to this equation by inspection, the solutions are of the form for an integer. If the numbers were bigger, inspection might have been more of an issue; an alternative way to generate an initial solution is to consider e.g. mod to get mod , etc. Now substitute back into the first equation to get so all solutions are of the form for integer .
Equations coming from word problems often have restrictions on the variables, e.g. all the solutions must be positive integers. Once all the solutions have been described, this generally leads to some inequalities that the parameters must satisfy. Here is a simple example:
How many ways are there to make from coins, each of which is a quarter, dime, or nickel?
Let be the number of quarters, dimes, and nickels, respectively. Then
Writing and substituting into the first equation gives , which reduces to
Since is one solution, all the solutions are given by for some integer . In this case , so the general solution is .
Since all the numbers must be nonnegative, we have, respectively, , , and . The last inequality reduces to , so the acceptable values of are . This gives a total of solutions.
At my butcher shop, you can buy 2 pounds of chicken thigh and 1 pound of chicken feet for 738 cents, and 3 pounds of chicken thigh and 1 pound of chicken heart for 852 cents.
For how many ordered sets of integers , with each of the element between 0 and 100 inclusive, can you determine the exact total cost of pounds of chicken thigh, pounds of chicken feet, and pounds of chicken heart?
Assume that the cost per pound of any given meat is constant.
After a long war, the Greeks finally decided to build a Trojan Horse to be lured into the heart of Troy. For this architecture, 180 soldiers were initially selected and would normally finish such work in 8 days.
However, after working for some whole days, 84 workmen were recruited back to the troops, leaving the rest to continue building.
Then, after working for some whole days, 16 workmen fell sick, and the remaining soldiers carried out the work for some whole days and eventually finished building the Greek gift.
How many days in total did it take for them to build the Trojan Horse, assuming the work capacity was always constant?