Fastest way to check whether $ax+by+cz=d$ has positive integer solutions, exact solutions are not required

Asked Feb 16 '19 at 00:25

Active Feb 16 '19 at 01:02

Viewed 128 times

What is the fastest way to check whether $ax+by+cz=d$ has positive integer solutions, exact solutions are not required.

We know if $\gcd(a,b,c)$ is not a factor of $d$, it does not have solutions, but if it is factor it can not guarantee of existence of solution.

edited Feb 16 '19 at 01:02

Akira

asked Feb 16 '19 at 00:25

martha

"but if it is factor it can not guarantee of existence of solution." Why not? Have you tried to prove that or find a counter example. – fleablood Feb 16 '19 at 00:35
Because she wants the solutions to be positive. – Robert Shore Feb 16 '19 at 00:38
1

See the Frobenius Coin Problem. – Bill Dubuque Feb 16 '19 at 01:02
For any fixed number of coin denominations, there is an algorithm computing the Frobenius number in polynomial time: http://web.iitd.ac.in/~atripath/publications/FP_3-var.pdf But it is perhaps not able to answer my question.. – martha Feb 16 '19 at 03:44

0 Answers0