# 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)We can now back substitute to find an equation in the form of $ax + by = d$.

(2)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:

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

- 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:

- 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:

- 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:

- By substitution of $q_2$ we obtain:

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