mersenneforum.org Numerical Semigroups for negative numbers?
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-23, 02:16 #1 MARTHA   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+by-cz=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+by-cz=n (other than brute force)
 2019-02-23, 17:02 #2 chris2be8     Sep 2009 32·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
 2019-02-23, 18:15 #3 Dr Sardonicus     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 ;-)
2019-02-23, 22:14   #4
MARTHA

Jan 2018

43 Posts

Quote:
 Originally Posted by Dr Sardonicus there is always a solution in positive x, y, and z provided n > a*b - c
How could I miss that

 2019-02-23, 23:08 #5 CRGreathouse     Aug 2006 3×1,993 Posts Not that you need more reasons, but a numerical semigroup is defined as the natural numbers minus a finite subset of the positive integers. Negative numbers aren't allowed, by definition.

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Homework Help 34 2013-03-03 09:35 smslca Math 40 2012-01-10 12:02 Arkadiusz Math 20 2009-12-22 16:07 ixfd64 Programming 11 2008-03-20 01:52 nibble4bits Math 5 2008-01-08 04:58

All times are UTC. The time now is 11:50.

Sun Jan 23 11:50:45 UTC 2022 up 184 days, 6:19, 0 users, load averages: 1.33, 1.26, 1.22