# Number of non-negative integer solutions for linear equations with constants

How do we find the number of non-negative integer solutions for linear equation of the form:

$$a \cdot x + b \cdot y = c$$

Where $a, b, c$ are constants and $x,y$ are the variables ?

• Generating functions might help - the count is the coefficient of $x^c$ in $\dfrac{1}{(1-x^a)(1-x^b)}$. Jul 22 '13 at 21:03
• Is there a known case where the number of solutions is not either $0$ or $\infty$? If $a,b,c \in \mathbb{Q}$, then any time $b | ka(1-c)$, $k\in\mathbb{N}$, then both $x$ and $y$ are integer solutions and I think there are infinitely many values of $k$ that solve the above. If any of the coefficients are irrational, then there are no integer solutions. Jul 22 '13 at 21:15
• @AnonSubmitter85 - Yes, the number of sols is not either 0 or Infinity Jul 22 '13 at 21:17
• @AnonSubmitter85, note that $x, y \ge 0$, so there are not infinitely many solutions. Jul 22 '13 at 21:17
• Have you found any answers for specific situations? For instance, if we assume that $a,b,c \in \mathbb{Q}$ and that $y = k \cdot \operatorname{lcm}(b_n,b_d)$, where $b = b_n/b_d$ and $k \in \mathbb{N}$, can you find ranges of $a$ and $c$ such that there are infinitely many or zero solutions? Jul 22 '13 at 22:09

Not a complete answer, but a relatively simple one and approximate one. By Schur's theorem of combinatorics?, the number of solutions is asymptotically ($c \to \infty$):

$$\frac{c}{ab}$$

Schur's theorem of combinatorics states that the number of solutions of (with $a_i$ relatively prime):

$$\sum_{i=1}^M a_i x_i = c$$

is:

$$\frac{c^{M-1}}{(M-1)!\prod a_i}$$

? This name is used by Wilf's Generatingfunctionology, but I cannot seem to find it elsewhere. It appears that Schur has many theorems.

• I love Generatingfunctionology! Jul 22 '13 at 21:23
• @George V. Williams - Thanks, probably this might be the easiest way to get the desired result. Could you pls explain what is 'n' in the above equation ? Jul 22 '13 at 21:28
• @darthy734, my apologies, I wrote $n$ instead of $c$. It's fixed now. Jul 22 '13 at 22:54
• You don't really need all of Schur for this - it is sort of obvious that $c/ab$ is approximation. Jul 23 '13 at 12:04
• Do you have a source for this? Also, for c=5, M=2, a1=1, a2=2 this gives 2.5... Apr 26 '15 at 4:41

You might be looking for Diophantine equations.

Check this link or this for an explanation!

• He's not looking for how to solve it, he's looking for how to count non-negative solutions. Jul 22 '13 at 21:05
• Maybe he was looking for small solution sets. Added because it provides a way to count solutions, mon ami. Jul 22 '13 at 21:06
• @ThomasAndrews - Can you please throw some more light on the generating functions method. Jul 22 '13 at 21:06
• @AnuragPallaprolu - Going through the link you've shared, will let you know once I'm done. Jul 22 '13 at 21:08
• @AnuragPallaprolu - Thanks for the link, but as Thomas mentioned, is there a way to get the number of non-neg solutions rather than solve for the whole set ? Jul 22 '13 at 21:13