Solve for $g_i$ in $\sum_{i=1}^k f_ig_i = 1$

Question

I was studying Linear Algebra from Hoffman Kunze and in the proof of the Primary Decomposition Theorem, I found

... the polynomials $f_1,f_2,\dots ,f_k$ are relatively prime. Thus, there are polynomials $g_1,g_2,\dots ,g_k$ such that $$\sum_{i=1}^k f_ig_i = 1$$

I can understand that this is a consequence of using Euclid's Division on polynomials. But, I wanted to know whether it is possible to explicitly calculate the $g_i$'s in terms of the $f_i$'s? Is there any algorithm that we can follow to find these $g_i$'s? I tried searching for such an algorithm, but it's not easy to get hold of an algorithm whose name you don't know.

I would like to know if any such algorithm exists.

Also, I'm not sure about the tags. Feel free to edit them.

Answer 1

This is an extension of Euclid's division lemma.

For $n=2$ we can use the idea given in Bezout's identity, we can find polynomials $g_1,g_2$ such that $$ \gcd(f_1,f_2) = g_1f_1 + g_2f_2 $$

In the case $n=3$, Note that $$\gcd(f_1,f_2,f_3) = \gcd(f_1,h_1) $$ where $h_1 = \gcd(f_2,f_3)$.

Using the idea given in Bezout's identity, we can find polynomials $a,b$ such that $$h_1 = \gcd(f_2,f_3) = af_2 + bf_3 $$, now again using the same procedure we can find polynomials $c,d$ such that $$ \gcd(f_1,h_1) = cf_1 + dh_1 = g_1f_1 + g_2f_2 +g_3f_3$$ by choosing suitable $g_i$ in terms of $a,b,c,d$.

In general, note that we have $$ \gcd(f_1, f_2, \ldots , f_n) = \gcd(f_1, \gcd(f_2, \ldots , f_n))$$ so we need to find recursively the coeffients $g_i$.