Mixing
Find the number of non-negative integer solutions to linear systems
For instance with two variables: $ax + by = c$, where x and y are variables.
I found these two threads [1, 2], where the solution is equal to $binom{n+p-1}{p-1}$, where n is the desired sum and p is the number of variables, so for the case above it would be $binom{c+2-1}{2-1}$. This is then divided by the product of the numbers multiplying the variables, so in this case by $a*b$. If the result is not an integer, it's rounded down. All in all: $lfloorfrac{binom{c+2-1}{2-1}}{ab}rfloor$.
This works for many equations, but I have found one where it doesn't, and I have no idea why and how to solve it. The problematic equation is the following:
$$54x+177y=81630.$$
Here the number of solutions should be 26, the solution above however gives 8. How do I get to 26?
elementary-number-theory discrete-mathematics diophantine-equations linear-diophantine-equations
asked Nov 16 '18 at 22:37
Drejk
83
|
show 8 more comments
For instance with two variables: $ax + by = c$, where x and y are variables.
I found these two threads [1, 2], where the solution is equal to $binom{n+p-1}{p-1}$, where n is the desired sum and p is the number of variables, so for the case above it would be $binom{c+2-1}{2-1}$. This is then divided by the product of the numbers multiplying the variables, so in this case by $a*b$. If the result is not an integer, it's rounded down. All in all: $lfloorfrac{binom{c+2-1}{2-1}}{ab}rfloor$.
This works for many equations, but I have found one where it doesn't, and I have no idea why and how to solve it. The problematic equation is the following:
$$54x+177y=81630.$$
Here the number of solutions should be 26, the solution above however gives 8. How do I get to 26?
elementary-number-theory discrete-mathematics diophantine-equations linear-diophantine-equations
asked Nov 16 '18 at 22:37
Drejk
83
Would it help to first divide by gcd of coefficients?
– coffeemath
Nov 16 '18 at 23:08
1
@coffeemath Yes it would, must have misunderstood that part in the linked threads. Thanks.
– Drejk
Nov 17 '18 at 0:06
I also noticed that if a and b are equal, and the number of solutions comes out greater than 1, it will be equal to 1.
– Drejk
Nov 17 '18 at 1:37
The equation $2x+3y=6$ has two nonnegative solutions, $(3,0),(0,2).$ But the formula gives floor of $7/6$ which is $1.$ Also in the link 1 only positive solutions were considered, and here there are none.
– coffeemath
Nov 17 '18 at 10:16
@coffeemath I think somebody here mentioned that it's for non-negative, but I can see it doesn't always work out. I think you could solve this by adding 1 to the result if a solution where x or y is equal to 0 exists (which is easy to check).
– Drejk
Nov 18 '18 at 4:11
|
show 8 more comments
For instance with two variables: $ax + by = c$, where x and y are variables.
I found these two threads [1, 2], where the solution is equal to $binom{n+p-1}{p-1}$, where n is the desired sum and p is the number of variables, so for the case above it would be $binom{c+2-1}{2-1}$. This is then divided by the product of the numbers multiplying the variables, so in this case by $a*b$. If the result is not an integer, it's rounded down. All in all: $lfloorfrac{binom{c+2-1}{2-1}}{ab}rfloor$.
This works for many equations, but I have found one where it doesn't, and I have no idea why and how to solve it. The problematic equation is the following:
$$54x+177y=81630.$$
Here the number of solutions should be 26, the solution above however gives 8. How do I get to 26?
elementary-number-theory discrete-mathematics diophantine-equations linear-diophantine-equations
asked Nov 16 '18 at 22:37
Drejk
83
For instance with two variables: $ax + by = c$, where x and y are variables.
I found these two threads [1, 2], where the solution is equal to $binom{n+p-1}{p-1}$, where n is the desired sum and p is the number of variables, so for the case above it would be $binom{c+2-1}{2-1}$. This is then divided by the product of the numbers multiplying the variables, so in this case by $a*b$. If the result is not an integer, it's rounded down. All in all: $lfloorfrac{binom{c+2-1}{2-1}}{ab}rfloor$.
This works for many equations, but I have found one where it doesn't, and I have no idea why and how to solve it. The problematic equation is the following:
$$54x+177y=81630.$$
Here the number of solutions should be 26, the solution above however gives 8. How do I get to 26?
elementary-number-theory discrete-mathematics diophantine-equations linear-diophantine-equations
elementary-number-theory discrete-mathematics diophantine-equations linear-diophantine-equations
asked Nov 16 '18 at 22:37
Drejk
83
asked Nov 16 '18 at 22:37
Drejk
83
asked Nov 16 '18 at 22:37
Drejk
83
asked Nov 16 '18 at 22:37
Drejk
83
asked Nov 16 '18 at 22:37
Drejk
83
83
Would it help to first divide by gcd of coefficients?
– coffeemath
Nov 16 '18 at 23:08
1
@coffeemath Yes it would, must have misunderstood that part in the linked threads. Thanks.
– Drejk
Nov 17 '18 at 0:06
I also noticed that if a and b are equal, and the number of solutions comes out greater than 1, it will be equal to 1.
– Drejk
Nov 17 '18 at 1:37
The equation $2x+3y=6$ has two nonnegative solutions, $(3,0),(0,2).$ But the formula gives floor of $7/6$ which is $1.$ Also in the link 1 only positive solutions were considered, and here there are none.
– coffeemath
Nov 17 '18 at 10:16
@coffeemath I think somebody here mentioned that it's for non-negative, but I can see it doesn't always work out. I think you could solve this by adding 1 to the result if a solution where x or y is equal to 0 exists (which is easy to check).
– Drejk
Nov 18 '18 at 4:11
|
show 8 more comments
Would it help to first divide by gcd of coefficients?
– coffeemath
Nov 16 '18 at 23:08
1
@coffeemath Yes it would, must have misunderstood that part in the linked threads. Thanks.
– Drejk
Nov 17 '18 at 0:06
I also noticed that if a and b are equal, and the number of solutions comes out greater than 1, it will be equal to 1.
– Drejk
Nov 17 '18 at 1:37
The equation $2x+3y=6$ has two nonnegative solutions, $(3,0),(0,2).$ But the formula gives floor of $7/6$ which is $1.$ Also in the link 1 only positive solutions were considered, and here there are none.
– coffeemath
Nov 17 '18 at 10:16
@coffeemath I think somebody here mentioned that it's for non-negative, but I can see it doesn't always work out. I think you could solve this by adding 1 to the result if a solution where x or y is equal to 0 exists (which is easy to check).
– Drejk
Nov 18 '18 at 4:11
Would it help to first divide by gcd of coefficients?
– coffeemath
Nov 16 '18 at 23:08
Would it help to first divide by gcd of coefficients?
– coffeemath
Nov 16 '18 at 23:08
1
1
@coffeemath Yes it would, must have misunderstood that part in the linked threads. Thanks.
– Drejk
Nov 17 '18 at 0:06
@coffeemath Yes it would, must have misunderstood that part in the linked threads. Thanks.
– Drejk
Nov 17 '18 at 0:06
I also noticed that if a and b are equal, and the number of solutions comes out greater than 1, it will be equal to 1.
– Drejk
Nov 17 '18 at 1:37
I also noticed that if a and b are equal, and the number of solutions comes out greater than 1, it will be equal to 1.
– Drejk
Nov 17 '18 at 1:37
The equation $2x+3y=6$ has two nonnegative solutions, $(3,0),(0,2).$ But the formula gives floor of $7/6$ which is $1.$ Also in the link 1 only positive solutions were considered, and here there are none.
– coffeemath
Nov 17 '18 at 10:16
The equation $2x+3y=6$ has two nonnegative solutions, $(3,0),(0,2).$ But the formula gives floor of $7/6$ which is $1.$ Also in the link 1 only positive solutions were considered, and here there are none.
– coffeemath
Nov 17 '18 at 10:16
@coffeemath I think somebody here mentioned that it's for non-negative, but I can see it doesn't always work out. I think you could solve this by adding 1 to the result if a solution where x or y is equal to 0 exists (which is easy to check).
– Drejk
Nov 18 '18 at 4:11
@coffeemath I think somebody here mentioned that it's for non-negative, but I can see it doesn't always work out. I think you could solve this by adding 1 to the result if a solution where x or y is equal to 0 exists (which is easy to check).
– Drejk
Nov 18 '18 at 4:11
|
show 8 more comments
1 Answer
1
active
oldest
votes
You're not supposed to divide by $ab$ but by the least common multiple $operatorname{lcm}(a,b)$.
Alternatively you can divide the equation by the $gcd(a,b)=3$ first, which yields $18x+59y=27210$. The formula works now.
Edit: The formula can be off by $1$. We can see this by considering that e.g. $3x+2y=5$ has $1$ solution, $3x+2y=6$ has $2$ solutions, but $3x+2y=7$ has $1$ solution again.
We can fix it for 2 variables (linear Diophantine equation) by first finding a solution $(x_0,y_0)$ that may contain a negative number. Let's assume that $gcd(a,b)=1$, which we can always achieve by dividing the equation by the $gcd$. Then consequently the set of solutions is:
$${ (x_0+kb,y_0-ka) mid x_0+kb ge 0 land y_0-kage 0 }$$
Solving this for $k$, we find:
$$leftlceil -frac{x_0}{b} rightrceil le k le leftlfloor frac{y_0}{a}rightrfloor$$
Therefore the number of solutions is:
$$leftlfloor frac{y_0}{a}rightrfloor - leftlceil -frac{x_0}{b} rightrceil + 1 approx frac{x_0}{b} + frac{y_0}{a} = frac{ax_0+by_0}{ab} = frac c{ab} approx leftlfloorfrac{c+1}{ab}rightrfloor$$
To find the initial solution $(x_0, y_0)$ we can use the Extended Euclidean algorithm.
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
Aha, I must have misunderstood this part in the linked threads. Thanks a ton.
– Drejk
Nov 17 '18 at 0:05
1
Actually, plugging the numbers I get only 25 (1 less). At first I thought I might have had the wrong reference result, but I checked the count by going through all the options (using loops, I can post the JavaScript function which prints all results if interested), and it should in deed be 26. Rounding up would give 26, but then it wouldn't work on other equations.
– Drejk
Nov 17 '18 at 1:15
@Drejk Which other equations would the formula not work on?
– coffeemath
Nov 17 '18 at 4:10
1
Yeah @Drejk, it's one of those $pm 1$ problems, and it's not trivial. Note that $3x+2y=5$ has 1 solution, $3x+2y=6$ has 2 solutions, but $3x+2y=7$ has 1 solution again. To resolve it, I believe we need to first find an actual solution $(x_0,y_0)$, and then see how many cycles of $operatorname{lcm}(a,b)$ fit within the domain.
– I like Serena
Nov 17 '18 at 14:47
1
@IlikeSerena That's awesome, I really appreciate the effort.
– Drejk
Nov 24 '18 at 19:44
|
show 3 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3001715%2ffind-the-number-of-non-negative-integer-solutions-to-linear-systems%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
You're not supposed to divide by $ab$ but by the least common multiple $operatorname{lcm}(a,b)$.
Alternatively you can divide the equation by the $gcd(a,b)=3$ first, which yields $18x+59y=27210$. The formula works now.
Edit: The formula can be off by $1$. We can see this by considering that e.g. $3x+2y=5$ has $1$ solution, $3x+2y=6$ has $2$ solutions, but $3x+2y=7$ has $1$ solution again.
We can fix it for 2 variables (linear Diophantine equation) by first finding a solution $(x_0,y_0)$ that may contain a negative number. Let's assume that $gcd(a,b)=1$, which we can always achieve by dividing the equation by the $gcd$. Then consequently the set of solutions is:
$${ (x_0+kb,y_0-ka) mid x_0+kb ge 0 land y_0-kage 0 }$$
Solving this for $k$, we find:
$$leftlceil -frac{x_0}{b} rightrceil le k le leftlfloor frac{y_0}{a}rightrfloor$$
Therefore the number of solutions is:
$$leftlfloor frac{y_0}{a}rightrfloor - leftlceil -frac{x_0}{b} rightrceil + 1 approx frac{x_0}{b} + frac{y_0}{a} = frac{ax_0+by_0}{ab} = frac c{ab} approx leftlfloorfrac{c+1}{ab}rightrfloor$$
To find the initial solution $(x_0, y_0)$ we can use the Extended Euclidean algorithm.
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
Aha, I must have misunderstood this part in the linked threads. Thanks a ton.
– Drejk
Nov 17 '18 at 0:05
1
Actually, plugging the numbers I get only 25 (1 less). At first I thought I might have had the wrong reference result, but I checked the count by going through all the options (using loops, I can post the JavaScript function which prints all results if interested), and it should in deed be 26. Rounding up would give 26, but then it wouldn't work on other equations.
– Drejk
Nov 17 '18 at 1:15
@Drejk Which other equations would the formula not work on?
– coffeemath
Nov 17 '18 at 4:10
1
Yeah @Drejk, it's one of those $pm 1$ problems, and it's not trivial. Note that $3x+2y=5$ has 1 solution, $3x+2y=6$ has 2 solutions, but $3x+2y=7$ has 1 solution again. To resolve it, I believe we need to first find an actual solution $(x_0,y_0)$, and then see how many cycles of $operatorname{lcm}(a,b)$ fit within the domain.
– I like Serena
Nov 17 '18 at 14:47
1
@IlikeSerena That's awesome, I really appreciate the effort.
– Drejk
Nov 24 '18 at 19:44
|
show 3 more comments
You're not supposed to divide by $ab$ but by the least common multiple $operatorname{lcm}(a,b)$.
Alternatively you can divide the equation by the $gcd(a,b)=3$ first, which yields $18x+59y=27210$. The formula works now.
Edit: The formula can be off by $1$. We can see this by considering that e.g. $3x+2y=5$ has $1$ solution, $3x+2y=6$ has $2$ solutions, but $3x+2y=7$ has $1$ solution again.
We can fix it for 2 variables (linear Diophantine equation) by first finding a solution $(x_0,y_0)$ that may contain a negative number. Let's assume that $gcd(a,b)=1$, which we can always achieve by dividing the equation by the $gcd$. Then consequently the set of solutions is:
$${ (x_0+kb,y_0-ka) mid x_0+kb ge 0 land y_0-kage 0 }$$
Solving this for $k$, we find:
$$leftlceil -frac{x_0}{b} rightrceil le k le leftlfloor frac{y_0}{a}rightrfloor$$
Therefore the number of solutions is:
$$leftlfloor frac{y_0}{a}rightrfloor - leftlceil -frac{x_0}{b} rightrceil + 1 approx frac{x_0}{b} + frac{y_0}{a} = frac{ax_0+by_0}{ab} = frac c{ab} approx leftlfloorfrac{c+1}{ab}rightrfloor$$
To find the initial solution $(x_0, y_0)$ we can use the Extended Euclidean algorithm.
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
Aha, I must have misunderstood this part in the linked threads. Thanks a ton.
– Drejk
Nov 17 '18 at 0:05
1
Actually, plugging the numbers I get only 25 (1 less). At first I thought I might have had the wrong reference result, but I checked the count by going through all the options (using loops, I can post the JavaScript function which prints all results if interested), and it should in deed be 26. Rounding up would give 26, but then it wouldn't work on other equations.
– Drejk
Nov 17 '18 at 1:15
@Drejk Which other equations would the formula not work on?
– coffeemath
Nov 17 '18 at 4:10
1
Yeah @Drejk, it's one of those $pm 1$ problems, and it's not trivial. Note that $3x+2y=5$ has 1 solution, $3x+2y=6$ has 2 solutions, but $3x+2y=7$ has 1 solution again. To resolve it, I believe we need to first find an actual solution $(x_0,y_0)$, and then see how many cycles of $operatorname{lcm}(a,b)$ fit within the domain.
– I like Serena
Nov 17 '18 at 14:47
1
@IlikeSerena That's awesome, I really appreciate the effort.
– Drejk
Nov 24 '18 at 19:44
|
show 3 more comments
You're not supposed to divide by $ab$ but by the least common multiple $operatorname{lcm}(a,b)$.
Alternatively you can divide the equation by the $gcd(a,b)=3$ first, which yields $18x+59y=27210$. The formula works now.
Edit: The formula can be off by $1$. We can see this by considering that e.g. $3x+2y=5$ has $1$ solution, $3x+2y=6$ has $2$ solutions, but $3x+2y=7$ has $1$ solution again.
We can fix it for 2 variables (linear Diophantine equation) by first finding a solution $(x_0,y_0)$ that may contain a negative number. Let's assume that $gcd(a,b)=1$, which we can always achieve by dividing the equation by the $gcd$. Then consequently the set of solutions is:
$${ (x_0+kb,y_0-ka) mid x_0+kb ge 0 land y_0-kage 0 }$$
Solving this for $k$, we find:
$$leftlceil -frac{x_0}{b} rightrceil le k le leftlfloor frac{y_0}{a}rightrfloor$$
Therefore the number of solutions is:
$$leftlfloor frac{y_0}{a}rightrfloor - leftlceil -frac{x_0}{b} rightrceil + 1 approx frac{x_0}{b} + frac{y_0}{a} = frac{ax_0+by_0}{ab} = frac c{ab} approx leftlfloorfrac{c+1}{ab}rightrfloor$$
To find the initial solution $(x_0, y_0)$ we can use the Extended Euclidean algorithm.
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
You're not supposed to divide by $ab$ but by the least common multiple $operatorname{lcm}(a,b)$.
Alternatively you can divide the equation by the $gcd(a,b)=3$ first, which yields $18x+59y=27210$. The formula works now.
Edit: The formula can be off by $1$. We can see this by considering that e.g. $3x+2y=5$ has $1$ solution, $3x+2y=6$ has $2$ solutions, but $3x+2y=7$ has $1$ solution again.
We can fix it for 2 variables (linear Diophantine equation) by first finding a solution $(x_0,y_0)$ that may contain a negative number. Let's assume that $gcd(a,b)=1$, which we can always achieve by dividing the equation by the $gcd$. Then consequently the set of solutions is:
$${ (x_0+kb,y_0-ka) mid x_0+kb ge 0 land y_0-kage 0 }$$
Solving this for $k$, we find:
$$leftlceil -frac{x_0}{b} rightrceil le k le leftlfloor frac{y_0}{a}rightrfloor$$
Therefore the number of solutions is:
$$leftlfloor frac{y_0}{a}rightrfloor - leftlceil -frac{x_0}{b} rightrceil + 1 approx frac{x_0}{b} + frac{y_0}{a} = frac{ax_0+by_0}{ab} = frac c{ab} approx leftlfloorfrac{c+1}{ab}rightrfloor$$
To find the initial solution $(x_0, y_0)$ we can use the Extended Euclidean algorithm.
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
edited Nov 19 '18 at 22:02
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
answered Nov 16 '18 at 23:36
I like Serena
3,7221718
3,7221718
Aha, I must have misunderstood this part in the linked threads. Thanks a ton.
– Drejk
Nov 17 '18 at 0:05
1
Actually, plugging the numbers I get only 25 (1 less). At first I thought I might have had the wrong reference result, but I checked the count by going through all the options (using loops, I can post the JavaScript function which prints all results if interested), and it should in deed be 26. Rounding up would give 26, but then it wouldn't work on other equations.
– Drejk
Nov 17 '18 at 1:15
@Drejk Which other equations would the formula not work on?
– coffeemath
Nov 17 '18 at 4:10
1
Yeah @Drejk, it's one of those $pm 1$ problems, and it's not trivial. Note that $3x+2y=5$ has 1 solution, $3x+2y=6$ has 2 solutions, but $3x+2y=7$ has 1 solution again. To resolve it, I believe we need to first find an actual solution $(x_0,y_0)$, and then see how many cycles of $operatorname{lcm}(a,b)$ fit within the domain.
– I like Serena
Nov 17 '18 at 14:47
1
@IlikeSerena That's awesome, I really appreciate the effort.
– Drejk
Nov 24 '18 at 19:44
|
show 3 more comments
Aha, I must have misunderstood this part in the linked threads. Thanks a ton.
– Drejk
Nov 17 '18 at 0:05
1
Actually, plugging the numbers I get only 25 (1 less). At first I thought I might have had the wrong reference result, but I checked the count by going through all the options (using loops, I can post the JavaScript function which prints all results if interested), and it should in deed be 26. Rounding up would give 26, but then it wouldn't work on other equations.
– Drejk
Nov 17 '18 at 1:15
@Drejk Which other equations would the formula not work on?
– coffeemath
Nov 17 '18 at 4:10
1
Yeah @Drejk, it's one of those $pm 1$ problems, and it's not trivial. Note that $3x+2y=5$ has 1 solution, $3x+2y=6$ has 2 solutions, but $3x+2y=7$ has 1 solution again. To resolve it, I believe we need to first find an actual solution $(x_0,y_0)$, and then see how many cycles of $operatorname{lcm}(a,b)$ fit within the domain.
– I like Serena
Nov 17 '18 at 14:47
1
@IlikeSerena That's awesome, I really appreciate the effort.
– Drejk
Nov 24 '18 at 19:44
Aha, I must have misunderstood this part in the linked threads. Thanks a ton.
– Drejk
Nov 17 '18 at 0:05
Aha, I must have misunderstood this part in the linked threads. Thanks a ton.
– Drejk
Nov 17 '18 at 0:05
1
1
Actually, plugging the numbers I get only 25 (1 less). At first I thought I might have had the wrong reference result, but I checked the count by going through all the options (using loops, I can post the JavaScript function which prints all results if interested), and it should in deed be 26. Rounding up would give 26, but then it wouldn't work on other equations.
– Drejk
Nov 17 '18 at 1:15
Actually, plugging the numbers I get only 25 (1 less). At first I thought I might have had the wrong reference result, but I checked the count by going through all the options (using loops, I can post the JavaScript function which prints all results if interested), and it should in deed be 26. Rounding up would give 26, but then it wouldn't work on other equations.
– Drejk
Nov 17 '18 at 1:15
@Drejk Which other equations would the formula not work on?
– coffeemath
Nov 17 '18 at 4:10
@Drejk Which other equations would the formula not work on?
– coffeemath
Nov 17 '18 at 4:10
1
1
Yeah @Drejk, it's one of those $pm 1$ problems, and it's not trivial. Note that $3x+2y=5$ has 1 solution, $3x+2y=6$ has 2 solutions, but $3x+2y=7$ has 1 solution again. To resolve it, I believe we need to first find an actual solution $(x_0,y_0)$, and then see how many cycles of $operatorname{lcm}(a,b)$ fit within the domain.
– I like Serena
Nov 17 '18 at 14:47
Yeah @Drejk, it's one of those $pm 1$ problems, and it's not trivial. Note that $3x+2y=5$ has 1 solution, $3x+2y=6$ has 2 solutions, but $3x+2y=7$ has 1 solution again. To resolve it, I believe we need to first find an actual solution $(x_0,y_0)$, and then see how many cycles of $operatorname{lcm}(a,b)$ fit within the domain.
– I like Serena
Nov 17 '18 at 14:47
1
1
@IlikeSerena That's awesome, I really appreciate the effort.
– Drejk
Nov 24 '18 at 19:44
@IlikeSerena That's awesome, I really appreciate the effort.
– Drejk
Nov 24 '18 at 19:44
|
show 3 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3001715%2ffind-the-number-of-non-negative-integer-solutions-to-linear-systems%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Would it help to first divide by gcd of coefficients?
– coffeemath
Nov 16 '18 at 23:08
1
@coffeemath Yes it would, must have misunderstood that part in the linked threads. Thanks.
– Drejk
Nov 17 '18 at 0:06
I also noticed that if a and b are equal, and the number of solutions comes out greater than 1, it will be equal to 1.
– Drejk
Nov 17 '18 at 1:37
The equation $2x+3y=6$ has two nonnegative solutions, $(3,0),(0,2).$ But the formula gives floor of $7/6$ which is $1.$ Also in the link 1 only positive solutions were considered, and here there are none.
– coffeemath
Nov 17 '18 at 10:16
@coffeemath I think somebody here mentioned that it's for non-negative, but I can see it doesn't always work out. I think you could solve this by adding 1 to the result if a solution where x or y is equal to 0 exists (which is easy to check).
– Drejk
Nov 18 '18 at 4:11