# How do I find natural number solutions?

I'm quite new to number theory and I'm studying diophantine equations. I noticed that the technique was used for solving integer solutions. However, what technique can I use for solving natural number solutions?

For example, $$ax + by = c$$ find natural number solutions for $$a$$ and $$b$$

The only guess I can come up with is to set x and y to be absolute value:

$$a|x| + b|y| = c$$

But I'm not really sure how to solve this. Is there any other way I can go about finding only natural number solutions? Any help would be appreciated, thank you!

Euclidean algorithm guarantees existence of $$a_0x+b_0y=c$$. I am assuming you know how to find one solution. Assuming $$\gcd(x,y)=1$$, I think all solutions are given by

$$a = a_0 + kb_0y \\ b = b_0 - ka_0x$$

I'm not sure how to prove this, though. But if you want to only find all natural number solutions, you just need to find values of $$k$$ such that both $$a$$ and $$b$$ are positive.

[Claim] If $$\gcd(x,y)=d$$ then all solutions are given by $$a = a_0 + k \frac{b_0}{d} y \\ b = b_0 - k \frac{a_0}{d} x$$

• oh okay, so you would just put an equality constraint on a or b >= 1 and solve for that in terms of the other stuff. Got it, thanks! – Dragoon GT Oct 15 '19 at 9:26
• @DragoonGT uniqueness only works if $\gcd(a,b)=1$ though, be careful. For example, $6x+4y=200$ then $(x,y)=(0,50)$. If you only use my formula you will miss the solution $(x,y)=(2,47)$. – Vladimir Putin Oct 15 '19 at 9:35
• Does it work like this? If I solve for a >= 1 in terms of n and b >= 1 in terms of n, I will get 2 inequality constraints for n. Hence, that means that every integer value of n in between those 2 bounds is the natural number solution set right? – Dragoon GT Oct 15 '19 at 9:41
• well, if you are not computing solutions by hand and you have a program to do it, you can just ask it to compute all solutions and "cherry-pick" the ones that satisfy your constraints (natural numbers). Why do you need inequality constraints when solving this equation? – Vladimir Putin Oct 15 '19 at 9:45
• So basically, I have to do a math project at my school on any topic where you use an advanced calculus/math topic to solve a real-world problem. I decided to do it on a purely mathematical approach to dynamic programming. Because a lot of the times dynamic programming involves natural number optimization solutions in the real world, I needed to learn some number theory for that. I'm trying NOT to use comp sci for this – Dragoon GT Oct 15 '19 at 9:53