0
$\begingroup$

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!

Improve this question
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Dragoon GT Oct 15 '19 at 9:26
  • $\begingroup$ @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)$. $\endgroup$ – Vladimir Putin Oct 15 '19 at 9:35
  • $\begingroup$ 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? $\endgroup$ – Dragoon GT Oct 15 '19 at 9:41
  • $\begingroup$ 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? $\endgroup$ – Vladimir Putin Oct 15 '19 at 9:45
  • $\begingroup$ 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 $\endgroup$ – Dragoon GT Oct 15 '19 at 9:53

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.