20190217, 02:31  #1 
Jan 2018
43 Posts 
Fastest way to check whether ax+by+cz=d has positive integer solutions
Hi again..
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. Is the problem far more complex than it seems? 
20190217, 18:22  #2  
Feb 2017
Nowhere
2×11×263 Posts 
Quote:
There is a wellknown result in the twovariable case: if a and b are positive integers with gcd(a, b) = 1, then a*x + b*y = N is solvable in nonnegative integers x and y for all N > a*b  a  b. So obviously, it will be solvable in positive x and y for N > a*b. You don't need to find exact solutions to know they exist. Checking smaller N, I don't remember how to do that. Now when you increase the number of variables, life becomes more complicated. In particular, you can have gcd(a, b, c) = 1 with gcd(a, b) > 1, gcd(b, c) > 1, and gcd(a, c) > 1 (e.g. a = 2*3, b = 2*5, c = 3*5). Even so, it does not look too hard to show that all "sufficiently large" d will be representable, and to find decent bounds. IIRC there is actually a good algorithm known for making the determination, but I'm too lazy to look it up :D 

20190217, 21:42  #3 
Jan 2018
101011_{2} Posts 
Yes Sir, for any d>"Frobenius number", equation is solvable with positive integers..The Frobeniustype lower bound is also possible to be calculated..
In fact if we keep changing the value of z, the equation is as easy as with two variables, but then it is too slow just to determine.. a trick could be to check whether the positive integer solution exists for: ax+by=d ax+cz=d OR by+cz=d.. if any of the solution exist, ax+by+cz=d is also solvable with positive integers. 
20190218, 13:37  #4 
Aug 2006
5979_{10} Posts 
There's an algorithm in GAP, due to Delgado & Sánchez:
Manuel Delgado and Pedro A. García Sánchez, numericalsgps, a GAP package for numerical semigroups, ACM Communications in Computer Algebra, 50 (2016) 1224. doi:10.1145/2930964.2930966 Code:
gap> LoadPackage("NumericalSgps");  Loading NumericalSgps 0.980 For help, type: ?NumericalSgps:  true gap> s := NumericalSemigroup("generators",101,103,107); <Numerical semigroup with 3 generators> gap> 1000 in s; false gap> 10000 in s; true 
20190218, 14:31  #6 
Aug 2006
3×1,993 Posts 
Would you give an example? I'm not sure which numbers become large.
Last fiddled with by CRGreathouse on 20190218 at 14:32 
20190218, 14:38  #7 
Aug 2006
3·1,993 Posts 
GAP seems to have no problem constructing and working with
Code:
NumericalSemigroup(2^100+1,10^30+1,7^35+1); 
20190218, 14:52  #8  
Jan 2018
43 Posts 
Quote:
thanks again sire !! 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fun with a false positive  Madpoo  Data  12  20160629 19:00 
another false positive?  ixfd64  Data  3  20160314 22:11 
positive LL test?  sixblueboxes  PrimeNet  90  20140724 05:51 
Feature request: integer check on input  Andi47  GMPECM  7  20071021 20:38 
False positive?  Pi Rho  Lounge  4  20030423 14:11 