Let \(a\), \(b\) and \(c\) be integers where \(a\) and \(b\) are non-zero. Consider the following equation

$$ \begin{align*} ax + by = c \end{align*} $$

This is called a linear Diophantine equation. We’re interested in only the integers solution to this equation (lattice points). Since we have two variables, then we know that there is either infinitely many solution or none. When do we have a solution? First a Corollary based on the Divison Algorithm / Euclidean Algorithm.

Corollary 2-1
If \(d = \gcd(a,b)\), then there exists integers \(x\) and \(y\) such that $$ \begin{align*} ax + by = d \end{align*} $$

Proof: TODO but based on the Euclidean Algorithm .. just backtrack.

Next, we have

Corollary 2-2
In order that there exist integers \(x\) and \(y\) satisfying $$ \begin{align*} ax + by = c \end{align*} $$ it is necessary and sufficient that \(d \mid c\), where \(d = \gcd(a,b)\)

Proof: Suppose \(ax + by = c\). Let \(\gcd(a,b) = d\). Then, \(a = ed\), \(b = fd\) for some \(e,f \in \mathbf{Z}\). Then

$$ \begin{align*} c = (ed)x + (fd)y = d(ex + fy) \end{align*} $$

Therefore, we must have that \(d \mid c\). For the other direction, suppose that \(d = \gcd(a,b)\). Then, by Corollary 2-1, there exists integers \(x'\) and \(y'\) such that

$$ \begin{align*} ax' + by' = d \end{align*} $$

But we’re given that \(d \mid c\) so \(c = dk\) for some \(k \in \mathbb{Z}\). Multiply the previous equation by \(k\) to see that

$$ \begin{align*} akx' + bky' = dk \\ a(kx') + b(ky') = c \end{align*} $$

So set \(x = kx'\) and \(y = ky'\) to be a solution. \(\ \blacksquare\)

How to Find a Solution

So now suppose that we have an equation like

$$ \begin{align*} ax + by = c \end{align*} $$

and suppose that \(\gcd(a,b) = d \mid c\). First, we find an integer \(k\) such that \(dk = c\). Then, divide the equation by \(k\) to get

$$ \begin{align*} aw_0 + bz_0 = d \end{align*} $$

Now let

$$ \begin{align*} x_0 = w_0k \quad \text{ and } \quad y_0 = z_0k \end{align*} $$

\((x_0,y_0)\) is a solution to the equation \(ax + by = c\). To find all the other solutions, suppose that \((x',y')\) is a solution too. Then

$$ \begin{align*} ax' + by' = c = ax_0 + by_0 \end{align*} $$

Divide the whole equation by \(d\) to get

$$ \begin{align*} \frac{a}{d}x' + \frac{b}{d}y' &= c = \frac{a}{d}x_0 + \frac{b}{d}y_0 \\ \end{align*} $$

Therefore,

$$ \begin{align*} \frac{a}{d}(x' - x_0) &= \frac{b}{d}(y_0 - y') \end{align*} $$

But now since \(\gcd(a/d,b/d)=1\), then

$$ \begin{align*} \frac{b}{d} \mid (x' - x_0) \end{align*} $$

Hence, there exists some \(t\) such that

$$ \begin{align*} \frac{b}{d}t &= (x' - x_0) \end{align*} $$

But this gives the following solution

$$ \begin{align*} x' &= x_0 + \frac{b}{d}t \quad \text{ and } \quad y' = y_0 - \frac{a}{d}t \end{align*} $$

To verify this, observe that

$$ \begin{align*} a(x_0 + \frac{b}{d}t) + b(y_0 - \frac{a}{d}t) &= ax_0 + \frac{ab}{d}t + by_0 - \frac{ab}{d}t \\ &= ax_0 + by_0 = c. \ \blacksquare \end{align*} $$

Stated as a theorem

Theorem 2-4
The linear Diophantine Equation $$ \begin{align*} ax + by = c \end{align*} $$ has a solution if and only if \(d \mid c\), where \(d = \gcd(a,b)\). Furthermore, if \((x_0,y_0)\) is a solution of this equation, then the set of solutions of the equation consists of all integer pairs \((x,y)\), where $$ \begin{align*} x &= x_0 + \frac{b}{d}t \quad \text{ and } \quad y = y_0 - \frac{a}{d}t \quad \quad t=...,-2,-1,0,1,2,... \end{align*} $$

Solutions Modulo \(b\)

Before doing an example, consider finding solutions modulo \(b\). That is

$$ \begin{align*} ax + by &\equiv c \pmod{b} \\ ax &\equiv c \pmod{b} \end{align*} $$

The congruence is just a special case of the linear Diophantine equation. By Theorem 2-4, this has a solution if and only if \(\gcd(a,b) \mid c\). Moreover, if we take

$$ \begin{align*} ax &\equiv 1 \pmod{b} \end{align*} $$

then again, by theorem 2-4, this has a solution if and only if \(\gcd(a,b) \mid 1\). That is, \(\gcd(a,b) = 1\) or \(a\) and \(b\) are coprime.

Example

Suppose we want to solve

$$ \begin{align*} 23x + 29y = 25 \end{align*} $$

Then, \(\gcd(23,29) = 1\). \(1 \mid 25\) so there is a solution. To find an initial solution \((x_0,y_0)\), we need to use the Euclidean Algorithm as follows

$$ \begin{align*} 29 &= 1 \cdot 23 + 6 \\ 23 &= 3 \cdot 6 + 5 \\ 6 &= 1 \cdot 5 + 1 \\ 5 &= 5 \cdot 1 \end{align*} $$

Then we work backwards to find the coefficients

$$ \begin{align*} 1 &= 6 - 1 \cdot 5 \\ 1 &= 6 - 1 \cdot (23 - 3 \cdot 6) \\ 1 &= 6 - 23 \cdot 1 + 3 \cdot 6 \\ 1 &= 4 \cdot 6 - 23 \cdot 1 \\ 1 &= 4 \cdot (29 - 1 \cdot 23) - 23 \cdot 1 \\ 1 &= 4 \cdot 29 - 4 \cdot 23 - 23 \cdot 1 \\ 1 &= 4 \cdot 29 - 5 \cdot 23 \\ \end{align*} $$

so \(x_0=-5\) and \(y_0=4\) is an initial solution to \(23x + 29y = 1\). We want to solve \(23x + 29y = 25\). Therefore, the initial solution is \((25 \cdot -5, 4 \cdot 25) = (-125, 100)\). To find the remaining solutions, we use the theorem to get

$$ \begin{align*} x &= -125 + \frac{29}{1}t = -125 + 29t \\ y &= 100 - \frac{23}{1}t = 100 - 23t. \end{align*} $$

References

  • Number Theory by George E. Andrews
  • Math310 Class Notes by Matthias Beck