Linear Diophantine Equation

A linear diophantine equation is an equation of the form
\[
ax + by = c
\]
where \( a, b, c \in \mathbb{ Z } \)

Note that while we know that there are infinitely many solutions to the above equation if we're seaching in \( \mathbb{ R } ^ 2 \) but it's not clear if there is even one solution when we restrict \( x, y \in \mathbb{ Z } \)

A Linear Diophantine Equation Has Solutions if the GCD of the coefficients divides the Constant

\( ax + by = c \) has solutions if and only if \( \gcd \left( a, b \right) \mid c \)

\( \implies \) Let \( g := \gcd \left( a, b \right) \) and suppose that \( x _ 0, y _ 0 \) is a solution so that \( a x _ 0 + b y_ 0 = c \) since \( g \mid a, b \) we know that \( g \mid ax _ 0 + b y _ 0 \) therefore \( g \mid c \) as needed.

\( \impliedby \) Recall that we have some \( x _ 0, y _ 0 \in \mathbb{ Z } \) such that \( \gcd \left( a, b \right) = a x _ 0 + b y _ 0 \) since \( g \mid c \) so \( c = gk \) for some \( k \in \mathbb{ Z } \) thus multiplying our previous equation by \( k \) we obtain \[ c = gk = a \left( k x _ 0 \right) + b \left( k y _ 0 \right) \]

One Solution Yields Infinitely Many

Suppose that \( a x _ 0 + b y _ 0 = c \) is a solution and \( d := \gcd \left( a, b \right) \) , then the entire set of solutions is given by:
\[
S := \left\{ \left( x _ 0, y _ 0 \right) + t \left( \frac{b}{d} , - \frac{a}{d} \right) : t \in \mathbb{ Z } \right\}
\]

Taking \( s \in S \) then we see that
\[
s = \left( x _ 0 + t \frac{b}{d}, y _ 0 - t \frac{a}{d} \right)
\]
Now, let's confirm that this is a solution, so we have to make sure that \( a s _ 1 + b s _ 2 = c \).
\[
a \left( x _ 0 + t \frac{b}{d} \right) + b \left( y _ 0 - t \frac{a}{d} \right) = ax _ 0 + b y _ 0 + 0 = c
\]
therefore every element in \( S \) is a solution, but let's now show that it contains all solutions.

We already know that \( \left( x _ 0, y _ 0 \right) \) is a solution, so let \( x _ 1, y _ 1 \) be a different solution, then we have \[ ax _ 1 + b y _ 1 = c = a x _ 0 + b y _ 0 \iff a \left( x _ 1 - x _ 0 \right) = - b \left( y _ 1 - y _ 0 \right) \] dividing through by \( g := \gcd \left( a, b \right) \) we see that \( \frac{a}{g} \left( x _ 1 - x _ 0 \right) = \frac{-b}{g} \left( y _ 1 - y _ 0 \right) \) but then recall that \( \gcd \left( \frac{a}{g} , \frac{b}{g} \right) = 1 \) thus by forced division, we see that \( \frac{a}{g } \mid y _ 1 - y _ 0 \)so that there is some \( k \in \mathbb{ Z } \) such that \( y _ 1 - y _ 0 = \frac{a}{g} k \) thus \[ \frac{a}{g} \left( x _ 1 - x _ 0 \right) = \frac{-b}{g} \left( y _ 1 - y _ 0 \right) \iff \frac{a}{g} \left( x _ 1 - x _ 0 \right) = \frac{-b}{g} \left( \frac{a}{g} k \right) \] therefore by cancellation we have that \( x _ 1 - x _ 0 = - \frac{b}{g} k \) and symmetrically \( y _ 1 - y _ 0 = \frac{a}{g} k \) therefore \[ \left( x _ 1, y _ 1 \right) = \left( x _ 0 - k \frac{b}{g} , y _ 0 + k \frac{a}{g} \right) \] so therefore \( \left( x _ 1, y _ 1 \right) \in S \) as needed.

The Set of Linear Combinations Are All Integral Multiples of Their GCD

For any \( a, b \in \mathbb{ Z } \) the set
\[
S : = \left\{ ax + b y: x, y \in \mathbb{ Z } \right\}
\]
is precisely the set of all integral multiples of \( \gcd \left( a, b \right) \)

For notational ease, let \( g := \gcd \left( a, b \right) \). Recall that \( \gcd \left( \frac{a}{g} , \frac{b}{g} \right) = 1 \) iff there are some \( x, y \in \mathbb{ Z } \) such that \( \frac{a}{g} x + \frac{b}{g} y = 1 \) if and only if \( a \left( dx \right) + b \left( dy \right) = dg \)

This observation tells us that any integer multiple of \( g \) is in \( S \). Now supose we have \( ax + by \in S \), we want to show this is a multiple of \( g \), equivalently we want to show that \( g \mid ax + by \), but this is certainly true becuase \( \frac{ax + by}{g} = \left( \frac{a}{g} \right)x + \left( \frac{b}{g} \right) y \in \mathbb{ Z } \) so it does