# Proof explanation for all solutions for linear diophantine equations

I hope I have provided all the information necessary to make my question clear and understandable.

The following theorem is well known in elementary number theory

Theorem. The linear Diophantine equation $ax+by = c$ has a solution if and only if $\, d \vert c \,$ where $d = \text{gcd}(a,b)$. If $x_0$,$y_0$ is any particular solution of this equation, then all other solutions are given by

$$x = x_0 + \bigg(\frac{b}{d}\bigg)t$$ $$y = y_0 - \bigg(\frac{a}{d}\bigg)t$$

where $t$ is an arbitrary integer (bold emphasis added).

Question. How is the transition made from $t$ being an existential integer in the proof to it being an arbitrary integer at the end of the proof?

Proof. We begin with two solutions $(x_0,y_0)$ and $(x\prime, y\prime)$. Then starting with the equation

$$ax_0 + by_0 = c = ax\prime + b\prime$$

we have

$$r(x\prime - x_0) = s(y\prime - y_0)$$

where $r$ and $s$ are relatively prime integers from $a = dr$ and $b = ds$. Consequently, Euclid's Lemma allows us to deduce that $r \vert (y_0 - y\prime)$; or $y_0 - y\prime = rt$ for some integer $t$.

So now we have some integer $t$ such that

$$y_0 - y\prime = rt$$

Substituting, we obtain

$$x\prime - x_0 = st$$

We then have the formulas

$$x\prime = x_0 + st = x_0 + \bigg(\frac{b}{d}\bigg)t$$ $$y\prime = y_0 + rt = y_0 - \bigg(\frac{a}{d}\bigg)$$

But then we show that the integer $t$ has no restrictions as to its values, because

\begin{align} ax\prime+by\prime &= a\bigg[x_0+\bigg(\frac{b}{d}\bigg)t\bigg] + b \bigg[y_0 - \bigg(\frac{a}{d}\bigg)t\bigg] \\ &= a(x_0+by_0) + \bigg(\frac{ab}{d} - \frac{ab}{d}\bigg)t \\ &= c + 0 \cdot t \\ &= c \end{align}

There are an infinite number of solutions of the given equation, one for each value of $t$

$\blacksquare$

I'm confused as to how $t$ can become arbitrary when it is existential. How do we extend the quantifier from existence to universality?

• The solutions of this diophantine equation have a special structure. If we have any special solution $s$ of $ax+by=c$ and an arbitary solution of the homogenous equation $ax+by=0$, lets call it $r$ , then $s+r$ is a solution of $ax+by=c$ as well. And the homogenous solution is $(-bt/at)$ , $t\in \mathbb Z$ , if $a$ and $b$ are coprime. – Peter May 7 '17 at 16:53
• So, if we have a solution, there are infinite many of them and we can parametrize it such that every solution corresponds with an integer number $t$ – Peter May 7 '17 at 16:57
• If I understand what you're saying, because $t$ doesn't affect the solution, we can introduce an arbitrary integer $r$, and replace $t$ with it, which would be parameterized. – Benedict Voltaire May 7 '17 at 22:58
• Until you demonstrated that it was arbitrary, it was only existential. You can consider it to be a happy coincidence or a sign of some deeper, as yet undiscovered, property of numbers. If you have ever used the slope of a line to find more points on that line, this result shouldn't come as a suprise to you. – steven gregory Aug 17 '17 at 6:38