A new algorithm and refined bounds for extended gcd computation (Q4375607)

Let \(a_1,\dots, a_n\) be given integers with \(\text{gcd }g\). It is required to find integers \(x_1,\dots, x_n\) such that \(\sum_{i=1}^n a_ix_i= g\). The authors propose a method that consists of the construction of a matrix \(P\), the first row of which is \(x_1,\dots, x_n\). No run times, that would enable comparisons to be made with other methods, are given. Optimal bounds are obtained for the \(x_1\). The method given on p. 147 for the construction of \(P\) seems to require the answer to be known beforehand: a worked example would have clarified what the authors intended. For the entire collection see [Zbl 0852.00023].