Section3.1Linear Diophantine Equations

The first goal for this chapter is Linear Diophantine Equations. 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 in solving something like \(ax+by=c\) for all integers \(x,y\) that make it work. Let \(gcd(a,b)=d\).

When \(c\) is not a multiple of \(d\)
When \(a\) or \(b\) is zero
When \(c=d\)
When \(c\) is a nontrivial multiple of \(d\)

You should definitely follow the steps with specific numbers (suggested) to see how each proof works

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.

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) 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: \[x=x_0+\frac{b}{d}n,\; y=y_0-\frac{a}{d}n\;\text{ for }n\in \mathbb{Z}\; !\] 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: \[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\; .\]
Why does this give all solutions? Well, pick another solution \((x,y)\), and let's show it has this form. Start with \[ax+by=c=ax_0+by_0\text{, so that }\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0)\; .\] Now we use the earlier fact; since we divided out by the gcd, \(\frac{b}{d}\) is coprime to \(\frac{a}{d}\), and since \(\frac{b}{d}\) does divide the left side, it must divide the other piece of the left side. That means \[k\frac{b}{d}=x-x_0\text{, which means }x=x_0+k\frac{b}{d}\; ,\] which is exactly what we just said was the form of all solutions.

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. (Try some simple numbers, such as the one in Example 3.1.1.)

We still have the same solution as above for \(d\) - so 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, 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.1An 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 \[x=1+\frac{4}{2}n,\; y=-1-\frac{6}{2}n\] or \[x=1+2n,y=-1-3n\, .\]

Now try to do it with \(15x-21y=6\), a slightly harder one.