2014-02-09
598
Определение 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) на , получаем
.
Левая часть данного равенства, очевидно, делится нацело на . Следовательно, делится нацело и правая часть, т. е. .
