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

Алгоритм Евклида

 

Определение. Наибольшим общим делителем (НОД) двух отличных от нуля многочленов и называется многочлен наибольшей степени среди многочленов, делящих оба многочлена и .

Обозначается наибольший общий делитель многочленов и символом . Другими словами, наибольшим общим делителем двух отличных от нуля многочленов и называется такой многочлен , который является их общим делителем и вместе с тем сам делится на любой другой общий делитель этих многочленов.

Находить наибольший общий делитель двух многочленов можно с помощью алгоритма Евклида, который состоит в следующем. Выполним цепочку делений с остатком: , ; , ; , ; …; , , .

Процесс конечен, т. е. на некотором шагу деление выполнится без остатка, потому что степень каждого последующего остатка меньше степени предыдущего. Остаток и будет наибольшим общим делителем для многочленов .

Наибольший общий делитель двух многочленов определяется с точностью до постоянного множителя. Поэтому, чтобы избежать дробных коэффициентов, можно умножать или сокращать делитель на любое не равное нулю число, причем не только начиная какое-либо из последовательных делений, но и в процессе этого деления.

Это приведет к искажению частного, но интересующие нас остатки будут приобретать лишь множители нулевой степени, что допускается при отыскании НОД.

П р и м е р. Найти наибольший общий делитель для многочленов и в кольце вещественных чисел.

Решение. Обозначим , . Найдем остаток :

 

x^5- 2 x^4 – 7 x^3 + 7 x^2 + 5 x – 4 x^5 + 2 x^4 – 3 x^3	x^2 + 2 x – 3
x^3 – 4 x^2 + 4 x − 13
− 4 x^4 – 4 x^3 +7x^2 − 4 x^4 – 8 x^3 +12x^2
	4 x^3 – 5x^2 +5x
	4x^3 + 8x^2 – 12x
	− 13x^2 + 17x − 4 − 13x^2– 26x + 39
	43x − 43

С точностью до постоянного множителя остаток равен . Найдем остаток . Для этого многочлен разделим на :

x^2 + 2x − 3 x^2 −x	x − 1
x + 3
	3x – 3 3x – 3
	0

Получили, что , следовательно, для многочленов и наибольшим общим делителем является , т. е. .

Наибольший общий делитель допускает линейное представление в виде , где и − некоторые многочлены. Можно считать при этом, что если степени многочленов и больше нуля, то степень меньше степени , а степень меньше степени . По алгоритму Евклида: , , , …, , . Получили, что . Возвращаясь назад, придем к доказываемому равенству.

П р и м е р. Для многочленов и найти такие многочлены и , чтобы .

Решение. В предыдущем примере нашли, что . Используя обратный ход в алгоритме Евклида, получим . После раскрытия скобок получим , .

П р и м е р. Найти многочлены и , чтобы выполнялось равенство для многочленов и .

Решение. Найдем такое, что :

Получили , , . Далее .

 

То есть . С другой стороны, . Далее .

 

 

Получили, что , т. е. . Учитывая, что , получим , т. е. , .

Свойства делимости многочленов

1. Если делится на , а делится на , то делится на .

Доказательство. Так как делится на , а делится на , то существуют многочлены и такие, что и . Поэтому , т. е. делится на .

2. Если и делятся на , то делится на . Доказать аналогично доказательству свойства 1.

3. Если делится на , то произведение делится на . Это свойство предлагается доказать самостоятельно.

4. Если , делится на , то , сумма делится на . Это свойство предлагается доказать самостоятельно.

5. Любой многочлен делится на многочлен нулевой степени.

Доказательство. Пусть С, С ¹ 0 – многочлен нулевой степени. Тогда , т. е. делится на С.

6. Если делится на , то делится на , где . Это свойство предлагается доказать самостоятельно.

7. Если , − делители многочлена , то они имеют такую же степень, что и .

Доказательство. Многочлен можно представить в виде . Из того, что , следует доказываемое утверждение.

8. Многочлены и делятся друг на друга, если существует , такое, что . Это свойство предлагается доказать самостоятельно.

9. Если , то делитель одного из многочленов и будет делителем и другого многочлена.

Доказательство. Пусть многочлен является делителем . Тогда существует многочлен такой, что . Поэтому , т. е. является делителем . Если же является делителем , то существует многочлен такой, что и , т. е. является делителем .

 

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

 

Определение. Два многочлена называются взаимно простыми, если их нормализованный наибольший общий делитель равен 1, т. е. эти многочлены не имеют никаких общих делителей, кроме констант.

Теорема. Для того чтобы многочлены и были взаимно просты, необходимо и достаточно, чтобы существовали многочлены и такие, что .

Доказательство. Если , то всякий общий делитель для и делит единицу и является константой. Если же и взаимно простые, то их нормализованный наибольший общий делитель 1 имеет линейное представление .