1
$\begingroup$

If $d$ is the gcd of positive integers $a < b$, Bézout's theorem states that there are integers $t$ and $u$ such that $$d = ta + ub \;.$$

One can use the Euclidean algorithm for computing the gcd of $a$ and $b$ to compute suitable values for the "Bézout coefficients"1 $t$ and $s$.

More specifically, set $r_{-1} = b$ and $r_0 = a$, and suppose that, for some non-negative integer $n$, the Euclidean algorithm produces the following sequence of $n + 1$ equations:

$$ \begin{array}{rcl} r_{-1} & = & r_0 q_0 + r_1 \\ \vdots & & \vdots \\ r_{i-1} & = & r_i q_i + r_{i+1} \\ \vdots & & \vdots \\ r_{n-2} & = & r_{n-1} q_{n-1} + r_n \\ r_{n-1} & = & r_n q_n \end{array} $$

...where

  • the $q_i$ and $r_i$ are all positive integers;
  • $r_{i-1} > r_i, \forall i \in \{0, \cdots, n\}$;
  • $r_n = d$.

(The case $n = 0$ corresponds to the edge case where $a$ divides $b$, so $d = a$.)

One can eliminate $r_1, \cdots, r_{n-1}$ from this system of equations (actually, only the first $n$ equations are needed for this) to end up with an expression for $r_n = d$ as a linear combination of $r_0 = a$ and $r_{-1} = b$, with coefficients given as (possibly empty) sums of (possibly empty) products of the integers $q_i$.

Below are the coefficients $t$ and $u$ (of $r_0 = a$ and $r_{-1} = b$, respectively) in such linear combinations, for the first few values of $n$:

$$ \begin{array}{r|l|l} n & t & u \\ \hline 0 & 1 & 0 \\ \hline 1 & -q_1 & 1 \\ \hline 2 & 1+q_1 q_2 & -q_2 \\ \hline 3 & -q_1-q_3-q_1 q_2 q_3 & 1+q_2 q_3 \\ \hline 4 & 1 + q_1 q_2 +q_1 q_4 +q_3 q_4 & -q_2-q_4 -q_2 q_3 q_4 \\ & + q_1 q_2 q_3 q_4 & \\ \hline 5 & -q_1 -q_3 -q_5 & 1 \\ & -q_1 q_2 q_3 -q_1 q_2 q_5 -q_1 q_4 q_5 & +q_2 q_3 +q_2 q_5 +q_4 q_5 \\ & -q_3 q_4 q_5 -q_1 q_2 q_3 q_4 q_5 & +q_2 q_3 q_4 q_5 \end{array} $$


I have not been able to find a more direct way to compute these coefficients than to step-by-step work out the recurrence $$ r_{i+1} = r_{i-1} - r_i q_i$$ for $i$ from $0$ to $n-1$. Is there such?

I.e. is there a formula for the "Bézout coefficients" $t$ and $u$ in terms of the $n$ quotients $q_0, \cdots, q_{n-1}$ resulting from the Euclidean algorithm?


1 I came up with the term "Bézout coefficients". I have no reason to think it is at all standard.

$\endgroup$
6
  • $\begingroup$ The extended Euclidean algorithm imlements a recursive computation of the coefficients of a Bézout's relation for each of the successive remainders. Why do you want to have a closed formula? $\endgroup$
    – Bernard
    Dec 30, 2017 at 15:16
  • $\begingroup$ @Bernard: I just wondered if such a formula existed... It would be nice if there was. Note that the existence of the formula would not eliminate the need for the algorithm, since it is still needed to compute the $q_i$. I'm just trying to avoid the extra step of back-solving for the coefficients. But maybe the answer to my question is the extended Euclidean algorithm you mentioned. $\endgroup$
    – kjo
    Dec 30, 2017 at 15:22
  • 1
    $\begingroup$ I don't know if it exists, and I'm sure the extended Euclidean algorithm would be faster than applying such a formula? Note there's no backsolving in this algorithm. Furthermore, an extra step yields the l.c.m. You can see an example of the algorithm in my answer to this question. $\endgroup$
    – Bernard
    Dec 30, 2017 at 15:33
  • 3
    $\begingroup$ In the continued fraction for $\frac{b}{a},$ the penultimate convergent gives your bezout coefficients. $\endgroup$
    – Will Jagy
    Dec 30, 2017 at 15:33
  • 1
    $\begingroup$ Once you have the $q_i$'s, you can use the matrix recursion form to compute the last $s,t$ coefficients $\endgroup$
    – G Cab
    Dec 30, 2017 at 15:39

1 Answer 1

3
$\begingroup$

$$ \gcd( 81201, 56660 ) = ??? $$

$$ \frac{ 81201 }{ 56660 } = 1 + \frac{ 24541 }{ 56660 } $$ $$ \frac{ 56660 }{ 24541 } = 2 + \frac{ 7578 }{ 24541 } $$ $$ \frac{ 24541 }{ 7578 } = 3 + \frac{ 1807 }{ 7578 } $$ $$ \frac{ 7578 }{ 1807 } = 4 + \frac{ 350 }{ 1807 } $$ $$ \frac{ 1807 }{ 350 } = 5 + \frac{ 57 }{ 350 } $$ $$ \frac{ 350 }{ 57 } = 6 + \frac{ 8 }{ 57 } $$ $$ \frac{ 57 }{ 8 } = 7 + \frac{ 1 }{ 8 } $$ $$ \frac{ 8 }{ 1 } = 8 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccc} & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 & & 8 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 10 }{ 7 } & & \frac{ 43 }{ 30 } & & \frac{ 225 }{ 157 } & & \frac{ 1393 }{ 972 } & & \frac{ 9976 }{ 6961 } & & \frac{ 81201 }{ 56660 } \end{array} $$ $$ $$ $$ 81201 \cdot 6961 - 56660 \cdot 9976 = 1 $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

$$ \gcd( 144, 89 ) = ??? $$

$$ \frac{ 144 }{ 89 } = 1 + \frac{ 55 }{ 89 } $$ $$ \frac{ 89 }{ 55 } = 1 + \frac{ 34 }{ 55 } $$ $$ \frac{ 55 }{ 34 } = 1 + \frac{ 21 }{ 34 } $$ $$ \frac{ 34 }{ 21 } = 1 + \frac{ 13 }{ 21 } $$ $$ \frac{ 21 }{ 13 } = 1 + \frac{ 8 }{ 13 } $$ $$ \frac{ 13 }{ 8 } = 1 + \frac{ 5 }{ 8 } $$ $$ \frac{ 8 }{ 5 } = 1 + \frac{ 3 }{ 5 } $$ $$ \frac{ 5 }{ 3 } = 1 + \frac{ 2 }{ 3 } $$ $$ \frac{ 3 }{ 2 } = 1 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccc} & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 1 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 5 }{ 3 } & & \frac{ 8 }{ 5 } & & \frac{ 13 }{ 8 } & & \frac{ 21 }{ 13 } & & \frac{ 34 }{ 21 } & & \frac{ 55 }{ 34 } & & \frac{ 144 }{ 89 } \end{array} $$ $$ $$ $$ 144 \cdot 34 - 89 \cdot 55 = 1 $$ .............................................

$\endgroup$
1
  • $\begingroup$ Fibonacci pairs FTW! $\endgroup$
    – kjo
    Dec 30, 2017 at 16:41

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.