mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-02-23, 02:16   #1
MARTHA
 
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
 
chris2be8's Avatar
 
Sep 2009

111111110002 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2019-02-23, 18:15   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

7·647 Posts
Default

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
MARTHA
 
Jan 2018

43 Posts
Default

Quote:
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
 
CRGreathouse's Avatar
 
Aug 2006

598510 Posts
Default

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
Reply

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.