Reduced resultants and Bezout's identity

Question

Introduction: Given two univariate and coprime integer polynomials $f(x), g(x)$, we can always write \begin{equation} u(x)f(x)+v(x)g(x)=c \end{equation} for a unique pair of integer polynomials $u(x), v(x)$, and a unique positive integer $c$, such that $\deg u<\deg g$ and $\deg v<\deg f$. (This is a consequence of cancellation in the denominators in Bezout's identity, applied to $f$ and $g$ as elements of $\mathbb{Q}[x]$ and $c$ is the $lcm$ of the denominators of the unique pair of rational polynomials determined by Bezout's identity).

However, the positive integer $c$ need not be the minimal integer satisfying such a relation—there may be integer polynomials $p(x)$ and $ q(x)$ of arbitrary degrees such that $$ p(x)f(x)+q(x)g(x)=d $$ with $d<c$.

As an example, consider $f(x)=2x+1$, $g(x)=2x+17$, for which Bezout's identity gives $c=16$: $$ \frac{1}{16}(2x+17)-\frac{1}{16}(2x+1)=1 \Leftrightarrow (2x+17)-(2x+1)=16; $$ while for $p(x)=-(x^4 + 8 x^3 - 4x^2 + 2 x - 1)$, $q(x)=x^4$, we obtain $d=1$: $$ (2 x + 17) (x^4)-(2 x + 1) (x^4 + 8 x^3 - 4x^2 + 2 x - 1)=1. $$ (This example is cited in On resultants, Proc Amer Math Soc 89 (1983) 419-420, G. Myerson.)

The minimal positive integer $c$ satisfying such a relation $p(x)f(x)+q(x)g(x)=c$, for $p(x), q(x)$ integer polynomials, is by definition called the reduced resultant of $f,g$ (see The resultant and the ideal generated by two polynomials in $\mathbb{Z}[x]$). As I understand it, if $f$ and $g$ are both monic (see Reduced resultant of monic polynomials), then this minimal positive integer (that is, the reduced resultant), can be found by applying the extended Euclidean algorithm, obtaining the Bezout's identity, and then clearing denominators.

Now the question: For any pair of coprime, integer polynomials $f$ and $g$, how can we find polynomials $p(x)$ and $q(x)$—of suitable degrees—together with the minimal positive integer $c$, such that $$ p(x)f(x)+q(x)g(x)=c. $$

P.S.: Given two coprime integer polynomials $f,g$, by Bezout's identity in $\mathbb{Q}[x]$, we know that all other pairs of rational polynomials, satisfying the relation $A(x)f(x)+B(x)g(x)=1$ are of the form $$ A(x)=\frac{1}{c}u(x)+g(x)w(x), \ \ \ B(x)=\frac{1}{c}v(x)-f(x)w(x) $$ for arbitrary $w(x)\in\mathbb{Q}[x]$. Notice also, that in the preceding example, by long-division we get: $$ B(x)=q(x)=x^4 + 8 x^3 - 4 x^2 + 2 x - 1=\left(-\frac{1}{16}+\frac{x}{8}-\frac{x^2}{4}+\frac{x^3}{2}\right) (2 x+17) +\frac{1}{16} $$ and: $$ A(x)=p(x)=x^4=\left(-\frac{1}{16}+\frac{x}{8}-\frac{x^2}{4}+\frac{x^3}{2}\right) (2 x+1)+\frac{1}{16} $$ for: $w(x)=\left(-\frac{1}{16}+\frac{x}{8}-\frac{x^2}{4}+\frac{x^3}{2}\right)$.

Thus, the problem amounts to deciding, whether we can determine a suitable rational polynomial $w(x)$, such that $A(x)$, $B(x)$ have $lcm$ of their denominators less than $c$.

Answer 1

First off, it can be seen that the reduced resultant must divide $c$. Indeed, if $u_1(x)f(x)+v_1(x)g(x)=c$ and $u_2(x)f(x)+v_2(x)g(x)=d$, then from the Bezout identity for integers $c,d$, we can construct the identity $u(x)f(x)+v(x)g(x)=\gcd(c,d)$. Hence, if $d$ is the reduced resultant, then $d=\gcd(c,d)$, i.e. $d\mid c$.

Now, let's see if a prime factor $p|c$ can be cancelled from the r.h.s. of the identity $u(x)f(x)+v(x)g(x)=c$. From polynomials $u(x)$ and $v(x)$, we need to obtain polynomials $cA(x)$ and $cB(x)$ with integer coefficients such that $cA(x)\equiv cB(x)\equiv 0\pmod{p}$. (I follow the notation of OP.)

I'll consider the case $\mathrm{cont}(f)=\mathrm{cont}(g)=1$. Then Gauss' lemma implies that $cw(x)$ is a polynomial with integer coefficients. Thus, the condition $v(x)-f(x)(cw(x))=cB(x)\equiv 0\pmod{p}$ implies that $f(x)$ divides $v(x)$ modulo $p$. The last condition is necessary and sufficient for cancellation of $p$. When the divisibility modulo $p$ holds, setting $w(x) = \frac{1}{c}\left(\frac{v(x)}{f(x)}\bmod p\right)$ delivers us the required polynomials $u'(x): = \frac{cA(x)}{p}=\frac{u(x)+g(x)(\frac{v(x)}{f(x)}\bmod p)}p$ and $v'(x): = \frac{cB(x)}{p}=\frac{v(x)-f(x)(\frac{v(x)}{f(x)}\bmod p)}p$, for which $$u'(x)f(x)+v'(x)g(x) = \frac{c}{p}.$$

So, the reduced resultant can be computed by first computing some $c=u(x)f(x)+v(x)g(x)$ (e.g., with the extended Euclidean algorithm), and then by eliminating prime factors from $c$ (as described above) one by one while this is possible.

---

Example. For $f(x)=2x+1$ and $g(x)=2x+17$, we have $c=16$ with $u(x)=-1$ and $v(x)=1$. To check if we can cancel factor $p=2$, we check if $g(x)$ divides $u(x)$ modulo $2$. It does, and we set $c w(x)$ to the quotient, i.e. $cw(x)=1$, to get new polynomials $u_2(x):=\frac{u(x) + g(x)}2 = x+8$ and $v_2(x):=\frac{v(x)-f(x)}2=-x$. It is easy to check that $$u_2(x)f(x) + v_2(x)g(x) = 8,$$ i.e. the factor $2$ is cancelled in the r.h.s.

Continuing this way, we can cancel another factor of $2$ by setting $cw(x)=x$ to get $u_3(x):=\frac{u_2(x)+g(x)x}2 = x^2 + 9x + 4$ and $v_3(x):=\frac{v_2(x)-f(x)x}2 = -x^2 - x$ with $$u_3(x)f(x) + v_3(x)g(x) = 4,$$ and so on.