# 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: $$\lfloor\frac{\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?

• Would it help to first divide by gcd of coefficients? – coffeemath Nov 16 '18 at 23:08
• @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

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-ka\ge 0 \}$$ Solving this for $$k$$, we find: $$\left\lceil -\frac{x_0}{b} \right\rceil \le k \le \left\lfloor \frac{y_0}{a}\right\rfloor$$ Therefore the number of solutions is: $$\left\lfloor \frac{y_0}{a}\right\rfloor - \left\lceil -\frac{x_0}{b} \right\rceil + 1 \approx \frac{x_0}{b} + \frac{y_0}{a} = \frac{ax_0+by_0}{ab} = \frac c{ab} \approx \left\lfloor\frac{c+1}{ab}\right\rfloor$$ To find the initial solution $$(x_0, y_0)$$ we can use the Extended Euclidean algorithm.

• Aha, I must have misunderstood this part in the linked threads. Thanks a ton. – Drejk Nov 17 '18 at 0:05
• 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
• 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. – Klaas van Aarsen Nov 17 '18 at 14:47
• @IlikeSerena That's awesome, I really appreciate the effort. – Drejk Nov 24 '18 at 19:44