Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section3.1Linear Diophantine Equations

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.

Proof

Subsection3.1.1If \(c\) is not a multiple of \(\gcd(a,b)\)

What is the possibility of solving \(ax+by=c\) in this case?

  • Here, our previous theorems say this is impossible. Can you see why?

  • For instance, if \(a=6\), \(b=9\), and \(c=5\).

Subsection3.1.2If \(a\) or \(b\) is zero

  • Say \(b=0\) – in which case \(\gcd(a,b)=a\). Try \(a=55\).

  • Then we are just solving \(ax=c\), so it is true precisely when \(a|c\), and then all pairs \(\left(\frac{c}{a},y\right)\) with integer \(y\) are solutions.

  • If \(a=0\) the answer is analogous; write it down for yourself as practice!

Subsection3.1.3If \(c=\gcd(a,b)\)

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*}

Subsection3.1.4If \(c\) works, but is not the gcd

What if \(c\) is not the greatest common divisor? Then let \(c=de\), where again \(d\) is the greatest common divisor.

  • We still have the same solution as above for \(d\), so we can find \(d=ax_0+by_0\) for some \((x_0,y_0)\) as above.

  • Now if we multiply the whole thing by \(e\), we have that \(de=ax_0 e+by_0 e\), or that \(c=a(x_0 e)+b(y_0 e)\) is a solution.

  • Now do exactly the same thing as above for the answer! The surprise is that \(x=x_0 e +\frac{b}{d}n, y=y_0 e-\frac{a}{d}n\) still works, but it's easy to check again (see Exercise 3.6.2), with virtually the same check working as above. You don't need the \(e\) in the fractions because they will just cancel anyway.

Example3.1.3

Try to do \(15x-21y=6\), a slightly harder one. (Hint: \(d=3\); what are \(c\) and \(d\)?