Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

$$ $$

share|improve this question

1 Answer 1

$\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.

share|improve this answer
    
Thanks, I'm going to think about this –  Jorge Apr 19 '13 at 10:04
    
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
1  
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
1  
@Nivalth, see my additional explanation. –  Easy Apr 20 '13 at 10:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.