If polynomials f(x) and g(x) have complex coefficients, their gcd is defined as another polynomial d(x) with the properties:

1) d(x) divides both f(x) and g(x)

2) every other polynomial d'(x) that divides f(x) and g(x) must divide d(x)

Oh, well, more exactly "a gcd" because it is not unique up to a multiplicative constant.

This is the definition.

But intuitively d(x) is the common divisor having the maximum degree possible.

I'm interested in a rigorous proof for this fact: the gcd is (up to a constant) the common divisor with the maximum degree.

I say like this:

I will work only with monic polynomials (dominant coefficient =1) so to not be bothered with the multiplicative constants.

Let d be the gcd according to the definition whose existence is proved by Euclid's algorithm)

And let d' be a common divisor of f and g with the greatest possible degree (I say "a " and not "the" because there may be more common divisors having the same maximum degree, I don't know yet)

Then we have d' divides d. (from definition of d)

That means that degree(d')<=degree(d) , we assume f and g are no both zero , so d is not zero)

But from the fact that d' has maximum degree we have also that degree(d')>=degree(d)

So we have deg(d')=deg(d)

But now from d'/d and this we have that d=kd', where k is a constant, but d, d' are monic so d=d'.

Is it correct?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.