# How do I calculate the number of natural solutions of ax+by=c?

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 :)

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})$

• 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. – C M Park Aug 7 '17 at 14:54
• 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 – L. Salvetti Aug 7 '17 at 15:08
• Edit: restrict the values of k for which both $x$ and $y$ are positive – L. Salvetti Aug 7 '17 at 15:20