2014-02-02
2591
Рассматриваются многочлены над числовым полем. Говорят, что многочлен f (x) делится на многочлен g (x), если остаток от деления равен нолю.
Для пары многочленов f (x) и g (x) под общим делителем будем понимать многочлен, который делит f (x) и g (x) без остатка. Общий делитель определён с точностью до числового множителя.
Общий делитель пары многочленов f (x) и g (x) наибольшей степени называется наибольшим общим делителем, и обозначается НОД(f(x),g(x)).
Многочлен наименьшей степени, делящийся на f (x) и g (x) называется их наименьшим общим кратным и обозначается НОК(f(x),g(x)).
Теорема 2.3 Если многочлен делится на многочлены f (x) и g (x), то он делится и на их наименьшее общее кратное.
Доказательство Пусть 
, а 
- многочлен, делящийся на f(x) и g(x). Поделим на 
с остатком 
, здесь 
- частное, а 
- остаток. Выразим 
. По условиям, правая часть равенства делится без остатка на f(x) и g(x). Таким образом, делится на f(x) и g(x) и имеет степень меньше , что возможно только если 
Теорема 2.4 Наибольший общий делитель пары многочленов f (x) и g (x) делится без остатка на любой их общий делитель.
|
|
|
Для доказательства достаточно заметить, что наибольший общий делитель является наименьшим общим кратным общих делителей этих многочленов.
Теорема 2.5 НОД(f (x), g (x))=НОД(f (x)- v (x) g (x), g (x))
Доказательство. Положим 
и 
. Поскольку 
делится на , то делится без остатка на . Аналогично, из равенства 
вытекает делимость 
на , а, значит и делимость на . Таким образом многочлены и отличаются только числовым множителем.
Из теоремы вытекает алгоритм Евклида, если в качестве v (x) выбирать частное от деления f (x) на g (x).
Теорема 2.6 Для произвольных многочленов f (x) и g (x) найдутся такие многочлены v (x) и w (x), степень которых не превосходит степени f (x) и g (x), соответственно, что f (x) w (x) +v (x) g (x)=НОД(f (x), g (x)).
Теорема вытекает очевидным образом из алгоритма Евклида.
