0

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!

Dragoon GT
  • 11

1 Answers1

1

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

user651267
  • 500
  • 2
  • 16
  • 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 09: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)$. – user651267 Oct 15 '19 at 09: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 09: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? – user651267 Oct 15 '19 at 09: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 09:53