4. Алгоритм Евклида.

Говорят, что многочлен P(x) делится на многочлен Q(x), если существует многочлен S(x), такой, что P(x) = Q(x)S(x). Многочлен S(x) называется частным от деления P(x) на Q(x). Из (??) следует, что deg S(x) = deg P(x) - degQ(x).

Теория делимости многочленов имеет много общего с теорией делимости целых чисел. В частности, выполняются следующие свойства:

• если P1(x) и P2(x) делятся на Q(x); то P1(x) + P2(x) и P1(x) - P2(x) делятся на Q(x);          (3)

• если P(x) делится на Q(x); а T(x) – произвольный многочлен; то P(x)T(x) делится на Q(x);  (4)

• если P(x) делится на Q(x); а Q(x) делится на H(x); то P(x) делится на H(x):                        (5)

Доказательство этих свойств ничем не отличается от доказательства соответствующих свойств делимости целых чисел. Отметим еще некоторые простые свойства:

• если ненулевой многочлен P(x) делится на Q(x); то deg P(x) ≥ degQ(x);                             (6)

• если deg P(x) = degQ(x); то P(x) делится на Q(x) тогда и только тогда, когда эти многочлены пропорциональны:                    (7)

(Многочлены называются пропорциональными, если один из них получается из другого умножением на число, отличное от 0.) Действительно, если P(x) делится на Q(x) и deg P(x) = degQ(x), то частное имеет степень 0, т.е. является числом, отличным от 0. Обратное утверждение очевидно.