# 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)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)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)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$.