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?
 A: 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.
