General form of Bezout numbers

106 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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.