4O. Делители многочленов. Наибольший общий делитель.

Определение 3. Пусть . Если , то говорят, чтоделится на илиделит , и пишут. Если, тоозначает, что остаток от деления равен. В этом случае многочленназываетсяделителем многочлена .

Свойства (делимости многочленов). Пусть ,,, , ,. Тогда справедливы свойства:

1) Если , .

Доказательство следует из равенства .

2) , .

Доказательство. Так как ; так как

. Тогда имеем

.

3) , .

4) выполняется.

Доказательство.. Тогда

; следовательно, .

5) Если ,, то справедливо

.

6)

Доказательство следует из равенства .

7) имеем.

8) .

Действительно, .

9) .

Доказательство.

и . Ho .

и .

10) .

Доказательство.

Если имеем .

Если и по свойству 1 имеем(в силу свойства 9).

Следует из свойства 9.

11) Если , тоимеем.

Определение 4. Многочлен называетсяобщим делителем и, еслии.Наибольшим общим делителем (НОД) двух многочленов иназывается их делитель, который делится на любой другой их общий делитель.

Замечание. Ненулевая постоянная является общим делителем любых двух многочленов.

Лемма 1. Если НОД двух многочленов исуществует, то он определен с точностью до множителя.

Доказательство. Пусть и– два НОД дляи и (по свойству 10) , для и. Пусть. Если– общий делитель дляи, то– тоже общий делитель. Если– НОД, то есть любой другой делитель делит, то− тоже НОД.■

Лемма 2. Если ,, то пары многочленов и имеют одинаковые общие делители.

Доказательство. Пусть – общий делительииз и по свойству 5. Аналогично, из делимости ина и делятся на.■

Лемма 3. Если , то.

Доказательство следует из того, что – делитель и и любой делитель и делит.

Теорема 3. Для ,НОД().

Доказательство. Рассмотрим . Если , то в силу леммы 3 и условияимеем= НОД(). Если, то поделим на с остатком. Если, то теорема доказана в силу леммы 3.

Пусть . Тогда делим на. Если остаток, то доказательство завершаем, если, то делимнаи так далее. Так как степени остатков все время уменьшаются, то процесс конечен. Таким образом, имеем следующую последовательность равенств:

,
,
,
	(E)
,
,
.

Здесь .

Из равенств () и леммы 2что пары многочленовимеют общие делителиделители и совпадают с делителями многочлена(по лемме 3)– делитель и .

Если – любой другой делитель и он делитель и– НОД.■

Замечание 1. Алгоритм построения НОД, использованный в теореме 3, называется алгоритмом Евклида или алгоритмом последовательного деления.

Замечание 2. Если .

Замечание 3. Так как НОД определен с точностью до множителя, то будем считать, что коэффициент при старшей степени равен 1.

Пример. Пусть . Используем формулы (E) для построения НОД Тогда, гдеДалее удобно рассматриватьТогдагдеОтсюда получаем:, то есть НОД

Замечание 4. При вычислении НОД результаты деления многочленов можно умножать и делить на элементы из С, что влияет лишь на множители.

Теорема 4 (теорема о разложении НОД). Пусть и,. Тогда

(2)

При этом, если , тоиможно подобрать так, чтои.

Доказательство. Если , то по лемме 3g(x)=и поэтому .

Аналогично, если .

Пусть теперь ине является делителем. Тогда можно считать, что. Из предпоследнего равенства из (Е) следует, что

. Положим .

Из равенства подставляя в последнее выражение дляd(x)

Поднимаясь дальше вверх, приходим к (2).

Докажем второе утверждение теоремы. Пусть (2) получено, но . Покажем, что (2) можно привести к виду, где. Разделимнас остатком:_, где ._. Подставляя это в (2), имеем:

.

Положим . Тогда. Покажем, что.От противного, то есть пусть. Тогда имеем:_.Так как из следует, то, что противоречит определению НОД.■

Пример. Если ,, то НОД()=

. Следовательно, .

Замечание. Аналогично вводится понятие НОД для случая многих многочленов.

 5˚. Взаимно простые многочлены.