Solving Linear Diophantine Equations with Linear Congruences

# 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)
\begin{align} by \equiv c \pmod a \end{align}

Or similarly, we can rewrite $ax + by = c$ as $by = c - ax$. Thus $by \mid (c - ax)$, i.e.:

(2)
\begin{align} \quad ax \equiv c \pmod b \end{align}

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)
\begin{align} \quad 9x & \equiv 11 \pmod {10} \\ \quad 9x & \equiv 1 \pmod {10} \end{align}

By inspection we see that $9(9) = 81 \equiv 1 \pmod 10$ and so:

(4)
\begin{align} \quad 9(9x) \equiv 9(1) \pmod {10} \\ \quad x \equiv 9 \pmod {10} \end{align}

Thus $x = 9 + 10t$ where $t \in \mathbb{Z}$. Substituting this into our linear diophantine equation gives us:

(5)
\begin{align} \quad 9(9 + 10t) + 10y &= 11 \\ \quad 81 + 90t + 10y &= 11 \\ \quad y &= -7 - 9t \end{align}

So the solutions to $9x + 10y = 11$ are given by $x = 9 + 10t$ and $y = -7 - 9t$ for $t \in \mathbb{Z}$.