4. Diophantine Equations

For equations like $x^2+y^2 = 1$ and $3x + 4y = 8$, it is easy to find a solution satisfying the equations when $(x,y)$ are reals. Actually there are infinitely many solutions to both equations $x^2 + y^2 = 1$ and $3x+4y = 8$. However, if we restrict our solutions to certain number, e.g. rational numbers, integers, and positive integers, then the equation might have finite solutions or no solution. If we restrict our self to rational numbers, integers and positive integers, then we call the equation to be diophantine equations. In today's post we observe the linear diophantine equation,

$ax+by=c$

where $a,b, c \in \mathbb{Z}$. 

From now on, the solution is assumed to be integers.

Lemma 1: If $x_0, y_0$ is a solution to $ax+by=c$, then so is

$x_0-bt, y_0+at$ 

for all integer $t \in \mathbb{Z}$.

Proof) It is clear that $ab - ba = 0$, hence $-b, a$ becomes the solution to the equation

$ax+by = 0$

Hence multiplying $t$ on both side we have that the solution is of the form $-bt, at$.

$ax_0+ by_0 = c$

$a(-bt)+ b(at) = 0$

If we add the two equations, then we get, 

$a(x_0-bt) + b(y_0 + at) = c$

hence the result follows. 

Lemma 2: If $(a,b) \not \mid c$, then $ax+by = c$ has no solution, and if $(a,b)|c$, then $ax+by=c$ has a solution.
Proof) Suppose there is a solution, then $ax_0 + by_0 = c$. As $(a,b) | ax_0$ and $(a,b) | by_0$, we get $(a,b) | c$. Conversely,  if $(a,b)|c$, then there exists $q$ such that $c = q(a,b)$. We know that there exists $x', y'$ such that $ax' + by' = (a,b)$, then $a(x'q) + b(y'q) = q(a,b) = c$, hence there is a solution.

Lemma 3: Suppose that $(a,b) = 1$ and $x_0, y_0$ is a solution of $ax+by=c$. Then all solutions of $ax+by = c$ are given by

$x=x_0 - bt$

$y=y_0 +at$

with $t \in \mathbb{Z}$.

Proof) We know that there exists a solution $x_0, y_0$ from lemma 2 above. Then suppose there exists another solution $u,v$, then we have that $0 = a(x_0 - u) + b(y_0 - v)$. Then because $b| a(x_0 - u) \Rightarrow b|(x_0 - u)$, hence there exists some $t$ such that$ u = x_0 - bt$. Then plugging back to the original equation, we get

$abt + b(y_0 -v) = 0 \Rightarrow at +y_0 -v = 0$

hence $v = y_0 + at$, which completes the proof.

Theorem: The equation $ax+by=c$ does not have a solution if $(a,b) \not \mid c$, and has infinitely many solutions if $(a,b) | c$ with the form

$\displaystyle x = x_0 - \frac{b}{gcd(a,b)} t$

$\displaystyle y = y_0 - \frac{a}{gcd(a,b)}t$

as $ax + by = c \Rightarrow (a/gcd(a,b))x + (b/gcd(a,b))y = c/gcd(a,b)$, then the coefficients of $x,y$ becomes coprime.