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.

I saw a lot of similar questions asked on this forum, however they were all mostly generalizing to variables a, b, c, d etc. or proofs. However would like to see an example of solving one rather than a proof.

Find all integer solutions to the following linear diophantine question with 4 variables: 2x1 + 5x2 + 4x3 + 3x4 = 5

So I know gcd of a, b, c, d is same as a, b, (c, d), do we use that fact here?

The gcd for (2, 5, 4, 3) = 1 here but how would this help find x1, x2, x3, x4.

In the 2-variable case, I know we can use the Euclidean Algorithm to solve it, does it work in this case too? Or do we brute force this?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Since "integer" unqualified allows negative or zero solutions, one way to solve this is to use the fact that in this example you have coprime coefficients. (Any choice other than $2,4$ will do; I chose $2,3$.) So put temporarily $A=5-5x_2-4x_3$ and your equation is $$2x_1+3x_4=A.\tag{1}$$ This can be solved in the usual two variable way to obtain $$x_1=2A+3t,\\ x_4=-A-2t.$$ Filling in $A$ here from $(1)$, and noting that $x_2,x_3$ are to be arbitrary integers, then gives a complete (though not especially symmetric) parametric solution.

share|improve this answer

First consider the three cases $x_2=0,x_2=1 $ and $x_2>1.$ It is clear that there is not any integer solution for $x_2>1$. For $x_2=1$ we have only one solution $(0,1,0,0).$ In the case $x_2=0$ we got the following simple equation $2 x_1+4 x_3+3 x_4=5$ with the solution $(1,0,0,1)$. Thus there are two solutions $(0,1,0,0)$ and $(1,0,0,1)$.

share|improve this answer
    
What's the rational for doing the above? –  DJ_ Sep 28 '13 at 22:07
    
For non-negative integers, I have not found more solutions than those of Leox. If negative integers are also allowed, other solutions do exist. Example (9, 9, -7, -10). –  Axel Kemper Sep 28 '13 at 22:41

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.