Set of all integer solutions to a linear diophantine equation

I am trying to figure out the set of all integer solutions in terms of an appropriate number of free variables for the following:

$2x_1 + 12x_2 + 3x_3 = 7$.

I have found that the $gcd(2,12,3) = 1$ and $1 | 7$ so I know there are infinitely many solutions. However, I do not understand how to find the set of all integer solutions from here. I understand how to solve these problems for the case where there are only two variables however I do not understand how to apply the extended Euclidean algorithm to the greater-than-two variable case.

Thank you in advance.

• You can solve it recursively. For example, see here – A.P. May 25 '15 at 19:54

Recall the following

Fact 1. The equation $$a x + b y = c$$ has no solution with $x,y \in \Bbb{Z}$ if $(a,b) \nmid c$, while it admits infinitely many if $d = (a,b) \mid c$. Further, in this case the general solution (i.e. every solution) is of the form $$x = \frac{b}{d} k + x_0 \quad y = -\frac{a}{d} k + y_0$$ for any integer $k$, where $(x_0,y_0)$ is a particular solution (e.g. any one given or known solution).

Note that you can rewrite your equation as $$2 x_1 + 12 x_2 + 3 x_3 = 2 x_1 + 3 ( 4x_2 + x_3) = 7 \label{eq:orig} \tag{1}$$ In particular, every solution $(x_1,x_2,x_3)$ of \eqref{eq:orig} gives you a solution $(x_1, y = 4x_2 + x_3)$ of $$2 x_1 + 3 y = 7 \label{eq:partial_1} \tag{2}$$ thus we will first solve this other equation and then for each of these solutions we will look for the corresponding solution of \eqref{eq:orig}, if there are any.

Observe that $(2,3) = 1$, thus \eqref{eq:partial_1} has infinitely many solutions. Furtehrmore, $x_1 = 2, y = 1$ is a particular solution of \eqref{eq:partial_1}, hence from Fact 1 you know that every solution of \eqref{eq:partial_1} is of the form $$x_1 = 3s + 2 \quad y = -2s + 1 \qquad \forall s \in \Bbb{Z}$$ Now, for any fixed $s$ we go on and solve the equation $$4 x_2 + x_3 = -2s + 1 \label{eq:partial_2} \tag{3}$$ Again, observe that $(4,1) = 1$ and that $x_2 = -s$, $x_3 = 2s + 1$ is a particular solution of \eqref{eq:partial_2}. Hence it follows from Fact 1 that the general solution is of the form $$x_2 = t - s \quad x_3 = -4t + 2s + 1 \qquad \forall t \in \Bbb{Z}$$ Putting it together, we conclude that the general solution of \eqref{eq:orig} is of the form $$x_1 = 3s + 2 \quad x_2 = t - s \quad x_3 = -4t + 2s + 1 \qquad \forall s,t \in \Bbb{Z}$$

• I found your answer very confusing. How did you think to use the equality given by (2)? Even so, given (2) it appears that we would have $y=1=4x_2 + x_3$ and I have no idea how you get $x_1 = 3s + 2$ and $y = -2s +1$ $\forall s \in \mathbb{Z}$. – letsmakemuffinstogether May 26 '15 at 1:59
• For your first question: notice that every solution to \eqref{eq:orig} immediately gives a solution to \eqref{eq:partial_1}, so I solve that one first. Then for every fixed solution of \eqref{eq:partial_1} we go on to find all the solutions of \eqref{eq:orig} that correspond to it. This is a rather standard technique, which is why I thought my exposition was clear. – A.P. May 26 '15 at 8:17
• For your first question... I never said that $y = 1$. I treat $y$ as an integer variable and solve \eqref{eq:partial_1}. From your question it appeared clear that you know what are all the solutions of a linear Diophantine equation $a x + b y = c$ where $(a,b) = 1$, i.e. $x = bk + x_0, y = -ak + y_0$ for any integer $k$, where $(x_0,y_0)$ is any known solution. That's where the '$s$' comes from. – A.P. May 26 '15 at 8:23
• @A.P. Is there a name for this method? Also, what would be the time complexity of using this method? – GoodDeeds Mar 29 '18 at 19:28
• @GoodDeeds I don't think that this has a specific name. As far as I can tell, the only step that's not $O(1)$ is finding a particular solution of two equations of the form $a x + b y = \gcd(a,b)$, which for example can be done with the Euclidean algorithm. The latter's computational complexity is well known. By the way, if you have an equation like $a_1 x_1 + \dotsb + a_{n+1} x_{n+1} = c$ such that $\gcd(a_1,\dotsc,a_{n+1}) \mid c$, then you can always reduce to solving $n$ equations of type $ax + by = \gcd(a,b)$. – A.P. Mar 31 '18 at 21:30

I don't like subscripts, so I'll make it $2a+12b+3c=7$. Since $2$ and $3$ are relatively prime, I'll rewrite as $2a+3c=7-12b$. Now consider $2a+3c=1$. One solution is $a=2$, $c=-1$. So, a solution to $2a+3c=7-12b$ is $a=14-24b$, $c=12b-7$. Then the general solution is $$a=14-24b+3d,\ \ \ c=12b-7-2d$$ with $b$ and $d$ arbitrary.