Наибольший общий делитель

Определение 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 ₀, f ₂) ¹ 1НОД() = 1.

Следствие 1.4.3. Если НОД(,) = 1, а , то .

Доказательство. Поскольку и взаимно просты, то существуют такие полиномы и , что справедливо (1.4.3). Умножая обе части соотношения (1.4.3) на , получаем

.

Левая часть данного равенства, очевидно, делится нацело на . Следовательно, делится нацело и правая часть, т. е. .