We are familiar with the form of linear equation in a plane, which is $ax + by = c$, where $a, b$ and $c$ are constants.
We also know that there can be infinitely many real number solutions to any such given linear equation.
Today we are going to learn a specific subset of these solutions, namely integer solutions only.
Let us start with a problem statement.
$A$ wants to buy some erasers and pencils. Each eraser costs $Rs.\ 3$ and a pencil costs $Rs.\ 5$. $A$ wants to spend exactly $Rs.\ 75$ for this purpose. How many different ways can he do so?
If we take the number of erasers and pencils that $A$ buys as $x$ and $y$ respectively, then we get the equation:
$3x + 5y = 75$
We can very easily see that if $A$ buys no eraser, that is $x = 0$, we get $y = 75 \div 5 = 15$, or on the other hand he buys no pencils, that is $y = 0$, we get $x = 75 \div 3 = 25$
But there could be many more combinations of pencils and erasers that he can purchase with the same amount of money.
Here is one way we can we go about finding the various combinations of pencils and erasers that he can buy.
Let us say he decides to buy $0$ erasers and $15$ pencils.
-----------book page break-----------
We know that every set of $3$ pencils costs $Rs\ 15$, which he can replace with $5$ erasers.
Therefore, he can buy his stationery in the following ways:
$Erasers$
$0$
$5$
$10$
$15$
$20$
$25$
$Pencils$
$15$
$12$
$9$
$6$
$3$
$0$
What we did was to start with $0$ eraser and $15$ pencils, kept replacing some pencils with an equivalent number of erasers. Why did we choose to replace $3$ pencils at a time? Because, if the number of pencils is not a multiple of $3$ the resulting price of those many pencils will not be divisible by $3$, therefore, will not give an integer number of erasers.
Now, let us change the problem a little bit.
Let's say each eraser costs $Rs\ 7$ but each pencil costs $Rs\ 11$, and $A$ has to spend exactly $Rs 300$ on these items.
So our equation becomes:
$7x + 11y = 300$
Now we can see that even finding the first solution is much trickier and involves much more trial and error as compared to the previous example.
In the following sections, we will examine two different ways to find the first set of integer solution to these types of equation, and then see how to go about counting the number of ways.
We will use this equation in all the following sections to understand the different approaches explained in them.
II. Solvable And Unsolvable Diophantine Equations
Is it possible to have a linear equation of the form $ax + by = c$ such that there is no integer $x$ and $y$ satisfying the equation?
Let us try the following question.
-----------book page break-----------
--------- Reference to question: c063c3a6-45ff-469f-b42e-be273b8c433c ---------
-----------book page break-----------
In the previous example we saw that if $c$ is not a multiple of $gcd(a, b)$ then there is no integer solution for the given equation, which also means, that if a linear equation has integer solutions, then in the fully reduced form of the equation, $gcd(a, b) = 1$.
Let us see why using mathematical logic.
If the $gcd$ of $a$ and $b$ is $g$ where $g > 1$, we can write $a = ga'$ and $b = gb'$, where $a'$ and $b'$ are integers and are co-primes.
Therefore, our equation becomes:
$ga'x + gb'y = c$
$\Rightarrow g(a'x + b'y) = c$
$\Rightarrow a'x + b'y = \dfrac{c}{g}$
If $c$ is not divisible by $g$ then $\dfrac{c}{g}$ is a fraction, and if there is any solution with integer $x$ and $y$, then the left side of the equation will be an integer, which is not possible.
Whereas, if $c$ is divisible by $g$ then the right side will also be an integer, and the equation will have integer solutions. In that case we can divide both sides of the equation to obtain the fully reduced form of the equation $gcd(a, b) = 1$
Therefore, we can say that an equation of the form $ax + by = c$ with $a, b, c$ as integers, has integer solution in $x$ and $y$ $if\ and\ only\ if$ $c$ is divisible by $gcd(a, b)$
-----------book page break-----------
III. Using Euclid's Method
Euclid's algorithm says that if for integers $a$ and $b$ $gcd(a, b) = g$ then there exists integers $p, q$ such that:
$ap + bq = g$
(Watch out!!! It says integers and not positive integers, which means we can have negative values satisfying the equations as well).
In this section we will see how to find the first solution, no matter whether they are positive or negative values, and later on we will find the other solutions meeting the criteria for the problem in hand.
The gcd of $7$ and $11$ is $1$, therefore, we will find a linear combination of $7$ and $11$ such that $7x + 11y = 1$ for integer $x$ and $y$.
We will do so by using the to calculate the gcd of $7$ and $11$
To begin with, our dividend is $11$ and divisor is $7$. In all the following steps we have written the values as $dividend = divisor(quotient) + remainder$. The divisor is shown in blue, quotient in red and the remainder in green.
Dividing $11$ by $7$ we get a quotient of $1$ and a remainder of $4$, therefore:
We know that the remainder in the step before the remainder becomes $0$ is the $gcd$ of the given numbers.
-----------book page break-----------
Starting with $step (iii)$ above, we can now write the same steps in the reverse order to obtain the original numbers, but we will keep the remainders on the left hand side, and everything else on the right hand side.
$1 = 4 - 3(1)$ remainder $1$ from $step\ (iii)$
$1 = 4 - (7 - 4(1))(1)$ we replaced remainder $3$ from $step\ (ii)$
$1 = 4 - 7(1) + 4(1)$
$1 = 4(2) - 7(1)$
$1 = (11 - 7(1))(2) - 7(1)$ we replaced the remainder $4$ from $step\ (i)$
$1 = 11(2) - 7(2) - 7(1)$
$1 = 11(2) - 7(3)$
$1 = 11(2) + 7(-3)$
Now we can see that we can express the $GCD$ of $11$ and $7$ as a sum of multiples of $11$ and $7$
And if we put $x = -3$ and $y = 2$ on the left hand side of the our equation we will get $1$.
But we need to get $300$, therefore, if we multiply both sides by $300$ we get:
Therefore, $x = -900,\ y = 600$ is the first solution we get for integer $x$ and $y$. Let us call this solution $x_0,\ y_0$
We will see in a subsequent section how to get all possible solutions for this equation, out of which we can choose the solutions that meet our criteria, that is, $x$ and $y$ should be non-negative integers.
-----------book page break-----------
IV. Using Modular Arithmetic
Now that we have learnt one method, we will look at another method to find the first solution to a Diophantine equation.
We will use the same equation from the above example, which is:
$7x + 11y = 300$
Here, we can see that if $300$ was divisible by $11$ then we could have taken $x = 0$ and $y = \dfrac{300}{11}$, and that would give us the first solution. Similarly, if $300$ was divisible by $7$ we could have taken $y = 0$ and $x = \dfrac{300}{7}$, which would give us the first solution.
Unfortunately $300$ is neither divisible by $11$ nor by $7$, which means we will get fraction values, which are not acceptable.
Now if we could subtract a multiple of $11$ from $300$ such that the result was divisible by $7$, then we could have surely used that for finding our first solution.
Now let us choose the smaller of $a$ and $b$, which in our case is $7$ and find what is the remainder when we divide $300$ by that number:
$300 \equiv 6\ (mod\ 7)$
We need to find a number which is of the form $11p$ where $p$ is an integer, such that $11p$ leaves a remainder of $6$ when divided by $7$, that is:
$11p \equiv\ 6\ (mod\ 7)$
We will find it by trial and error:
$11 \times 1 = 11 \equiv\ 4\ (mod\ 7)$
$11 \times 2 = 22 \equiv\ 1\ (mod\ 7)$
Since we have $11 \equiv\ 4\ (mod\ 7)$ and $22 \equiv\ 1\ (mod\ 7)$, we can say:
$11 + 22 + 22 \equiv 4 + 1 + 1 = 6\ (mod\ 7)$
$55 \equiv 6\ (mod\ 7)$
-----------book page break-----------
Therefore we need to subtract $55$ from $300$ to get a number divisible by $7$
$300 - 55 = 245$ which indeed, is divisible by $7$
Hence we can take the first solution as $x = 35$ and $y = 5$.
We can cross verify this solution:
$7 \times 35 + 11 \times 5 = 245 + 55 = 300$ Therefore this is a valid solution.
We can see that the first solution we obtained in $Section\ III$ is different from the one we obtained here. But that is fine, since a solvable Diophantine equation will have infinite number of solutions, we can use any one as a starting point.
V. Counting All Positive Solutions Using Parametric Equation
Now that we have our first solution/s we will use the concept called parametric equation to represent the same line.
If we are able to represent our line $7x + 11y = 300$ as two equations using a third parameter $t$ such that:
$x = f(t)$
$y = f(t)$ such that each value of $t$ gives us a point on the line $7x + 11y = 300$ then we can find all the solutions in the given range, which in this case are $x \ge 0$ and $y \ge 0$
We know that any line of the form $7x + 11y = k$ will be a line parallel to the line $7x + 11y = 300$. What is the equation of the line that is parallel to $7x + 11y = 300$ and passes through the origin?
It is intuitive to see that the line $7x + 11y = 0$ passes through the point $(0, 0)$ and is parallel to the given line. Let us call this line $l_0$
Hence we can write $\dfrac{x}{y} = \dfrac{11}{-7}$
The line $l_0$ passes through the point $(11, -7)$ or any other point which is of the form $(11t, -7t)$
Hence if we write $x = 11t$ and $y = -7t$ for any particular value of $t$ the point will lie on the line $l_0$.
-----------book page break-----------
We learnt about origin translation . Now all we need to do is translate the origin to the point $x_0$ and $y_0$ to get the parametric form of our equation $7x + 11y = 300$
So, we can say:
$x - x_0 = 11t \Rightarrow x = 11t + x_0$
$y - y_0 = -7t \Rightarrow y = -7t + y_0$
Now we will take the values of $x_0, y_0$ from each of the above sections and see if we get a consistent result.
$\underline{Case\ 1:}$
We got $x_0 = -900$ and $y_0 = 600$ in $Section\ III$ using $Euclid's\ Method$
Therefore, our parametric representation becomes:
$x = 11t - 900$
$y = -7t + 600$
Each integer value of $t$ will give us an integer solution in terms of $x$ and $y$. Now we need to find the non-negative values of $x$ and $y$
$x \ge 0$
$\Rightarrow 11t - 900 \ge 0$
$\Rightarrow 11t \ge 900$
$\Rightarrow t \ge \dfrac{900}{11}$
$\Rightarrow t \ge 81\dfrac{9}{11}$
Since $y$ is also non-negative, we can write:
$y \ge 0$
$\Rightarrow -7t + 600 \ge 0$
$\Rightarrow 600 \ge 7t$
$\Rightarrow 7t \le 600$
$\Rightarrow t \le \dfrac{600}{7}$
$\Rightarrow t \le 85\dfrac{5}{7}$
-----------book page break-----------
Combining this with the previous equation, we get:
$81\dfrac{9}{11} \le t \le 85\dfrac{5}{7}$
Given that $t$ is an integer, the valid values of $t$ ranges from $82$ to $85$, both values included. Therefore there can be $4$ sets of integer solutions for the equation $7x + 11y = 300$
Now we will take each valid value of $t$ and find the corresponding values of $x$ and $y$ from the parametric equations, to see what are the possible valid combinations of erasers and pencils that can be bought.
$x = 11t - 900$
$y = -7t + 600$
$t$
$82$
$83$
$84$
$85$
$Erasers\ (x)$
$2$
$13$
$24$
$35$
$Pencils\ (y)$
$26$
$19$
$12$
$5$
$\underline{Case\ 2:}$
Using the modular arithmetic approach we got our first point as $x_0 = 35$ and $y_0 = 5$
We will use the same parametric form of equation we derived earlier, with these values of $x_0, y_0$ and see what we get.
$x = 11t + x_0$
$\Rightarrow x = 11t + 35$
$y = -7t + y_0$
$\Rightarrow y = -7t + 5$
-----------book page break-----------
To find the values in the acceptable range:
$x \ge 0$
$\Rightarrow 11t + 35 \ge 0$
$\Rightarrow 11t \ge -35$
$\Rightarrow t \ge -\dfrac{35}{11}$
$\Rightarrow t \ge -3\dfrac{2}{11}$
Similarly,
$y \ge 0$
$\Rightarrow -7t + 5 \ge 0$
$\Rightarrow 5 \ge 7t$
$\Rightarrow 7t \le 5$
$\Rightarrow t \le \dfrac{5}{7}$
Combining the two we get:
$-3\dfrac{2}{11} \le t \le \dfrac{5}{7}$
Since $t$ is an integer, the smallest valid value of $t$ is $-3$ and the largest value of $t$ is $0$
Therefore $t$ varies from $-3$ to $0$, both values included, hence there are $4$ positive integer solutions for this equation.
Now we will find the valid combinations of erasers and pencils using the new parametric equations and the range of $t$ we obtained for these.
-----------book page break-----------
$x = 11t + 35$
$y = -7t + 5$
$t$
$-3$
$-2$
$-1$
$0$
$Erasers\ (x)$
$2$
$13$
$24$
$35$
$Pencils\ (y)$
$26$
$19$
$12$
$5$
Now, we can compare the results we obtained using the two methods for finding the initial values of $x$ and $y$.
Our results are exactly same, despite the fact that with each case we obtained a different set of initial solution and a different set of parametric equations.
--------- Reference to question: 242ac8b5-ce04-4142-8ca8-c706e27ea535 ---------
VI. Summary
Let us summarise the steps for solving a linear Diophantine equation for a particular range.
You need to represent the given linear equation as a parametric equation, where $x = pt + x_0$ and $y = qt + y_0$ where $p$ and $q$ are integer constants $x_0,\ y_0$ are any set of values that satisfy the given equation. Each integer value of $t$ will give a solution with integer $x$ and $y$ which satisfies the given linear equation.
If the problem specifies a range and you have done everything correctly then one of the parametric equations will give the lower limit and the other one the upper limit for the value of $t$
-----------book page break-----------
To form a parametric equation you need to find an initial integer solution to your linear equation $x_0,\ y_0$, which you can find out by using $Euclid's\ method$, $Modular\ arithmetic$ or even by simply inspecting the given equation. Any integer solution $x_0, y_0$ to the given linear equation can be a starting point.
To find the parametric equation, you need to find the parametric form of the equation of the line passing through the origin and parallel to the given equation. If the given equation is $ax + by = c$. Then the parametric form of the equation passing through the origin will be: $x = pt$ and $y = qt$, where $p = b$ and $q = -a$. Perform an origin translation, to this equation to get the line passing through $x_0,\ y_0$ by adding these values to get the final form of our parametric equations which are: $x = pt + x_0$, $y = qt + y_0$ (You can see that putting $t = 0$, this passes through the point $x_0$ and $y_0$)
Not all linear equations have integer solutions. It can have a linear solution if and only if the $gcd$ of the coefficients of $x$ and $y$ is $1$ in the fully reduced form of the equation. You need to make sure the equation you are solving has integer solutions.