3
$\begingroup$

I found out about getting the integer solutions of ax+by=c on other questions, and I also found out there exists a solution only when gcd(a,b)|c. But then I want to know how many natural solutions(x,y) there are(or how to figure out the number of them), where values a, b, and c are all natural numbers, but only c is given. edit : I forgot to mention an important detail, a+b< c

I tried messing around with it, but got stuck, like the following-

ax+by=c, therefore y=(c-ax)/b, but I can't quite figure it out from this point. My friend told me that I can't solve this because the only given number is c. Is he right? why or why not? This has been bothering me for weeks, so please help me :)

$\endgroup$
3
$\begingroup$

You're right! When you solve the linear diophantine equation $ax+by=c$, this equation has infinite solutions if and only if $gcd(a,b)|c$.

To find all of these solutions, compute $gcd(a,b)$ using the Euclidean algorithm (you only need to find one solution $(x_0,y_0))$. Once you have $(x_0,y_0)$, the other solutions comes in the form:

$$x=x_0+\frac {bk}{gcd(a,b)}$$ $$y=y_0-\frac {ak}{gcd(a,b)}$$

For all integers $k$

Answering your question, it depends on the values of $a$ and $b$, given that for some natural numbers $a,b$ the $gcd(a,b)$ could or could not divide $c$. For instance: $ax+by=12$

If $a=3$ and $b=9$, the equation $3x+9y=12$ has solutions: $$x=1+3k$$ $$y=1-k$$ For all integers $k$

But, if $a=5$ and $b=10$, then $gcd(a,b)=gcd(5,10)=5$ which doesn't divide $c$. Therefore, the equation has no solutions

Hope it helps!


To find all natural solutions restrict values of k for which $x>0$ and $y>0$:

$$x>0 \Rightarrow k>\frac {-x_ogcd(a,b)}{b}$$ $$y>0 \Rightarrow k<\frac {y_ogcd(a,b)}{a}$$

In conclusion:

If $gcd(a,b)$ doesn't divide c, there are no natural solutions

If $gcd(a,b)$ divides c, exists a pair of natural solutions $(x_0,y_0)$ and the equation has a finite set of solutions of the form:

$$x=x_0+\frac {bk}{gcd(a,b)}$$ $$y=y_0-\frac {ak}{gcd(a,b)}$$

For all integers $k$ such that $k\in (\frac {-x_ogcd(a,b)}{b},\frac {y_ogcd(a,b)}{a})$

In other words, the number of natural solutions of the diophantine equation $ax+by=c$ where $c$ is given, is equal to the number of integers in the interval $(\frac {-x_ogcd(a,b)}{b},\frac {y_ogcd(a,b)}{a})$

$\endgroup$
  • $\begingroup$ First of all thanks, now I do see some kind of method of procuring solutions. But I still don't get how this would be used to figure out the number of all possible natural solutions. Oh, I just realized, I should've mentioned a+b<c...sorry. $\endgroup$ – C M Park Aug 7 '17 at 14:54
  • $\begingroup$ Right, I gave you all integer solutions! If $a+b>c$, there are none natural solutions. If $a+b=c$, then you have only one natural solution $(1,1)$. If $a+b<c$, then use the method to find all integer solutions and restrict the values of k for which both $a$ and $b$ are positive. I don't know a formula to solve your equation generally, because it depends on the value of $gcd(a,b)$. If I find some general method, I´ll add it to the post $\endgroup$ – L. Salvetti Aug 7 '17 at 15:08
  • $\begingroup$ Edit: restrict the values of k for which both $x$ and $y$ are positive $\endgroup$ – L. Salvetti Aug 7 '17 at 15:20

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.