Set of all integer solutions to a linear diophantine equation

Question

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.

Answer 1

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} $$

Answer 2

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.