The first goal for this chapter is to completely solve all ‘Linear Diophantine Equations’ (of two variables), generically \begin{equation*}ax+by=c\text{ for }a,b,c\in\mathbb{Z}\end{equation*} They have been studied since the late Roman era (by Greeks, of course), but it turns out that a general solution for equations like \(6x+4y=2\) were already known in the early medieval days by Indian mathematicians like Aryabhata. When, shortly after 1600, Bachet de Méziriac came up with the same answer, it was only the first in a long line of people coming up with this solution again and again. And that's the one we are doing today!
There are several main cases involved.
Theorem3.1.1Solutions of Linear Diophantine Equations
We wish to solve \(ax+by=c\) for all integers \(x,y\) that make it work. Let \(\gcd(a,b)=d\). Then:
When \(c\) is not a multiple of \(d\) (or both \(a\) and \(b\) are zero) and \(c\) is not), there is no solution.
When \(a\) or \(b\) is zero (but not both), there are infinitely many solutions that require little work to obtain.
When \(c=d\), there are infinitely many solutions, but you will need to first obtain one solution in order to generate the others.
When \(c\) is a nontrivial multiple of \(d\), there are infinitely many solutions that are easiest to generate by means of a solution to \(ax+by=d\).
Proof
The details are in the following subsections.
When \(c\) is not a multiple of \(d\): Subsection 3.1.1
When \(a\) or \(b\) is zero: Subsection 3.1.2
When \(c=d\): Subsection 3.1.3
When \(c\) is a nontrivial multiple of \(d\): Subsection 3.1.4
You should definitely follow the steps with specific simple numbers to see how each proof works. Examples 3.1.2 and 3.1.3 are good models.
Suppose \(a,b\neq 0\) and \(c\) actually is the gcd of \(a\) and \(b\;\ldots\) then there is some work to do. Follow along with \(a=60\), \(b=42\), and \(c=6\).
Your first step should be to get that gcd via the Euclidean algorithm. Let's call it \(d\).
Then go backwards (i.e. Bezout identity 2.4.1) to get one solution \((x_0,y_0)\). That is important, since now at least one \(ax_0+by_0=c\) is known.
Next, simply write down the whole solution set: \begin{equation*}x=x_0+\frac{b}{d}n,\; y=y_0-\frac{a}{d}n\;\text{ for }n\in \mathbb{Z}\; !\end{equation*} Notice that \(a\) and \(b\) switch their ‘affiliation’ here from \(x\) and \(y\) to \(y\) and \(x\). Also note that \(x\) and \(y\) have \(\pm\) involved. It doesn't really matter which is which (switch \(-n\) for \(n\) to see why), but if they have the same sign it is wrong. (When in doubt, try something and then check to see if the answers are right.)
It's easy to check this works: \begin{equation*}a\left(x_0+\frac{b}{d}n\right)+b\left(y_0-\frac{a}{d}n\right)=ax_0+\frac{abn}{d}+by_0-\frac{abn}{d}=c\; .\end{equation*}
Why does this give all solutions? Well, pick another solution \((x,y)\), and let's show it has this form. Start with \begin{equation*}ax+by=c=ax_0+by_0\text{, so that }\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0)\; .\end{equation*} Now we use Proposition 2.4.6. Since \(\frac{b}{d}\) divides the right side, it divides the left side. But since \(\frac{b}{d}\) is coprime to \(\frac{a}{d}\), then it must divide the other piece of the left side, so that \begin{equation*}x-x_0=k\frac{b}{d}\text{, which means }x=x_0+k\frac{b}{d}\; ,\end{equation*} which is exactly what we just said was the form of all solutions.
Example3.1.2An easy example: \(6x+4y=2\)
Trial and error tells us that \(6x+4y=2\) can be solved with \(x_0=1,y_0=-1\). Thus the full answer is \begin{equation*}x=1+\frac{4}{2}n,\; y=-1-\frac{6}{2}n\end{equation*} or \begin{equation*}x=1+2n,y=-1-3n\, .\end{equation*}
