System of Linear Diophantine Equations

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 \( 4x-2y=5 \) 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 \( x = 1.25+t, y = 2t \).

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:

1. Turn the problem into one involving a system of Diophantine equations (if it is a word problem).
2. 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.
3. Find the general parametric solution of that equation using standard number theory techniques.
4. Substitute that solution back into the other equations to solve for the remaining variables.
5. 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

\[\begin{align} 5x+6y+8z &=1 \\ 6x-11y+7z &= 9. \end{align}\]

---

Solution 1:
Eliminate one variable, say \( x\). Since \( 6x = 11y-7z+9\) from the second equation, substituting in the first equation gives \[ \begin{align} \frac56(11y-7z+9)+6y+8z &=1 \\ 5(11y-7z+9)+36y+48z &= 6 \\ 91y+13z &= -39 \\ 7y+z &= -3. \end{align} \] So \( z = -3-7y \), and substituting back in the \( x\) equation gives \[ \begin{align} 6x &= 11y-7(-3-7y)+9\\ 6x &= 60y + 30 \\ x &= 10y+5, \end{align} \] so the solutions are of the form \( (10y+5,y,-7y-3) \), for \( y \) any integer. \(_\square\)

Solution 2:
Manipulate equations to eliminate one variable, say \( y \). Multiply the first equation by 11 and multiply the second equation by 6, and then add to get \[ \begin{align} 91x+130z &= 65 \\ 7x+10z &= 5. \end{align} \] Since \( (-5,4) \) is a solution to this equation by inspection, the solutions are of the form \( x = -5+10t, z = 4-7t \) for \( t \) 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. \( 10z\equiv 5 \) mod \( 7 \) to get \( z\equiv 4 \) mod \( 7\), etc.\()\) Now substitute back into the first equation to get \[ \begin{align} 5(-5+10t)+6y+8(4-7t) &= 1 \\ -6t+6y &= -6 \\ y &= t-1, \end{align} \] so all solutions are of the form \( (10t-5,t-1,4-7t) \) for integer \( t \). \(_\square\)

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 \( \$ 200\) from \( 1000 \) coins, each of which is a quarter, dime, or nickel?

---

Let \(q,d,n\) be the number of quarters, dimes, and nickels, respectively. Then

\[\begin{align} 25q+10d+5n &=20000 \\ q+d+n &=1000. \end{align}\]

Writing \(q= 1000-d-n\) and substituting into the first equation gives \( 25000-15d-20n = 20000\), which reduces to

\[3d+4n=1000.\]

Since \( (0,250) \) is one solution, all the solutions are given by \( (4t,250-3t) \) for some integer \( t \). In this case \( q = 750-t \), so the general solution is \( (750-t,4t,250-3t)\).

Since all the numbers must be nonnegative, we have, respectively, \( t \le 750\), \( t \ge 0 \), and \(3t \le 250\). The last inequality reduces to \( t \le 83\frac13\), so the acceptable values of \( t \) are \( 0,1,\ldots,83 \). This gives a total of \(\fbox{84}\) solutions. \(_\square\)