3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – letsmakemuffinstogether May 26 '15 at 1:59
  • $\begingroup$ 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. $\endgroup$ – A.P. May 26 '15 at 8:17
  • $\begingroup$ 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. $\endgroup$ – A.P. May 26 '15 at 8:23
  • $\begingroup$ @A.P. Is there a name for this method? Also, what would be the time complexity of using this method? $\endgroup$ – GoodDeeds Mar 29 '18 at 19:28
  • $\begingroup$ @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)$. $\endgroup$ – A.P. Mar 31 '18 at 21:30
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.