Next: Mignotte's factor bound Up: Advanced Computer Algebra: The resultant Previous: The resultant

# Lucky and unlucky modular reductions

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

 gcd(f, g) R        res(f, g) 0 (36)

The formula of the resultant of f and g shows that res(f, g) is a multivariate polynomial expression in the coefficients of f and g. Hence we might be tempted to say
• = res(,).
• and are coprime in R/p[x] iff p does not divide res(f, g).

Example 1   Consider R = , p = 2, f = x + 2 and g = x. Then we have

 res(f, g) = - 2 0 mod2    and   res(,) = 0 (37)

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

 res(f, g) = 0    and   res(,) = res(x, 1) = 1 (38)

The reason for this unexpected behavior in the last example is that the Sylvester matrix of = x and = 1 is

 (39)

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

 (40)

In other words the res operation for and is not the reduction modulo 2 of the res operation for f and g. This is because the 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 R[x] be nonzero polynomials. Let r be their resultant. Let I be an ideal if R and let denote by a the reduction modulo I. Assume that

 0 (41)

Then we have

 = 0        res(,) = 0 (42)

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

 = 0        deg(gcd(,)) > 0 (43)

Proof. Let us write:

 f  =  fnxn + ... + f0    and    g  =  gmxm + ... + g0 (44)

with fn 0 and gm 0. If n = 0 then Sylv(f, g) and Sylv(,) are both diagonal with f on the diagonal. Then in that case

 =    =    =  res(,)m (45)

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

 Sylv(f, g)  = (46)

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

 res(f, g)  =  (- 1)nm (47)

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

 =  (- 1)nm (48)

Since

 =  det()  =  res(,) (49)

we obtain

 =  (- 1)nm res(,) (50)

This shows that we have

 = 0        res(,) = 0 (51)

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

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

 h = gcd(f, g),    e = deg(h).    and    = lc(h) (52)

Assume that p does not divide

 b  =  gcd(lc(f ), lc(g)) (53)

Finally let

 e *   =  deg(gcd(,)) (54)

Then we have
1. divides b
2. e * e
3. e * = e     gcd(,) =     p res(f /h, g/h)

Proof. Since in R[x]

 h  |  f    and    h  |  g (55)

we have in R

 lc(h)  |  lc(f )    and    lc(h)  |  lc(g). (56)

Therefore

 =  lc(h)  |  gcd(lc(f ), lc(g))  =  b (57)

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

 u  =  f /h    and    v  =  g/h. (58)

Then we have

 =      and       = (59)

which shows that

 |  gcd(,) (60)

and implies that

 deg()   deg(gcd(,)) (61)

Since p does not divide b, it cannot not divide neither. Hence the leading coefficient of is and we have

 deg()  =  deg(h) (62)

Therefore

 e  =  deg(h)   deg(gcd(,))  =  e * (63)

and the second claim is proved.

Now consider the case where e  =  e * . Since divides gcd(,) and since gcd(,) is monic (as a gcd over the field R/p) there exists a unit such that

 =   gcd(,) (64)

Since the leading coefficient of is we have in fact

 = (65)

Therefore we have the following equivalence

 e  =  e *           =   gcd(,) (66)

It remains to prove that

 gcd(,) =     p res(f /h, g/h) (67)

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

 = 0        res(,) = 0 (68)

By applying Proposition 5 this leads to

 p  |  res(u, v)        gcd(,) 1 (69)

From Relation (59) we have

 gcd(,)  =  gcd(,) / (70)

Therefore

 p   res(u, v)        gcd(,)  =  1 × / (71)

This concludes the proof of the theorem.

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

Example 2   Consider f = 12x3 - 28x2 + 20x - 4, g = - 12x2 + 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

(16)  0


Example 3   Consider f = x4 - 3x2 + 2x, g = x3 - 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


Next: Mignotte's factor bound Up: Advanced Computer Algebra: The resultant Previous: The resultant
Marc Moreno Maza
2004-04-27