Bézout's lemma can be generalized to $n$ co-prime integers $a_1, \dots a_n$ : there exists integers $x_1, \dots, x_n$ such that $$a_1 x_1 + \dots + a_n x_n = 1$$

For the case $n = 2$, one can show that $(x_1,x_2) \in \{ (u_1 + k a_2, u_2 - k a_1), k \in \mathbb{Z} \}$.

Is there a similar general form for $(x_1, \dots, x_n)$ when $n > 2$ ?


I suspect that such a general form doesn't exist for multiple variables.

However there's a simple algorithm for finding the general solution for any particular set of numbers $a_1,\dots,a_n$. What you want to do is to solve the homogeneous equation $a_1 x_1 + \dots + a_n x_n = 0$, after which the general solution is just the solution to the homogeneous equation plus a particular solution to $a_1 x_1 + \dots + a_n x_n = 1$.

Now if $a_i = 1$ for some $1 \le i \le n$, we can just write $x_i$ as a linear combination of the others, giving a solution. Otherwise choose a variable $x_i$ with the smallest coefficient $a_i$, and write it as $x_i = y_i - k x_j$, where $k$ is chosen so that $a_j - a_i k$ is the remainder of the division $a_j/a_i$ ($j \neq i$ can be chosen arbitrarily). Repeat this and keep track what substitutions were made. Eventually you'll reach $1$, and are done.

Example: $5x + 8y + 13z = 0$

Do the substitution $x = x_1 - y$ to get $5x_1 + 3y + 13z = 0$.

Do the substitution $y = y_1 - x_1$ to get $2x_1 + 3y_1 + 13z = 0$.

Do the substitution $x_1 = x_2 - y_1$ to get $2x_2 + y_1 + 13z = 0$.

We can now write $y_1 = - 2x_2 - 13z$.

Backsubstitution gives $x_1 = 3x_2 + 13z$, $y = -5x_2 - 26 z$ and finally $x = 8x_2 + 39z$. Thus $(x,y,z) = (8x_2 + 39z, -5x_2 - 26z, z)$ is a general solution for the homogeneous equation.

  • $\begingroup$ Just a comment: Of course the method described also works directly with the non-homogeneous equation. $\endgroup$ – J. J. Apr 10 '14 at 14:52

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.