mersenneforum.org Numerical Semigroups for negative numbers?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-23, 02:16 #1 MARTHA   Jan 2018 4310 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 111111110002 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 7·647 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 598510 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.

 Thread Tools

 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 07:42.

Sun May 9 07:42:11 UTC 2021 up 31 days, 2:23, 0 users, load averages: 3.50, 3.42, 3.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.