The number of non-negative integer solutions of $ax+by=k$

Question

A linear equation in one variable $x$, $$ax+b=k$$ has only one non-negative integer solution. For example, $2x+3=85$ has a solution 41.

How to find the number of non-negative integer solutions of a linear equation in two variables $x$ and $y$, for example, $5x+3y=100$ and in general, $$ax+by=k$$

By brute-force search, I found 7 non-negative integer solutions of $5x+3y=100$. They are $(2, 30), (5, 25), (8, 20), (11, 15), (14, 10), (17, 5), \text{ and }(20, 0)$.

P.S. I came to know that a linear equation in two variables is also know as linear Diophantine equation. I also came across Kuṭṭaka, Aryabhata's algorithm for solving linear Diophantine equations in two variables.

Answer 1

Assume $\gcd(a, b)=1$. If there are any such solutions at all in non-negative integers, there will be a unique solution where $0 \leq x \lt b$. Start there. Increment $x$ by $b$ while simultaneously decrementing $y$ by $a$. When this process results in $y \lt 0$, you're done. In your example, you start with $(2, 30)$ (note that $0 \leq 2 \lt 3$) and then increase the first coordinate by $3$ while simultaneously decreasing the second coordinate by $5$.

If $\gcd(a, b) \neq 1$, then $\gcd(a, b) \mid k$ (or there would be no solutions in integers) so divide $a, b, k$ by $\gcd(a, b)$ and apply the first paragraph.

Answer 2

Given $a, b, k$, your linear equation defines a line on the plane: $y = k - \frac{a}{b} x$

The solutions will be limited to $x$ less than the $x$-intercept, and $y$ less than the $y$ intercept, i.e. $0 < x < \frac{bk}{a}$ and $0 < y < k$. So your answer will be bounded by $\mathrm{min} ( \lfloor \frac{bk}{a}\rfloor, \lfloor k \rfloor$) if both intercepts are positive, and zero otherwise. This reduces the search space for brute force. I'm not sure if there is an analytic solution.

Answer 3

One way to solve this, when $(a,b)=1,$ is to use partial fractions:

$$\frac1{(1-x^a)(1-x^b)}=\frac{\alpha}{(1-x)^2}+\frac\beta{1-x}+\frac{p(x)}{1-x^a}+\frac{q(x)}{1-x^b}$$ where $\deg p<a, \deg q<b,$ and $p(1)=q(1)=0.$

If $p(x)=\sum_i p_i x^i, q(x)=\sum_{i} q_i x^i,$ then the coefficient of $x^k$ is $$\alpha(k+1)+\beta +p_{k\bmod a}+q_{k\bmod b}$$

It’s easy to calculate the dominant term, $\alpha=\frac1{ab}.$

So if $C_k$ is the count of solutions, $C_k\sim \frac{k}{ab}.$ We also get $C_{k+ab}=C_k+1.$

For $k<ab,$ $c_{k}=0,1,$ so this means the $\beta+p_{k\bmod a}+q_{k\bmod b}$ is always of absolute value $<1.$

For $a=3,p=5,$ Wolfram Alpha gives:

$\beta=\frac15,$ $p_*=\left(\frac13,-\frac13,0\right),$ $q_*=\left(\frac25,0,-\frac25,\frac15,-\frac15\right).$

---

The general question, given relatively prime $a_1,\cdots,a_n$ of $$a_1x_1+\cdots+a_nx_n=k,$$ the partial fraction formula is similar if the $a_i$ are pairwise relatively prime. It gets more complicated with common factors.

In either event, the dominant term is still simple: $$\frac{\binom{k+n-1}{n-1}}{a_1a_2\cdots a_n}$$

Answer 4

Or, you could solve a linear program with a solver (as the tag linear-programming is in your question), or more precisely an integer program (MIP), and add a no good cut to exclude the current solution, until there are no more left.

The variables are $(x,y)\in \mathbb{N}^2$, there is no objective function (add a dummy one, e.g., $0$), and the unique constraint is $$ ax+by = k $$ The no good constraint should cut out a given solution $(\hat{x},\hat{y})$. An option is to add: $$ |x-\hat{x}|+|y-\hat{y}| \ge 1 $$

So for example, if the first iteration gives you $(x,y)=(2,30)$, you can solve $$ 5x + 3y = 100 \\ |x-2|+|y-30| \ge 1 $$ And it should give you a solution among the other ones you found by brute force, perhaps $(5,25)$. So the third iteration would be: $$ 5x + 3y = 100 \\ |x-2|+|y-30| \ge 1 \\ |x-5|+|y-25| \ge 1 $$

Once the program becomes infeasible, you have your set of all feasible solutions.