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.