Linear Diophantine equations

Section 2.3 Linear Diophantine equations

In Chapter 1, we went through a proof of the Pythagorean Theorem, a version of which tells us that there are infinitely many solutions to the Diophantine equation

\begin{equation*} x^2+y^2=z^2. \end{equation*}

We also noted the following very interesting result.

Theorem 2.3.1 (Fermat's Last Theorem).

For \(n\gt 2\) the equation \(x^n+y^n=z^n\) has no non-trivial solutions in integers \(x,y,\) and \(z.\)

But what about a linear Diophantine equation? What if we are interested in a solution \((x,y)\) to the equation \(ax+by=c\) with \(a,b,c\in\mathbb{N}?\)

These questions are answered by the following theorem.

Theorem 2.3.2.

Let \(a,b,c\in\mathbb{N},\) and \(d=\gcd(a,b).\) Then the equation \(ax+by=c\) has an integer solution \(x,y\) if and only if \(d\vert c.\)

Proof.

Let \(d=\gcd(a,b).\) Suppose \(ax+by=c\) has an integer solution. Now we have \(d\vert a\) and \(d\vert b\) so that \(d\vert c.\)

Now suppose that \(d\vert c.\) Then \(d=au+bv\) for some \(u,v\in\mathbb{Z}\) and \(c=dk\) for some \(k\in\mathbb{Z}.\) Now

\begin{equation*} c=kd=k(au+bv)=a(ku)+b(kv), \end{equation*}

and \(x=ku, y=kv\) is a solution to \(ax+by=c.\)

Theorem 2.3.3 (Euclid's Lemma).

If \(a\vert bc,\) with \(d=\gcd(a,b)=1,\) then \(a\vert c.\)

Proof.

Since \(\gcd(a,b)=1\) there are \(x,y\in\mathbb{Z}\) such that \(1=ax+by.\) Multiplication by \(c\) gives

\begin{equation*} c = 1\cdot c = (ax + by)c = acx + bcy. \end{equation*}

Since \(a\vert ac\) and \(a\vert bc,\) we have that \(a\vert (acx + bcy),\) so that \(a\vert c.\)

Theorem 2.3.4.

Let \(a,b,c\in\mathbb{N},\) and \(d = \gcd(a, b).\) If the equation \(ax + by = c\) has one solution, then it has infinitely many. Moreover, all solutions \(x, y\) are of the form

\begin{equation*} x = x_0 +\frac{b}{d}n, \hspace{10mm} y=y_0-\frac{a}{d}n \hspace{10mm} n\in\mathbb{Z} \end{equation*}

where \(x_0, y_0\) is any particular solution.

To see that indeed \(x, y\) is a solution if \(x_0, y_0\) is a solution, we may just plug in \(x, y.\) To see that these are all possible solutions suppose that \(x_0, y_0\) and \(x, y\) are solutions. Then

\begin{equation*} ax + by = c = ax_0 + by_0. \end{equation*}

With some rearrangement we have

\begin{equation*} a(x-x_0) + b(y-y_0) = 0. \end{equation*}

Dividing by \(d = \gcd(a, b)\) gives

\begin{equation*} \frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0). \end{equation*}

Since¹

\begin{equation*} \gcd\left(\frac{a}{d},\frac{b}{d}\right)=1, \end{equation*}

an application of Euclid's Lemma gives \(\frac{b}{d}\vert(x-x_0).\) Thus there is some \(n\in\mathbb{Z}\) such that \(x-x_0=\frac{b}{d}n,\) so

\begin{equation*} x=x_0+\frac{b}{d}n \end{equation*}

Substituting back we get that

\begin{equation*} y=y_0-\frac{a}{d}n. \end{equation*}

This is left to the reader.

These results are particularly nice because they give an algorithm for finding all solutions to a linear Diophantine equation \(ax + by = c.\) We just

Calculate \(d = \gcd(a, b),\) either directly or by Euclidean Algorithm.
Check to see if \(d\vert c.\) If not, there are no solutions. If so, write \(c = dk.\)
If \(d\vert c,\) then use Euclidean Algorithm backwards to find integers \(u\) and \(v\) such that \(au + bv = d.\) Then \(x_0 = uk,\) \(y_0 = vk\) is a particular solution of \(ax + by = c.\)
Now use the results of Theorem 2.3.4 to find the general solution \(x, y\) of the equation.