Делимость многочленов
Начнем этот параграф с аналога теоремы о делении с остатком для целых чисел.
Теорема 3.3 (о делении с остатком для многочленов).
Пусть заданы два многочлена
и
.
Тогда имеет место представление
,
где
или
.
Здесь
и называются соответственно неполным
частным и остатком от деления. Указанное
представление единственно.
Доказательство. Единственность. Пусть, например, существуют два представления
и
.
Вычитая из первого второе, получим
или
.
Если
,
то
,
но тогда
и
,
что приводит к противоречию. Но тогда
,
ибо – целостное кольцо.
Теперь докажем существование представления. Сначала рассмотрим частные случаи.
1. Пусть
.
Тогда
.
2. Пусть
,
таким образом,
,
.
Тогда, как легко видеть,
.
И, наконец, опишем основной случай, когда
.
Пусть заданы многочлены
и
.
И
.
Рассмотрим цепочку разностей
–
старший коэффициент
;
–
старший коэффициент
;
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
–
старший коэффициент
;
,
.
Просуммируем полученные равенства. Имеем
.
Теперь обозначая
и
,
получаем требуемое.
Определение 3.7. Пусть заданы
многочлены
,
,
тогда говорят, что
делится на
,
если существует такой многочлен
,
что имеет место равенство
.
Обозначение:
.
Лемма 3.4 (критерий делимости)
Многочлен делится на тогда и только тогда, когда остаток от деления в теореме 3.3 равен нулю.
Свойства делимости многочленов.
1.
Если
– свойство транзитивности делимости;
2.
Если
;
3.
Если
;
4.
Если
;
5. Каждый многочлен делится на многочлен нулевой степени;
6.
Если
,
то
,
где
;
7.
,
где
;
8.
,
где
,
;
9. Множество делителей многочлена совпадает с множеством делителей
многочлена
,
где
.
Эти свойства легко доказываются по определению с привлечением леммы 3.2.
Определение. 3.8. Пусть
.
Если
,
то тогда
называется общим делителем многочленов
и
.
Нашей ближайшей задачей является обсуждение понятия наибольшего общего делителя двух многочленов. Но ввести это понятие гак, как это делается в кольце целых чисел, не представляется возможным ввиду того, что множество многочленов не является упорядоченным, как это имеет место во множестве целых рациональных чисел. Поэтому поступим, давая определение в случае с многочленами, используя одно известное свойство наибольшего общего делителя целых.
Определение 3.9. Наибольшим общим
делителем двух многочленов называется
такой их общий делитель, который делится
на любой их общий делитель. Обозначение:
для
их НОД
.
Это определение страдает заведомой
неоднозначностью, что следует из свойства
9
.
Таким образом, НОД двух многочленов
определен с точностью до мультипликативной
константы из
,
т.е. многочлена нулевой степени.
Определение 3.10. Два многочлена называются взаимно простыми, если их НОД равен многочлену нулевой степени.
Данные здесь определения не гарантируют существования определяемого объекта. Поэтому займемся доказательством существования НОД. Теорема, которая будет доказана носит конструктивный характер в том смысле, что следуя идее доказательства, можно построить НОД. Поэтому ее и называют алгоритмом.
Теорема 3.4 (алгоритм Евклида).
Наибольший общий делитель двух многочленов существует.
Доказательство. Пусть заданы
многочлены
и
.
Пусть для определенности
.
Тогда имеем по теореме о делении с
остатком 3.3:
;
;
;
. . . . . . . . . . . . . . . . .
.
Как видно, степени остатков строго
убывают, и поэтому обязательно наступит
момент деления нацело. Например, последний
отличный от нуля остаток будет многочленом
нулевой степени. Утверждаем, что
наибольшим общим делителем
и
как раз и является последний отличный
от нуля остаток в череде последовательных
делений. Действительно, как легко видеть,
является общим делителем
и
.
Этот многочлен делит все предыдущие
остатки, если подниматься по лестнице
соотношений снизу вверх, и наконец,
делит
и
.
С другой стороны, любой общий делитель
и
,
скажем
,
делит в свою очередь все остатки, в том
числе и
.
Это прослеживается, если последовательно
пройти по выписанным соотношениям
теперь сверху вниз. Поэтому в соответствии
с определением можно утверждать, что
.
Следствие. Если
,
то
.
Пример 3.2. Пусть
,
а
.
Найдем НОД
.
Условимся для сохранения вычислений в
кольце целых чисел умножать вычисляемые
остатки на подходящие множители помня
о том, что НОД двух многочленов определен
с точностью до мультипликативной
константы. При этом, разумеется, безнадежно
портятся неполные частные. Итак,
;
;
;
.
Последний, отличный от нуля остаток
.
Таким образом,
.
Теорема 3.5 (о линейном представлении НОД).
Пусть
и
.
Тогда найдутся такие многочлены
,
что
.
При этом, если
и
,
то
и
можно подобрать так, что
,
а
.
Доказательство. Доказательство
существования представления НОД легко
получить из соотношений, по которым
строится наибольший общий делитель.
Надо лишь последовательно выражать
последний отличный от нуля остаток
через вышестоящие выражения многочленов.
А вот доказательство второй части не
так очевидно. Пусть напротив, например,
.
Разделим
на
.
Получим
.
Рассмотрим оба случая. Пусть сначала
.
Тогда, подставляя выражение для
в представление НОД, получаем
.
Если теперь обозначить
,
а
,
то получим выражение для НОД в виде
,
где
,
и остается показать, что
.
Действительно, если бы
,
то в выражении для
степень этого многочлена определялась
бы вторым слагаемым, т.е.
,
что невозможно, ибо
.
Во втором случае имеем:
.
Таким образом,
и, значит, можно считать, что
,
а значит,
,
т.е.,
.
Но тогда
.
И теперь, обозначая через
,
а
получаем требуемое, ибо
,
а
.
Теорема доказана.
Рассмотрим теперь отдельно вопрос о свойствах взаимно простых многочленов. Из необходимых в дальнейшем отметим три:
1.
Если
;
2.
Если
;
3.
Если
.
Докажем, например, первое свойство. Из условия взаимной простоты и следует по теореме 3.5, что
для некоторых и . Умножим обе части этого равенства на многочлен . Получим
.
Так как
и
делится на себя, то по второму свойству
делимости получаем, что и
.
Остальные свойства доказываются похожим
образом.
Теорема 3.6 (критерий взаимной простоты двух многочленов).
Два многочлена взаимно просты тогда и только тогда, когда линейное представление их наибольшего общего делителя есть
.
Доказательство как необходимости, так и достаточности здесь тривиально. Но имеется
Следствие. Многочлены и в формулировке теоремы определены однозначно, если и .
Действительно, если предположить, что имеются два подобных представления
и
,
то, вычитая из первого второе, получим
.
Так как
,
а по первому свойству взаимно простых
многочленов
,
то немедленно приходим к противоречию,
если
.
Значит,
.
Но тогда и
,
ибо
– целостное кольцо.