20190223, 02:16  #1 
Jan 2018
43 Posts 
Numerical Semigroups for negative numbers?
To determine whether any solution exist for ax+by+cz=n given all the variables are positive, is effectively possible with the help of Numerical Semigroups algorithm..
but for ax+bycz=N, Numerical semigroups algorithms are not helpful..why these don't work in negative numbers? Is it because it is not explored OR it is just not possible? and finally how to determine whether any solution exist for ax+bycz=n (other than brute force) 
20190223, 17:02  #2 
Sep 2009
3^{2}·13·19 Posts 
Gut feel says that if gcd(a,b,c) divides N there will be an infinite number of solutions. But I can't work out how to prove it, or how to find one.
Chris 
20190223, 18:15  #3 
Feb 2017
Nowhere
23×233 Posts 
I'm assuming then that a, b, and c are all positive and you want x, y, and z all to be positive.
We may assume that g = gcd(a,b,c) is 1 since otherwise we could replace n with g*n and divide through by g. Assuming further that gcd(a, b) = 1, rewriting as a*x + b*y = n + c*z we know there is a solution in positive x and y provided n + c*z > a*b. In particular, taking z = 1 (which is positive), there is always a solution in positive x, y, and z provided n > a*b  c. If gcd(a,b) = g1 > 1 things are more complicated, but under the assumption that gcd(a,b,c) = 1 we have gcd(g1,c) = 1. So, for each possible residue class of n (mod g1) there is a unique residue class for z (mod g1) that will allow solutions. In each case there will be a bound for n, above which solutions are guaranteed to exist. As before, I'm too lazy to work out the details ;) 
20190223, 22:14  #4 
Jan 2018
43 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
square root equal to a negative  LaurV  Homework Help  34  20130303 09:35 
modulo division with negative power ?  smslca  Math  40  20120110 12:02 
Somebody made a numerical mistake  Arkadiusz  Math  20  20091222 16:07 
need help with C++ code (nonnegative integers)  ixfd64  Programming  11  20080320 01:52 
rational powers of negative one  nibble4bits  Math  5  20080108 04:58 