Lucky and unlucky modular reductions

Let $f,g \in R[x]$ be nonzero polynomials for an Euclidean domain $R$ . Let $p \in R$ be a prime. We denote by $a \longmapsto \overline{a}$ the reduction modulo $p$ . We know from the previous section that

$${\gcd}(f,g) \in R \ \ \ \ \iff \ \ \ \ {\rm res}(f,g) \neq 0$$ (36)

The formula of the resultant of $f$ and $g$ shows that ${\rm res}(f,g)$ is a multivariate polynomial expression in the coefficients of $f$ and $g$ . Hence we might be tempted to say

• $\overline{{\rm res}(f,g)} = {\rm res}(\overline{f}, \overline{g})$ .
• $\overline{f}$ and $\overline{g}$ are coprime in $R/p[x]$ iff $p$ does not divide ${\rm res}(f,g)$ .

Example 1   Consider $R = {\mbox{${\mathbb{Z}}$}}$ , $p = 2$ , $f = x + 2$ and $g = x$ . Then we have

$${\rm res}(f,g) = - 2 \equiv 0 \mod{2} \ \ \ \ {\rm and} \ \ \ {\rm res}(\overline{f}, \overline{g}) = 0$$ (37)

as expected. But when $f = 4 x^3 - x$ and $g = 2 x + 1$ we have

$${\rm res}(f,g) = 0 \ \ \ \ {\rm and} \ \ \ {\rm res}(\overline{f}, \overline{g}) = {\rm res}(x,1) = 1$$ (38)

The reason for this unexpected behavior in the last example is that the Sylvester matrix of $\overline{f} = x$ and $\overline{g} = 1$ is

$$\left( \begin{array}{c} 1 \end{array} \right)$$ (39)

and thus is not the reduction modulo $2$ of the Sylvester matrix of $f$ and $g$ which is

$$\left( \begin{array}{cccc} 4 & 2 & 0 & 0 \\ 0 & 1 & 2 & 0 \\ -1 & 0 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{array} \right)$$ (40)

In other words the ${\rm res}$ operation for $\overline{f}$ and $\overline{g}$ is not the reduction modulo $2$ of the ${\rm res}$ operation for $f$ and $g$ . This is because the ${\rm res}$ operation depends on the degrees of its input polynomials. Fortunately this nuisance disappears when $p$ does not divide at least one of the leading coefficients.

Lemma 2   Let $R$ be a commutative ring with identity element. Let $f,g \in R[x]$ be nonzero polynomials. Let $r$ be their resultant. Let $I$ be an ideal if $R$ and let denote by $a \longmapsto \overline{a}$ the reduction modulo $I$ . Assume that

$$\overline{{\rm lc}(f)} \ \neq 0$$ (41)

Then we have

$$\overline{r} = 0 \ \ \ \ \iff \ \ \ \ {\rm res}(\overline{f}, \overline{g}) = 0$$ (42)

Moreover, if $R/I$ is a UFD, then we have

$$\overline{r} = 0 \ \ \ \ \iff \ \ \ \ {\deg}({\gcd}(\overline{f}, \overline{g})) > 0$$ (43)

Proof. Let us write:

$$f \ = \ f_n x^n + \cdots + f_0 \ \ \ \ {\rm and} \ \ \ \ g \ = \ g_m x^m + \cdots + g_0$$ (44)

with $f_n \neq 0$ and $g_m \neq 0$ . If $n = 0$ then ${\rm Sylv}(f,g)$ and ${\rm Sylv}(\overline{f},\overline{g})$ are both diagonal with $f$ on the diagonal. Then in that case

$$\overline{r} \ = \ \overline{f^m} \ = \ \overline{f}^m \ = \ {{\rm res}(\overline{f}, \overline{g})}^m$$ (45)

If $n > 0$ we distinguish two cases. If $\overline{g} = 0$ then ${\rm res}(\overline{f},\overline{g}) = 0$ (by Definition 4). Moreover each $g$ -column of ${\rm Sylv}(f,g)$ is zero modulo $I$ such that $\overline{r} = 0$ too. From now on assume $\overline{g} \neq 0$ and let $i$ be the smallest index such that $\overline{g_{m-i}} \neq 0$ holds.

$${\rm Sylv}(f,g) \ = \ \left( \begin{array}{ccccccccc} f_0 & & & &... ...ddots & \vdots & & & & \vdots \\ & & & & f_n & & & & g_m \\ \end{array} \right)$$ (46)

By exchanging the $f$ -zone with the $g$ -zone we have also

$${\rm res}(f,g) \ = \ (-1)^{n m} \left\vert \begin{array}{cccccccc... ...s & & & & \ddots & \vdots \\ & & & g_m & & & & & f_n \\ \end{array} \right\vert$$ (47)

Let $M$ be the submatrix obtained from ${\rm Sylv}(g,f)$ by deleting the last $i$ rows and the last $i$ columns. Observe that we have

$$\overline{{\rm res}(f,g)} \ = \ (-1)^{n m} \ \overline{{\det}(M)} \ \overline{{f_n}^i}$$ (48)

Since

$$\overline{{\det}(M)} \ = \ {\det}(\overline{M}) \ = \ {\rm res}(\overline{f},\overline{g})$$ (49)

we obtain

$$\overline{{\rm res}(f,g)} \ = \ (-1)^{n m} \ {\rm res}(\overline{f},\overline{g}) \ {\overline{{\rm lc}(f)}}^i$$ (50)

This shows that we have

$$\overline{r} = 0 \ \ \ \ \iff \ \ \ \ {\rm res}(\overline{f}, \overline{g}) = 0$$ (51)

and the first claim of the lemma is proved. The second claim follows from Proposition 6. $\qedsymbol$

Theorem 3   Let $f,g \in R[x]$ be nonzero polynomials for an Euclidean Domain $R$ . Let $p \in R$ be a prime. Let

$$h = {\gcd}(f,g), \ \ \ \ e = {\deg}(h). \ \ \ \ {\rm and} \ \ \ {\alpha} = {\rm lc}(h)$$ (52)

Assume that $p$ does not divide

$$b = {\gcd}({\rm lc}(f), {\rm lc}(g))$$ (53)

Finally let

$$e^{\ast} \ = \ {\deg}({\gcd}(\overline{f}, \overline{g}))$$ (54)

Then we have

1. ${\alpha}$ divides $b$
2. $e^{\ast} \geq e$
3. $e^{\ast} = e \ \ \iff \ \ \overline{{\alpha}} \ {\gcd}(\overline{f}, \overline{g}) = \overline{h} \ \ \iff \ \ p \not\mid {\rm res}(f/h, g/h)$

Proof. Since in $R[x]$

$$h \ \mid \ f \ \ \ \ {\rm and} \ \ \ \ h \ \mid \ g$$ (55)

we have in $R$

$${\rm lc}(h) \ \mid \ {\rm lc}(f) \ \ \ \ {\rm and} \ \ \ \ {\rm lc}(h) \ \mid \ {\rm lc}(g).$$ (56)

Therefore

$${\alpha} \ = \ {\rm lc}(h) \ \mid \ {\gcd}({\rm lc}(f), {\rm lc}(g)) \ = \ b$$ (57)

and the first claim is proved. Consider now the cofactors of $f$ and $g$ in $R[x]$

$$u \ = \ f/h \ \ \ \ {\rm and} \ \ \ \ v \ = \ g/h.$$ (58)

Then we have

$$\overline{u} \, \overline{h} \ = \ \overline{f} \ \ \ \ {\rm and} \ \ \ \ \overline{v} \, \overline{h} \ = \ \overline{g}$$ (59)

which shows that

$$\overline{h} \ \mid \ {\gcd}(\overline{f}, \overline{g})$$ (60)

and implies that

$${\deg}(\overline{h}) \ \leq \ {\deg}({\gcd}(\overline{f}, \overline{g}))$$ (61)

Since $p$ does not divide $b$ , it cannot not divide ${\alpha}$ neither. Hence the leading coefficient of $\overline{h}$ is $\overline{{\alpha}}$ and we have

$${\deg}(\overline{h}) \ = \ {\deg}(h)$$ (62)

Therefore

$$e \ = \ {\deg}(h) \ \leq \ {\deg}({\gcd}(\overline{f}, \overline{g})) \ = \ e^{\ast}$$ (63)

and the second claim is proved.

Now consider the case where $e \ = \ e^{\ast}$ . Since $\overline{h}$ divides ${\gcd}(\overline{f}, \overline{g})$ and since ${\gcd}(\overline{f}, \overline{g})$ is monic (as a gcd over the field $R/p$ ) there exists a unit ${\beta}$ such that

$$\overline{h} \ = \ {\beta} \ {\gcd}(\overline{f}, \overline{g})$$ (64)

Since the leading coefficient of $\overline{h}$ is $\overline{{\alpha}}$ we have in fact

$${\beta} \ = \ \overline{{\alpha}}$$ (65)

Therefore we have the following equivalence

$$e \ = \ e^{\ast} \ \ \ \ \iff \ \ \ \ \overline{h} \ = \ \overline{{\alpha}} \ {\gcd}(\overline{f}, \overline{g})$$ (66)

It remains to prove that

$$\ \ \overline{{\alpha}} \ {\gcd}(\overline{f}, \overline{g}) = \overline{h} \ \ \iff \ \ p \not\mid {\rm res}(f/h, g/h)$$ (67)

Observe that $p$ cannot divide both ${\rm lc}(u)$ and ${\rm lc}(v)$ . If this was the case then from Relation (59) (and since $p$ does not divide ${\alpha} = {\rm lc}(h)$ ) $p$ would divide ${\rm lc}(f)$ and ${\rm lc}(g)$ , and thus $b$ . A contradiction. Therefore we can assume that $p$ does not divide ${\rm lc}(u)$ . By applying Lemma 2 we obtain

$$\overline{{\rm res}(u,v)} = 0 \ \ \ \ \iff \ \ \ \ {\rm res}(\overline{u}, \overline{v}) = 0$$ (68)

By applying Proposition 5 this leads to

$$p \ \mid \ {\rm res}(u,v) \ \ \ \ \iff \ \ \ \ {\gcd}(\overline{u},\overline{v}) \neq 1$$ (69)

From Relation (59) we have

$${\gcd}(\overline{f},\overline{g}) \ = \ {\gcd}(\overline{u},\overline{v}) \ \overline{h} / \overline{{\alpha}}$$ (70)

Therefore

$$p \ \ \not\mid \ {\rm res}(u,v) \ \ \ \ \iff \ \ \ \ {\gcd}(\overline{f},\overline{g}) \ = \ 1 \ \times \ \overline{h} / \overline{{\alpha}}$$ (71)

This concludes the proof of the theorem. $\qedsymbol$

Definition 5   Let $f,g \in R[x]$ be nonzero polynomials for an Euclidean domain $R$ . Let $h \in R[x]$ be ${\gcd}(f,g)$ . A prime element $p \in R$ is said lucky if $p$ does not divide ${\rm res}(f/h, g/h)$ otherwise it is said unlucky.

Example 2   Consider $f = 12x^3 -28x^2 +20x - 4$ , $g = -12x^2 +10x -2$ and $p = 17$ . We have the following computation in AXIOM (where we do not display types)

N := NonNegativeInteger

   (1)  NonNegativeInteger

Z := Integer

   (2)  Integer

U := UnivariatePolynomial(x,Z)

   (3)  UnivariatePolynomial(x,Integer)

f: U := 12*x^3 -28*x^2 +20*x - 4

           3      2
   (4)  12x  - 28x  + 20x - 4

g: U := -12*x^2 +10*x -2

             2
   (5)  - 12x  + 10x - 2

resultant(f,g)

   (6)  0

h: U := gcd(f,g)

   (7)  6x - 2

r: Z := resultant(exquo(f,h),exquo(g,h))

   (8)  2

K17 := PrimeField(17)

   (9)  PrimeField 17

r :: K17
 

   (10)  2

U17 := UnivariatePolynomial(x,K17)

   (11)  UnivariatePolynomial(x,PrimeField 17)

f17: U17 := f :: U17

            3     2
   (12)  12x  + 6x  + 3x + 13

g17: U17 := g :: U17

           2
   (13)  5x  + 10x + 15

h17: U17 := h ::U17

   (14)  6x + 15

c17 := gcd(f17,g17)

   (15)  x + 11

h17 - (leadingCoefficient(h17)) * c17

   (16)  0

Example 3   Consider $f = x^4 -3x^2 + 2x$ , $g = x^3 -1$ and $p = 13$ . We have the following computation in AXIOM (where we do not display types) The variables N, Z, U are defined as above.

f: U := x^4 -3*x^3 + 2*x 

         4     3
   (4)  x  - 3x  + 2x

g: U := x^3  -1

         3
   (5)  x  - 1

resultant(f,g)

   (6)  0

h: U := gcd(f,g)

   (7)  x - 1

r: Z := resultant(exquo(f,h),exquo(g,h))

   (8)  9

K3 := PrimeField(3)

   (9)  PrimeField 3

r :: K3

   (10)  0

U3 := UnivariatePolynomial(x,K3)

   (11)  UnivariatePolynomial(x,PrimeField 3)

f3: U3 := f :: U3

          4
   (12)  x  + 2x

g3: U3 := g :: U3

          3
   (13)  x  + 2

h3: U3 := h ::U3

   (14)  x + 2

c3 := gcd(f3,g3)

          3
   (15)  x  + 2

exquo(c3, h3)

          2
   (16)  x  + x + 1