UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 7

Problem:

Solution:

The key proposition to prove is
$ GCD(f_1, \cdots. f_s) = GCD(f_1, GCD(f_2, \cdots, f_s)) $.

Once we have this proposition, then all we have to do is to recursively compute the GCDs.

To prove the key proposition, we let $ a = GCD(f_2, \cdots, f_s) $ and $ b = GCD(f_1, a) $, obviously we need to prove $ b = GCD(f_1, \cdots, f_s) $.

First, obviously, $ b $ is a factor of $ f_1 $, $ b $ is also a factor of $ a $ so that it is also a factor of $ f_2, \cdots, f_s $.

So now we proved $ b $ is a common factor, but is it the greatest?

Suppose it is not, so that in fact $ c $ is $ GCD(f_1, \cdots, f_s) $. Now we know $ c = bd $ and $ d $ is not a constant.

Because $ b = GCD(f_1, a) $, $ c $ cannot be a factor of $ a $, for if it were, then $ c $ is a factor of $ f_1 $, $ c $ is a factor of $ a $, $ c $ has a higher degree than $ b $, yet $ b $ is the GCD.

Now $ c $ is a factor of $ f_2, \cdots, f_s $, $ a = GCD(f_2, \cdots, f_s) $, yet $ c $ is not a factor of $ a $. A common factor is not a factor of the greatest common factor. This is impossible (*), the contradiction proved our key proposition.

Now let us finish the unfinished business in Exercise 6. There we assumed if $ h = GCD(f_1, \cdots, f_s) $, then we can write $ h = \sum\limits_{i=1}^{s}{p_if_i} $.

If $ s = 2 $ then Exercise 4 showed what we wanted.

Now assume it can be written so for $ s = k $, now for $ s = k + 1 $, we have the recursion above

$ GCD(f_1, \cdots, f_{k+1}) = GCD(f_1, GCD(f_2, \cdots f_{k+1})) $

So $ GCD(f_1, \cdots, f_{k+1}) = Af_1 + BGCD(f_2, \cdots f_{k+1}) $.

But we know by our induction hypothesis that

$ GCD(f_2, \cdots f_{k+1}) = \sum\limits_{i = 2}^{k+1}{p_i f_i} $.

Putting it back we get what we wanted.

$ GCD(f_1, \cdots, f_{k+1}) = Af_1 + B\sum\limits_{i = 2}^{k+1}{p_i f_i} = \sum\limits_{i = 1}^{k+1}{q_i f_i}$.

By mathematical induction we proved our unfinished business in Exercise 6!

(*) To prove this, we leverage crucially on polynomials uniquely factorize.

Suppose $ d $ is a common factor and $ g $ is the greatest common factor, if $ d $ is not a factor of $ g $, then $ \frac{d}{GCD(d, g)}g $ is also a greater common factor. Prime factorization is needed to claim that.