Определение 1.4.1. Полином называется общим делителем двух полиномов и , если , .
Определение 1.4.2. Общий делитель полиномов и называется наибольшим общим делителем (НОД), если делится нацело на любой другой общий делитель этих полиномов.
Определение 1.4.3. Полиномы и называются взаимно простыми, если они не имеют общих делителей положительных степеней.
Лемма 1.4.1. Наибольший общий делитель двух полиномов определяется с точностью до постоянного сомножителя.
Доказательство. Пусть даны два различных наибольших общих делителя и полиномов и . По определению НОД имеем
,,
т. е. полиномы и являются константами.
Приведем конструктивный способ построения НОД двух полиномов и , который называется алгоритмом Евклида.
Пусть для определенности . Имеем цепочку равенств
, , , …, , . (1.4.1)
Так как , то цепочка равенств (1.4.1) конечна и в ней существует звено, в котором деление осуществляется нацело. Докажем, что полином является наибольшим общим делителем полиномов и .
Действительно,
, ,
т. е. является общим делителем полиномов и .
|
|
Пусть =НОД().
, , …, .
В силу произвольности и в соответствии с определением НОД получаем, что = НОД().
Теорема 1.4.1. Если — это наибольший общий делитель полиномов и , то существуют такие полиномы и , что
. (1.4.2)
Доказательство. В соответствии с алгоритмом Евклида =. Но
,
где , .
Из (1.4.1)
,
где , .
Далее заменяем и т. д. В итоге имеем
,
, ,
Поэтому окончательно
,
где , .
Следствие 1.4.1. Полиномы и взаимно просты тогда и только тогда, когда существуют полиномы и , для которых
. (1.4.3)
Следствие 1.4.2. Если НОД(,) = 1, НОД(,) = 1, то
НОД(,) = 1.
Доказательство. Так как и взаимно просты, то существуют такие полиномы и , что
.
Умножая обе части данного соотношения на , получаем
.
Пусть = НОД(), . Тогда
НОД(f 0, f 2) ¹ 1НОД() = 1.
Следствие 1.4.3. Если НОД(,) = 1, а , то .
Доказательство. Поскольку и взаимно просты, то существуют такие полиномы и , что справедливо (1.4.3). Умножая обе части соотношения (1.4.3) на , получаем
.
Левая часть данного равенства, очевидно, делится нацело на . Следовательно, делится нацело и правая часть, т. е. .