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 does one find the number of integral solutions of equations like,

$2x + 5y + 4z = 20$

I know how to do this counting if the coefficient of every variable on the LHS is $1$. But I don't know how to do this counting with arbitrary coefficients.

share|improve this question
1  
Do you mean positive integral solutions? (Or nonnegative?) There are infinitely many integral solutions. –  Jonas Meyer Mar 25 '11 at 15:31
    
I don't know if this helps, but what you have there is a linear Diophantine equation in which Bézout's identity applies (en.wikipedia.org/wiki/B%C3%A9zout%27s_identity). It doesn't give any guidance with respect to counting though. –  Gilead Mar 25 '11 at 16:24
add comment

3 Answers 3

The linear equation $2x + 5y + 4z = 20$ has a two-parameter family of infinite solutions in integers. Note that $y$ has to be even. Further any even $y$ will give a one parameter family of infinite solutions for the equation $2x + 4z = 20 - 5y$.

Let $y = 2y_1$. Then we need to solve $2x + 4z = 20 - 10y_1 \implies x + 2z = 10 -5y_1$.

Hence, the set of all integer solutions is the two parameter family $$(10-5y_1-2z_1,2y_1,z_1)$$ where $y_1,z_1 \in \mathbb{Z}$

If you are interested in non-negative integral solutions for $(x,y,z)$, then we need $y_1 \geq 0$,$z_1 \geq 0$ and $5y_1 + 2z_1 \leq 10$.

This implies $y_1 \in \{0,1,2\}$.

If $y_1 = 0$, then $z_1 = \{0,1,2,3,4,5\}$.

If $y_1 = 1$, then $z_1 = \{0,1,2\}$.

If $y_1 = 2$, then $z_1 = \{0\}$.

Hence, the set of all non-negative solutions are $$\{ (10,0,0),(8,0,1),(6,0,2),(4,0,3),(2,0,4),(0,0,5),(5,2,0),(3,2,1),(1,2,2),(0,4,0) \}$$

The set of all positive solutions are $$\{(3,2,1),(1,2,2)\}$$

share|improve this answer
add comment

here is a paper on the problem i just happened to see somewhere else

share|improve this answer
    
What is the connection? I can't see how that helps solves my question! –  Anirbit Mar 31 '11 at 8:32
    
While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. –  Arkamis Aug 31 '12 at 21:11
add comment

Let $x' = 2x$, $y' = 5y$ and $z' = 4z$. Then $2 \leq x' \leq 18$, $5 \leq y' \leq 15$ and $4 \leq z' \leq 16$ for $x',y',z' \in \mathbb{Z}^{+}$. So you can apply the same techniques for counting the number of integral solutions if all the coefficients on the LHS are $1$.

So the number of solutions would be the coefficient of $x^{20}$ in $$\left[(x^2)^{a_1}+(x^2)^{a_1+1}+ \cdots+ (x^a)^{a_2} \right] \cdot \left[(x^5)^{b_1}+(x^5)^{b_1+1}+ \cdots+ (x^5)^{b_2}\right] \cdot \left[(x^4)^{c_1}+(x^4)^{c_1+1}+ \cdots+ (x^4)^{c_2} \right]$$

where $a_1 \leq x \leq a_2$, $b_1 \leq y \leq b_2$ and $c_1 \leq z \leq c_2$.

share|improve this answer
1  
So you're assuming that each is positive. But then your bounds are quite weak relative to what is given. E.g. $y'>4$ and $z'>3$ implies $x'<12$. How do you know you can apply the same techniques? I don't know what techniques the OP uses when the coefficients are 1, but note that modified unknowns aren't allowed to take on all integer values, only multiples of 2,5,4, respectively, so it isn't exactly reduced to the previous problem. –  Jonas Meyer Mar 25 '11 at 15:36
1  
I didn't understand your answer. What is $a_1$, $a_2$, $b_1$, $b_2$, $c_1$ and $c_2$ ? Can you give some background, references and some more explanations? –  Anirbit Mar 31 '11 at 8:25
add comment

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.