Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

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

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
1  
I love Generatingfunctionology! –  Torsten Hĕrculĕ Cärlemän 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 ? –  darthy734 Jul 22 '13 at 21:28
    
@darthy734, my apologies, I wrote $n$ instead of $c$. It's fixed now. –  George V. Williams 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. –  Thomas Andrews Jul 23 '13 at 12:04

You might be looking for Diophantine equations.

Check this link or this for an explanation!

share|improve this answer
    
He's not looking for how to solve it, he's looking for how to count non-negative solutions. –  Thomas Andrews 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. –  Torsten Hĕrculĕ Cärlemän Jul 22 '13 at 21:06
    
@ThomasAndrews - Can you please throw some more light on the generating functions method. –  darthy734 Jul 22 '13 at 21:06
    
@AnuragPallaprolu - Going through the link you've shared, will let you know once I'm done. –  darthy734 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 ? –  darthy734 Jul 22 '13 at 21:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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