Linear Diophantine equations

Section 11.3 Linear Diophantine equations

Let us consider again the linear Diophantine equation

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

We will use some properties about continued fractions to find a solution \((x, y)\) to this equation provided one exists. Since we must have \(\gcd(a, b)\vert c\) to have a solution we will assume this to be the case. Also, if \(d = \gcd(a, b)\gt 1,\) we can consider the related equation

\begin{equation*} \frac{a}{d}x+\frac{b}{d}y=\frac{c}{d}, \end{equation*}

where \(\gcd(a/d, b/d) = 1.\) We continue to reduce this system to only looking at the equation

\begin{equation*} ax + by = 1, \end{equation*}

where \(\gcd(a, b) = 1;\) we can then find a solution to the general equation.

To get a solution to

\begin{equation*} ax + by = 1, \end{equation*}

where \(\gcd(a, b) = 1,\) we will consider the simple continued fraction of \(a/b.\) Doing this we gain the following theorem.

Theorem 11.3.1.

Let \(a, b \in\mathbb{N}\) with \(\gcd(a, b) = 1.\) Write \(a/b =[a_0; a_1,..., a_n], C_k = p_k/q_k\) the convergents of \(a/b,\) and consider the equation

\begin{equation} ax + by = 1.\label{Eqn_11_1}\tag{11.3.1} \end{equation}

If \(n\) is odd then the equation in (11.3.1) has the solution \((x_0, y_0) =(q_{n-1}, -p_{n-1}),\) whereas for even \(n,\) then (11.3.1) has the solution \((x_0, y_0) =(-q_{n-1}, p_{n-1}).\)

Proof.

We expand

\begin{equation*} \frac{a}{b}= [a_0; a_1,..., a_n]. \end{equation*}

The last two convergents of this continued fraction are

\begin{equation*} C_{n-1} =\frac{p_{n-1}}{q_{n-1}} \hspace{5mm} \text{ and } \hspace{5mm} C_{n} =\frac{p_{n}}{q_{n}}. \end{equation*}

Since \(\gcd(p_n, q_n) = 1\) we have that \(p_n = a\) and \(q_n = b.\) By the last theorem of the previous section we have that

\begin{equation*} a(q_{n-1})-b(p_{n-1}) = p_nq_{n-1}-q_np_{n-1} = (-1)^{n-1}. \end{equation*}

Considering the cases of \(n\) for even and odd, we will have our result.

If \(n\) is even, write \(n = 2k\) for some \(k,\) then

\begin{equation*} a(q_{n-1})+b(-p_{n-1}) = (-1)^{2k-1}=-1, \end{equation*}

and so

\begin{equation*} a(-q_{n-1})+b(p_{n-1}) = 1. \end{equation*}

If \(n\) is odd, write \(n=2k+1\) for some \(k,\) then

\begin{equation*} a(q_{n-1})+b(-p_{n-1}) = (-1)^{2k+1}= 1. \end{equation*}

Example 11.3.2.

We solve the Diophantine equation \(6x + 32y = 2.\) Since \(\gcd(6, 32) = 2,\) we divide by \(2\) and consider the equation

\begin{equation*} 3x + 16y = 1. \end{equation*}

Using the Euclidean algorithm for \(3\) and \(16\) gives

\begin{align*} 3 \amp = 0 \cdot 16 + 3\\ 16 \amp = 5\cdot 3 + 1\\ 3 \amp = 3 \cdot 1. \end{align*}

\begin{equation*} \frac{3}{16}=0+\frac{1}{5+\frac{1}{3}}= [0; 5, 3]. \end{equation*}

The convergents of \(3/16\) are \(C_0 = 0, C_1 = 1/5,\) and \(C_2 = 3/16.\) Since \(n\) is even we have that \((x_0, y_0) = (-5, 1)\) is a solution to \(3x + 16y = 1.\) Thus multiplying the equation by \(2,\) we have that \((x_0, y_0) = (-5, 1)\) is a solution to \(6x + 32y = 2.\)