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 ?

  • 1
    $\begingroup$ Generating functions might help - the count is the coefficient of $x^c$ in $\dfrac{1}{(1-x^a)(1-x^b)}$. $\endgroup$ Jul 22 '13 at 21:03
  • $\begingroup$ 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. $\endgroup$ Jul 22 '13 at 21:15
  • $\begingroup$ @AnonSubmitter85 - Yes, the number of sols is not either 0 or Infinity $\endgroup$
    – darthy734
    Jul 22 '13 at 21:17
  • 1
    $\begingroup$ @AnonSubmitter85, note that $x, y \ge 0$, so there are not infinitely many solutions. $\endgroup$ Jul 22 '13 at 21:17
  • $\begingroup$ 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? $\endgroup$ 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 $$


$$ \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.

  • 1
    $\begingroup$ I love Generatingfunctionology! $\endgroup$ Jul 22 '13 at 21:23
  • $\begingroup$ @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 ? $\endgroup$
    – darthy734
    Jul 22 '13 at 21:28
  • $\begingroup$ @darthy734, my apologies, I wrote $n$ instead of $c$. It's fixed now. $\endgroup$ Jul 22 '13 at 22:54
  • $\begingroup$ You don't really need all of Schur for this - it is sort of obvious that $c/ab$ is approximation. $\endgroup$ Jul 23 '13 at 12:04
  • $\begingroup$ Do you have a source for this? Also, for c=5, M=2, a1=1, a2=2 this gives 2.5... $\endgroup$ Apr 26 '15 at 4:41

You might be looking for Diophantine equations.

Check this link or this for an explanation!

  • $\begingroup$ He's not looking for how to solve it, he's looking for how to count non-negative solutions. $\endgroup$ Jul 22 '13 at 21:05
  • $\begingroup$ Maybe he was looking for small solution sets. Added because it provides a way to count solutions, mon ami. $\endgroup$ Jul 22 '13 at 21:06
  • $\begingroup$ @ThomasAndrews - Can you please throw some more light on the generating functions method. $\endgroup$
    – darthy734
    Jul 22 '13 at 21:06
  • $\begingroup$ @AnuragPallaprolu - Going through the link you've shared, will let you know once I'm done. $\endgroup$
    – darthy734
    Jul 22 '13 at 21:08
  • $\begingroup$ @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 ? $\endgroup$
    – darthy734
    Jul 22 '13 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.