Solutions to Linear Diophantine Equations

Recall from the Linear Diophantine Equations page that if $a, b, c \in \mathbb{Z}$ then an equation of the following form is called a linear diophantine equation:

(1)

\begin{align} \quad ax + by = c \end{align}

The solutions are ordered pairs $(x, y)$ where $x, y \in \mathbb{Z}$. We will now look more into whether solutions exist for certain cases of these equations.

Theorem 1: If $ax + by = c$ has a known solution then there are infinitely many solutions.

• Proof: If $x = x_0$ and $y = y_0$ are integer solutions to the linear diophantine equation $ax + by = c$, then consider $x = x_0 + bt$ and $y = y_0 - at$ for $t \in \mathbb{Z}$. We have that:

(2)

\begin{align} \quad ax + by = a(x_0 + bt) + b(y_0 - at) = ax_0 + abt + by_0 - abt = ax_0 + by_0 = c \end{align}

• Therefore $(x_0 + bt, y_0 - at)$ is also a solution to the linear diophantine equation for all integers $t$. $\blacksquare$

Lemma 2: If $(a, b) \not \mid c$ then $ax + by = c$ has no solutions.

• Proof: Suppose that $(a, b) \mid c$. Then there exists an integer $r$ such that $(a, b)r = c$. We know that there exists integers $x_0$ and $y_0$ such that:

(3)

\begin{equation} ax_0 + by_0 = (a, b) \end{equation}

• Consider $ax + by = c$. We have that:

(4)

\begin{align} \quad ax + by = c = (a, b)r = arx_0 + bry_0 \\ \quad c = arx_0 + bry_0 \end{align}

• So $x = rx_0$ and $y = ry_0$ is a solution. $\blacksquare$.

Lemma 3: If $(a, b) = 1$, and $x_0$ and $y_0$ is a solution to $ax + by = c$, then all solutions of $ax + by = c$ are given.

We will leave the proof of Lemma 3 to the reader.