Solving Linear Diophantine Equations with Linear Congruences
Recall that a linear diophantine equation is an equation of the form $ax + by = c$ for some $a, b, c \in \mathbb{Z}$ where $(x, y)$ is a solution if $x, y \in \mathbb{Z}$ satisfies this equation.
So, let $a, b, c \in \mathbb{Z}$ and consider $ax + by = c$. Then this equation can be rewritten as $ax = c - by$. Thus $ax \mid (c - by)$, i.e.:
(1)Or similarly, we can rewrite $ax + by = c$ as $by = c - ax$. Thus $by \mid (c - ax)$, i.e.:
(2)Upon solving these linear congruences we will simultaneously solve the corresponding linear diophantine equations. Let's look at an example. Suppose that we want to solve $9x + 10y = 11$. Then, consider the following linear congruence:
(3)By inspection we see that $9(9) = 81 \equiv 1 \pmod 10$ and so:
(4)Thus $x = 9 + 10t$ where $t \in \mathbb{Z}$. Substituting this into our linear diophantine equation gives us:
(5)So the solutions to $9x + 10y = 11$ are given by $x = 9 + 10t$ and $y = -7 - 9t$ for $t \in \mathbb{Z}$.