Go Back > Math Stuff > Computer Science & Computational Number Theory

Thread Tools
Old 2019-02-23, 02:16   #1
Jan 2018

4310 Posts
Question 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)
MARTHA is offline   Reply With Quote
Old 2019-02-23, 17:02   #2
chris2be8's Avatar
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.

chris2be8 is offline   Reply With Quote
Old 2019-02-23, 18:15   #3
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

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
Dr Sardonicus is offline   Reply With Quote
Old 2019-02-23, 22:14   #4
Jan 2018

43 Posts

Originally Posted by Dr Sardonicus View Post
there is always a solution in positive x, y, and z provided
n > a*b - c
How could I miss that
MARTHA is offline   Reply With Quote
Old 2019-02-23, 23:08   #5
CRGreathouse's Avatar
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.
CRGreathouse is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
square root equal to a negative LaurV Homework Help 34 2013-03-03 09:35
modulo division with negative power ? smslca Math 40 2012-01-10 12:02
Somebody made a numerical mistake Arkadiusz Math 20 2009-12-22 16:07
need help with C++ code (non-negative integers) ixfd64 Programming 11 2008-03-20 01:52
rational powers of negative one 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.