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$