0

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?

DJ_
  • 1,400

2 Answers2

1

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.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
0

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

Leox
  • 8,120
  • 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