1. ## Diophantine question

Hi plz give me a help to find the answer for following

If $\displaystyle a \ne 0$, gcd(a,b)=g and $\displaystyle (x_0,y_0)$ is a solution of $\displaystyle ax+by=c$ then show that
$\displaystyle x=x_0+\frac{b}{g}t$, $\displaystyle y=y_0-\frac{a}{g}t$

2. What is $\displaystyle t$ ?

3. Originally Posted by dhammikai
Hi plz give me a help to find the answer for following

If $\displaystyle a \ne 0$, gcd(a,b)=g and $\displaystyle (x_0,y_0)$ is a solution of $\displaystyle ax+by=c$ then show that
$\displaystyle x=x_0+\frac{b}{g}t$, $\displaystyle y=y_0-\frac{a}{g}t$
Here we are dealing with integer solution of
$\displaystyle ax+by=c$

Since,
$\displaystyle (x_0,y_0)$ is a solution
$\displaystyle ax+by=ax_0+by_0$
$\displaystyle a(x-x_0)+b(y-y_0)=0$
Since there are infinite integer solution(why?), let us introduce an integer parameter m such that $\displaystyle x-x_0=m$
It becomes
$\displaystyle am+b(y-y_0)=0$
$\displaystyle y-y_0=\frac{am}{b}$
Now, to ensure that RHS is always an integer, make substitution $\displaystyle m=\frac{bt}{g}$....where t is new integer parameter.

4. (1) ax + by = c
(2) $\displaystyle ax_{0} + by_{0} = c$ is an integer solution.

Subtracting (2) from (1),
$\displaystyle a\left(x-x_{0}\right)+b\left(y-y_{0}\right)=0$.

Now
(*) $\displaystyle \frac{a}{g}\left(x-x_{0}\right)=-\frac{b}{g}\left(y-y_{0}\right)$.

Thus
$\displaystyle \frac{b}{g}\mid \frac{a}{g}\left(x-x_{0}\right)$. But $\displaystyle \left(\frac{b}{g},\frac{a}{g}\right)=1$ therefore,

$\displaystyle \frac{b}{g}\mid \left(x-x_{0}\right)$. Hence it follows that there is a $\displaystyle t \in \mathbb{Z}$ such that

(3) $\displaystyle x-x_{0} = t \frac{b}{g}$. Substituting this in (*),

$\displaystyle \frac{a}{g} \cdot t\frac{b}{g} = -\frac{b}{g}\left(y-y_{0}\right)$. Hence $\displaystyle y-y_{0}=-t\frac{a}{g}$

Therefore, from above and (3),
$\displaystyle x = x_{0} + t\frac{b}{g}$

$\displaystyle y=y_{0}-t\frac{a}{g}$
$\displaystyle QED$

5. OK Thanks, I got the idea for the answer, thanks again