Lattice Basis Reduction

Polynomial Factorization 291

Lemma 15.38. Let f, g ∈ Z[x] with n = deg(f ) > 0 and m = deg(g) > 0.

Suppose that u ∈ Z[x] is monic and nonconstant, and that f ≡ uv

1

(mod m)

and g ≡ uv

2

(mod m) for some v

1

, v

2

∈ Z[x] and some m > |f|

k

2

|g|

n

2

. Then

gcd(f, g) ∈ Z[x] is nonconstant.

Proof. We show by contradiction that gcd(f, g) ∈ Q[x], the GCD with rational

coefficients, is nonconstant. Suppose that gcd(f, g) = 1 in Q[x]. By Lemma

15.36 there exist s, t ∈ Z[x] such that sf + tg = res(f, g), a nd hence sf + tg ≡

res(f, g) (mod m). Since f ≡ uv

1

(mod m) and g ≡ uv

2

(mod m) we get

res(f, g) = u(sv

1

+ tv

2

) (mod m);

thus u is a divisor of res(f, g) modulo m. But u is