Introduction

In the previous lesson, Linear Diophantine Equations Part 1, we began a discussion of linear Diophantine equations. In that lesson, we focused on what these equations are, when a solution exists, and how to find a solution when one exists. Recall, a linear Diophantine equation is an equation of the form $ax+by=c$, where coefficients $a$, $b$, and $c$ are all integers, and we’re looking for integers $x$ and $y$ that satisfy the equation.

In this lesson, we will explore how to find all solutions to linear Diophantine equations, and also look at finding solutions under various constraints.

Consider the following example, which was also discussed in the previous lesson.

Finding the Complete Solution to a Linear Diophantine Equation

First, when we say we are looking for the complete solution to an equation, we mean that we are looking for all solutions to the equation.

Let’s look closer at the linear Diophantine equation in Example $1$: $$130x+50y=10$$ Rearranging, we obtain $$50y=-130x+10$$ And so, $$y=-\frac{13}{5}x+\frac{1}{5}$$

This is the equation of a line with slope $-\frac{13}{5}$ and $y$-intercept $\frac{1}{5}$.

Thus, the solutions to the linear Diophantine equation $130x+50y=10$ are exactly the points $(x,y)$ on this line whose coordinates are integers!

We know that $(2,-5)$ lies on this line. How can we find another point $(x,y)$ on this line with integer coordinates? Let’s look at what is happening geometrically.

The equation $130x+50y=10$ is the equation of a line through the point $(2,-5)$.

The slope of this line is equal to $-\frac{130}{50}$, which can be reduced to $-\frac{13}{5}$.

Notice that, in reducing this fraction, we factored out a common factor of $10$, which is equal to $gcd(130,50)$.

Now, from $(2,-5)$, how do we find another point on the line with integer coordinates?

We can move left $5$ and up $13$, to get to the point $(-3,8)$.

Or, we can move right $5$ and down $13$, to get to the point $(7,-18)$.

From $(7,-18)$, we can again move right $5$ and down $13$, to get to the point $(12,-31)$.

We can continue in this manner to generate all of the points on the line with integer coordinates.

In general, every point $(x,y)$ that is of the form $x=2+5n$ and $y=-5-13n$, where $n$ is any integer will be a solution to the linear Diophantine equation $130x+50y=10$. Also, it turns out that every solution to this Diophantine equation must be of this form.

That is, the complete solution to the linear Diophantine equation $130x+50y=10$ is

Let’s check this for the robot example. Here, we looking to find the complete solution to the linear Diophantine equation $130x+50y=10$, so $a=130$, $b=50$, and $c=10$. Also, $d=gcd(a,b)=gcd(130,50)=10$. We had found that one solution is $(x_0,y_0)=(2,-5)$.

According to this theorem, the complete solution to the linear Diophantine equation $130x+50y=10$ is $$x=x_0+n\left(\frac{b}{d}\right),y=y_0-n\left(\frac{a}{d}\right)$$ Substituting $x_0=2$, $y_0=-5$, $a=130$, $b=50$, and $d=10$: $$x=2+n\left(\frac{50}{10}\right),y=-5-n\left(\frac{130}{10}\right)$$ This simplifies to $x=2+5n$, $y=-5-13n$, where $n$ is any integer.

As expected, this is exactly we had found earlier!

Summary of Steps to find all integer solutions to $ax+by=c$:

1. First, find a solution $(x_0,y_0)$ to $ax+by=c$. You can do so by inspection, or by using the techniques that we learned in the previous lesson.

2. The complete solution to the linear Diophantine equation is then $$x=x_0+n\left(\frac{b}{d}\right),y=y_0-n\left(\frac{a}{d}\right),\text{where }n\text{ is any integer}$$

Notice that in order to find the complete solution to a linear Diophantine equation, we need to start with a solution, but it does not matter how we find this solution! If we can find a solution by inspection, trial-and-error, or some other method, this will also suffice! If we can find a solution quickly by inspection or trial-and-error, this can lead to quickly finding the complete solution, as we’ll see in our next example.

Restrictions on Solutions to a Linear Diophantine Equation

Notice that what we have seen so far tells us that if a linear Diophantine equation has a solution, then it has infinitely many (since there are infinitely many choices for the integer $n$). But do all of these solutions make sense in the context of our problem? Consider the following example, which was also discussed in the previous lesson.

In Example $4$, we really want is a solution where both $x$ and $y$ are non-negative integers (that is, integers greater than or equal to $0$).

First, what is the complete solution to this problem? In this problem $a=25$, $b=10$, and $d=gcd(a,b)=gcd(25,10)=5$. We also know that $x=43$, $y=-86$ is one solution to the linear Diophantine equation. Thus, we can use $x_0=43$, $y_0=-86$ to generate the complete solution.

That is, the complete solution is $$x=43+n\left(\frac{b}{d}\right),y=-86-n\left(\frac{a}{d}\right)$$ Substituting $a=25$, $b=10$, and $d=5$: $$x=43+n\left(\frac{10}{5}\right),y=-86-n\left(\frac{25}{5}\right)$$ This simplifies to $x=43+2n$, $y=-86-5n$.

For the solution to make sense in the context of the problem, we need both $x\ge 0$ and $y\ge 0$. Which values of $n$ will satisfy these conditions?

$$\begin{array}{rl}x\ge 0& ⟹43+2n\ge 0\\ & ⟹2n\ge -43\\ & ⟹n\ge -21.5\end{array}$$ So $n$ is an integer and $n\ge -21.5$, which tells us that $n\ge -21$.

Similarly, $$\begin{array}{rl}y\ge 0& ⟹-86-5n\ge 0\\ & ⟹-5n\ge 86\\ & ⟹n\le -17.2\end{array}$$ So $n$ is an integer and $n\le -17.2$, which tells us that $n\le -18$.

Thus, in order for there to be a non-negative number of quarters and dimes, we must have $n\ge -21$ and also have $n\le -18$. Thus, there are $4$ possible values for $n$: $-18,-19,-20,-21$.

Using $x=43+2n$ and $y=-86-5n$, we find there are four solutions to this problem, given the context. They are:

• $x=7$, $y=4$ (when $n=-18$)

• $x=5$, $y=9$ (when $n=-19$)

• $x=3$, $y=14$ (when $n=-20$)

• $x=1$, $y=19$ (when $n=-21$)