1
$\begingroup$

According to my notes: $$ \begin{align} & \text{ Let } a,b \text{ not both } 0. \\ & ax+by \text{ has a solution iff } (a,b) \mid c \\ & \text{ If } d:=(a,b) \mid c \text{ and } a=d \cdot a_1 , b=d \cdot b_1 \text{ and } x_1,y_1 \text{ is a solution of } \\ & ax+by=c \text{ , then all the solutions are given by the formulas: } \\ & x=x_1+k \cdot b_1, y=y_1-k \cdot a_1, k \in \mathbb{Z} \end{align} $$

I am looking at the solution of this exercise:

Let $a,b \geq 0 , (a,b)=1$ . Show that the diophantine equation $ax-by=c$ has infinite solutions with $x,y>0$.

That is the solution:

Since $(a,b)=1$ , $\exists x_0,y_0 \text{ such that } ax_0+by_0=1 \Rightarrow a(cx_0)-b(-cy_0)=c$

Therefore, $\displaystyle x_1=cx_0 , y_1=-cy_0 \text{ is a solution of } ax-by=c$

The solutions of $ax-by=c$ are described by the formulas:

$$x=cx_0+kb , y=-cy_0+ka, k\in \mathbb{Z}$$

And,as we want $x>0,y>0$, it must be $\displaystyle k> \max\left\{\frac{-cx_0}{b},\frac{cy_0}{a}\right\}$

But...why are these : $x=cx_0+kb , y=-cy_0+ka, k\in \mathbb{Z}$ the solutions of $ax-by=c$,and not $x=cx_0+kb, y=-cy_0-ka$. Doesn't it have to be at one of $x,y$ , minus and at the other one plus???

$\endgroup$
  • 1
    $\begingroup$ They changed sign on you, are looking at $ax-by=c$. $\endgroup$ – André Nicolas Jun 13 '14 at 17:08
  • $\begingroup$ A ok...I understand...So,if we would have $-ax+by=c$,we would take $x=x_1-k \cdot b_1 \text{ and } y=y_1+k \cdot a_1$,right? $\endgroup$ – evinda Jun 13 '14 at 17:17
  • 1
    $\begingroup$ No, it would be similar to the case $ax-by$, you use the same sign to get the cancellation. $\endgroup$ – André Nicolas Jun 13 '14 at 17:19
  • $\begingroup$ A ok...I got it...thank you very much!!! $\endgroup$ – evinda Jun 13 '14 at 17:23
  • 1
    $\begingroup$ You are welcome. Minus signs give me trouble too. $\endgroup$ – André Nicolas Jun 13 '14 at 17:24
1
$\begingroup$

So that $ax-by = \langle\text{stuff with $c$s}\rangle +akb-bka$ and the last two terms cancel.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I understand...thanks a lot!!! $\endgroup$ – evinda Jun 13 '14 at 17:24

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.