Solution of Linear Diophantine Equation

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Solution_of_Linear_Diophantine_Equation&oldid=555771"