Linear Diophantine Equations

Consider the equation $ax + by = c$ where $a, b, c \in \mathbb{Z}$ are constants. Suppose that we want to find integer solutions $x, y \in \mathbb{Z}$ that satisfy this equation. Such equations are important when dealing with real life objects which must be counted as integers. We define these equations below.

Definition: An equation of the form $ax + by = c$ where $a, b, c \in \mathbb{Z}$ is called a Linear Diophantine Equation and a solution to this equation is the ordered pair $(x, y)$ where $x, y \in \mathbb{Z}$.

It is not entirely clear yet as to whether solutions to a linear diophantine equation exist or not. The following theorem will give us a criterion which will guarantee a solution.

Theorem 1: If $(a, b) = c$ then there exists $x, y \in \mathbb{Z}$ such that $ax + by = c$.

We will leave Theorem 1 above as an exercise and look at an example. Consider the equation $27x - 96y = 3$. We see check to see that $(27, 96) = 3$ and by applying the Euclidean algorithm we see that:

(1)

\begin{align} \quad 96 = 27q + r \\ \quad 96 = 27(3) + 15\\ \quad 27 = 15q_1 + r_1 \\ \quad 27 = 15(1) + 12 \\ \quad 15 = 12q_2 + r_2 \\ \quad 15 = 12(1) + 3 \\ \quad 12 = 3q_3 + r_3\\ \quad 12 = 3(4) + 0 \\ \quad \quad (96, 27) = (27 , 15) = (15, 12) = (12 , 3) = 3 \end{align}

We can now back substitute to find an equation in the form of $ax + by = d$.

(2)

\begin{align} \quad 3 = 15 + 12(-1) \\ \quad 3 = 15 + (27 - 15)(-1) \\ \quad 3 = 15 + (27)(-1) + (-15)(-1) \\ \quad 3 = 2(15) + (27)(-1) \\ \quad 3 = 2(96 - 3(27)) + (27)(-1) \\ \quad 3 = 2(96) -6(27) + (27)(-1) \\ \quad 3 = 96(2) + 27(-7) \end{align}

Therefore $x = 2$ and $y = -7$ is a solution to $96x + 27y = 3$.

Corollary 1: If $c \mid ab$ and $(c, a) = 1$ then $c \mid b$.

• Proof: Let $c \mid ab$ and $(c , a) = 1$. Since $(c, a) = 1$ there exists integers $x$ and $y$ such that:

(3)

\begin{align} \quad dx + ay = 1 \end{align}

• Multiplying both sides of the equation by $b$ gives us:

(4)

\begin{equation} bcx + bay = b \end{equation}

• Since $c \mid bcx$ and $c \mid bay$ (since $c \mid ab$) we must have that $c \mid b$ as desired. $\blacksquare$

Corollary 2: If $(a, b) = d$, $c \mid a$, and $c \mid b$ then $c \mid d$.

• Proof: Since $(a , b) = d$ there exists integers $x$ and $y$ such that $ax + by = d$ by Theorem 1. If $c \mid a$ and $c \mid b$ then:

(5)

\begin{align} \quad c \mid (ax + by) \end{align}

• Since $ax + by = d$ we must therefore have that $c \mid d$. $\blacksquare$

Corollary 3: If $(a, b) = 1$, $a \mid m$, and $b \mid m$ then $ab \mid m$.

• Proof: Since $a \mid m$ and $b \mid m$ there exists integers $q_1$ and $q_2$ such that $aq_1 = m$ and $bq_2 = m$, and so:

(6)

\begin{align} \quad aq_1 = bq_2 \end{align}

• Notice that $a \mid bq_2$ and also $(a , b) = 1$ is given to us. By Corollary 1, we see that $a \mid q_2$. Hence, there exists some integer $r$ such $ar = q_2$ so:

(7)

\begin{align} \quad ar = q_2 \end{align}

• By substitution of $q_2$ we obtain:

(8)

\begin{align} ar = m/b \\ abr = m \end{align}

• Since $ab \mid abr$ it follows that $ab \mid m$. $\blacksquare$