Solution of Linear Diophantine Equation

From ProofWiki

Jump to: navigation, search

Theorem

$ax + by = c$

has solutions iff $\gcd \left\{{a, b}\right\} \backslash c$ (that is, iff $\gcd \left\{{a, b}\right\}$ divides $c$).

If this condition holds with $\gcd \left\{{a, b}\right\} > 1$ then division by $\gcd \left\{{a, b}\right\}$ reduces the equation to:

$a' x + b' y = c'$

where $\gcd \left\{{a', b'}\right\} = 1$.

If $x_0, y_0$ is one solution of the latter equation, then the general solution is:

$\forall k \in \Z: x = x_0 + b' k, y = y_0 - a' k$.

We assume that both $a$ and $b$ are non-zero, otherwise the solution is trivial.

The first part of the problem is a direct restatement of Integer Combinations Multiples of GCD:

The set of all integer combinations of $a$ and $b$ is precisely the set of all integer multiples of the GCD of $a$ and $b$:

$\gcd \left\{{a, b}\right\} \backslash c \iff \exists x, y \in \Z: c = x a + y b$

Now, suppose that $x', y'$ is any solution of the equation.

Then we have:

$a' x_0 + b' y_0 = c'$ and $a' x' + b' y' = c'$.

Substituting for $c'$ and rearranging:

$a' \left({x' - x_0}\right) = b' \left({y_0 - y'}\right)$.

So $a'$ divides $b' \left({y_0 - y'}\right)$.

Since $\gcd \left\{{a', b'}\right\} = 1$, from Euclid's Lemma we have $a'$ divides $y_0 - y'$.

So $y_0 - y' = a' k$ for some $k \in \Z$.

Substituting into the above gives $x' - x_0 = b' k$ and so:

$x' = x_0 + b' k, y' = y_0 - a'k$ for some $k \in \Z$

which is what we claimed.

Substitution again gives that the integers:

$x_0 + b' k, y_0 - a' k$

constitute a solution of $a' x + b' y = c'$ for any $k \in \Z$.

$\blacksquare$