Solution of Linear Diophantine Equation
Theorem
The linear Diophantine equation:
- $a x + b y = c$
has solutions if and only if:
- $\gcd \set {a, b} \divides c$
where $\divides$ denotes divisibility.
If this condition holds with $\gcd \set {a, b} > 1$ then division by $\gcd \set {a, b}$ reduces the equation to:
- $a' x + b' y = c'$
where $\gcd \set {a', b'} = 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$
or:
- $\forall k \in \Z: x = x_0 + \dfrac b d k, y = y_0 - \dfrac a d k$
where $d = \gcd \set {a, b}$.
Proof
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 Set of Integer Combinations equals Set of Multiples of GCD:
The set of all integer combinations of $a$ and $b$ is precisely the set of integer multiples of the GCD of $a$ and $b$:
- $\gcd \set {a, b} \divides 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' \paren {x' - x_0} = b' \paren {y_0 - y'}$
So:
- $a' \divides b' \paren {y_0 - y'}$
Since $\gcd \set {a', b'} = 1$, from Euclid's Lemma we have:
- $a' \divides \paren {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$
Examples
Example: $15 x + 27 y = 1$
The linear diophantine equation:
- $15 x + 27 y = 1$
has no solutions for $x$ and $y$ integers.
Example: $5 x + 6 y = 1$
The linear diophantine equation:
- $5 x + 6 y = 1$
has the general solution:
- $x = -1 + 6 t, y = 1 - 5 t$
Sources
- 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {2-3}$ The Linear Diophantine Equation: Theorem $\text {2-4}$