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