# Linear diophantine equation solution existence

Given the linear diophantine equation

$$ax+by=c$$

I have to show that it has solution if and only if $gcd(a,b)$ divides $c$.

$$1)\Rightarrow$$

Let $m=gcd(a,b)$ then

$$a'x+b'y=c'$$

where $gcd(a',b')=1$, but how can I continue from here?

$$2) \Leftarrow$$

I don't know even how to start. I've never studied seriously number theory until now, and I'm self-studying so this is difficult to me. Any help will be appreciated.

Should I use the division theorem? I mean that, for $a,b\neq0 \in \mathbb{Z}$ there exists numbers $q, 0\leq r <|b|$ such that $a=bq+r$



-

$\Rightarrow)$Every number that divides $a$ and $b$ divides $c$, so $gcd(a,b)|c$.

$\Leftarrow)$If $gcd(a,b)|c$, then $\frac{a}{gcd(a,b)}x+\frac{b}{gcd(a,b)}y=\frac{c}{gcd(a,b)}$ has a solution. Here $\frac{a}{gcd(a,b)}$ and $\frac{b}{gcd(a,b)}$ are coprime. In other words, you need to show: if $a,b$ coprime, then there exists $x,y$ such that $ax+by=1$. To show this, you need to use Euclidean algorithm.

Showing $a,b$ coprime $\Rightarrow ax+by=1$.

With loss of generality, assume $a>b>0$. By division we have $$a=bq+r_1$$where $0<r_1<b$. Notice that $gcd(b,r_1)|a$, and hence $gcd(b,r_1)=1$ as $a,b$ coprime. Similarly, we have $$b=r_1q_1+r_2$$with $gcd(r_1,r_2)|b$ and so $gcd(r_1,r_2)=1$ since $b,r_1$ coprime. Continue this division and say it eventually stops at $$r_{n-1}=r_nq_n$$Then $r_n=1$ since $gcd(r_{n-1},r_n)=1$.

For simplicity, let us assume $r_2=1$. Then $r_1q_1=b-1$. Subing in the first equation gives $$aq_1=bq+(b-1)$$which is what you want.

-
the $\Rightarrow$ part. I understand that given the equation, every number that divides $ax$ and $by$ divides $c$ and hence every number that divides $a$ and $b$ divides $c$?. I'm kind of confused with this implication, sorry. –  Jorge Apr 19 '13 at 10:09
Yes, and particularly $gcd(a,b)$ divides $a$ and $b$. –  Easy Apr 19 '13 at 10:11
the $\Leftarrow$ part: I don't see how the equation $ax+by=1$ comes. Does $a$ there mean $a'=\frac{a}{gcd(a,b)}$ and the same for $b$?. I don't see how the Euclidean algorithm may help me showing that $1=ax+by$. Shall I use it to $gcd(a',b')=1$ and find that indeed there exists $x$ and $y$ that solve the equation? Thanks for your time –  Jorge Apr 19 '13 at 10:29
@Nivalth, see my additional explanation. –  Easy Apr 20 '13 at 10:56
m = gcd(a, b)

a = m*i
b = m*j

a*x + b*y = c
m*i*x + m*j*y = c
m * (i*x + j*y) = c


so the first equation have a solution then you should be able to write c in a form:

c = m * k
k = i*x + j*y

-