Solving Linear Diophantine Equations with Congruences

Solving Linear Diophantine Equations with Congruences

Recall that a linear diophantine equation assumes the form $ax + by = c$, or rather, $ax = c + b(-y)$. But this is essentially the same form as a congruence. Recall that $a \equiv b \pmod m$ implies that $a = b + km$ for some k. Hence we can say that the linear diophantine equation $ax = c + b(-y)$ can be turned into a congruence. Additionally, by = c + a(-x) can also be turned into congruences, namely:

(1)
\begin{align} ax \equiv c \pmod b \quad \mathbf{or} \quad by \equiv c \pmod a \end{align}

If we solve one of these congruences, then we will obtain solutions for the linear diophantine equation corresponding to them.

Example 1

Using congruences, solve linear diophantine equation $9x + 10y = 11$.

We know that $9x \equiv 11 \pmod {10}$. Now let's solve this congruence by finding and inverse of 9 (mod 10). By inspection, 9 is a good choice. Hence we obtain that $(9)9x \equiv (9)11 \pmod {10}$, or rather $x \equiv 99 \pmod {10}$ which is not in least residue, so more appropriately, $x \equiv 9 \pmod {10}$. Hence, $x = 9 + 10t$ for $t \in \mathbb{Z}$.

Now we must substitute this into our original equation:

(2)
\begin{align} 9x + 10y = 11 \\ 9(9 + 10t) + 10y = 11 \\ 81 + 90t + 10y = 11 \\ 90t + 10y = -70 \\ 10y = -70 - 90t \\ y = -7 - 9t \end{align}

Hence the solutions to our linear diophantine equation is $x = 9 + 10t$ and $y = -7 - 9t$.

Example 1.1

Solve the linear diophantine equation, $9x + 10y = 11$ using just the division algorithm.

We will now verify our solutions from (1):

(3)
\begin{align} 10 = 9(1) + 1 \\ 1 = 10(1) + 9(-1) \\ 11 = 10(11) + 9(-11) \\ \end{align}

Hence $x = -11 + 10t$ and $y = 11 - 9t$ where $t \in \mathbb{Z}$. But these equation are the same as the original. Adding multiples of 10 and 9 to our solution equations we get: $x = 9 + 10t$ and $y = -7 -9t$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License