

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


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|cite|improve this question

$\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|cite|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
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
share|cite|improve this answer

Your Answer


