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

Определение 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)

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

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

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

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

. Положим .

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

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

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

.

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

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

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

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

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