0
$\begingroup$

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$

$$ $$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks, I'm going to think about this $\endgroup$ – Jorge Lavín Apr 19 '13 at 10:04
  • $\begingroup$ 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. $\endgroup$ – Jorge Lavín Apr 19 '13 at 10:09
  • 1
    $\begingroup$ Yes, and particularly $gcd(a,b)$ divides $a$ and $b$. $\endgroup$ – Easy Apr 19 '13 at 10:11
  • $\begingroup$ 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 $\endgroup$ – Jorge Lavín Apr 19 '13 at 10:29
  • 1
    $\begingroup$ @Nivalth, see my additional explanation. $\endgroup$ – Easy Apr 20 '13 at 10:56
0
$\begingroup$
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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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