Diophantine Equations

Linear Diophantine Equation

A linear diophantine equation is an equation of the form

a x + b y = c

where

a, b, c \in ℤ

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

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

a x + b y = c

has solutions if and only if

\gcd (a, b) | c

$⟹$ Let $g : = \gcd (a, b)$ and suppose that $x_{0}, y_{0}$ is a solution so that $a x_{0} + b y_{0} = c$ since $g | a, b$ we know that $g | a x_{0} + b y_{0}$ therefore $g | c$ as needed.

$⟸$ Recall that we have some $x_{0}, y_{0} \in ℤ$ such that $\gcd (a, b) = a x_{0} + b y_{0}$ since $g | c$ so $c = g k$ for some $k \in ℤ$ thus multiplying our previous equation by $k$ we obtain $c = g k = a (k x_{0}) + b (k y_{0})$

One Solution Yields Infinitely Many

Suppose that

a x_{0} + b y_{0} = c

is a solution and

d : = \gcd (a, b)

, then the entire set of solutions is given by:

S : = {(x_{0}, y_{0}) + t (\frac{b}{d}, - \frac{a}{d}) : t \in ℤ}

Taking

s \in S

then we see that

s = (x_{0} + t \frac{b}{d}, y_{0} - t \frac{a}{d})

Now, let's confirm that this is a solution, so we have to make sure that

a s_{1} + b s_{2} = c

a (x_{0} + t \frac{b}{d}) + b (y_{0} - t \frac{a}{d}) = a x_{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 $(x_{0}, y_{0})$ is a solution, so let $x_{1}, y_{1}$ be a different solution, then we have $a x_{1} + b y_{1} = c = a x_{0} + b y_{0} ⟺ a (x_{1} - x_{0}) = - b (y_{1} - y_{0})$ dividing through by $g : = \gcd (a, b)$ we see that $\frac{a}{g} (x_{1} - x_{0}) = \frac{- b}{g} (y_{1} - y_{0})$ but then recall that $\gcd (\frac{a}{g}, \frac{b}{g}) = 1$ thus by forced division, we see that $\frac{a}{g} | y_{1} - y_{0}$ so that there is some $k \in ℤ$ such that $y_{1} - y_{0} = \frac{a}{g} k$ thus $\frac{a}{g} (x_{1} - x_{0}) = \frac{- b}{g} (y_{1} - y_{0}) ⟺ \frac{a}{g} (x_{1} - x_{0}) = \frac{- b}{g} (\frac{a}{g} k)$ 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 $(x_{1}, y_{1}) = (x_{0} - k \frac{b}{g}, y_{0} + k \frac{a}{g})$ so therefore $(x_{1}, y_{1}) \in S$ as needed.

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

For any

a, b \in ℤ

the set

S : = {a x + b y : x, y \in ℤ}

is precisely the set of all integral multiples of

\gcd (a, b)

For notational ease, let $g : = \gcd (a, b)$ . Recall that $\gcd (\frac{a}{g}, \frac{b}{g}) = 1$ iff there are some $x, y \in ℤ$ such that $\frac{a}{g} x + \frac{b}{g} y = 1$ if and only if $a (d x) + b (d y) = d g$

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