Делимость многочленов. Наибольший общий делитель. Алгоритм Евклида. Расширенный алгоритм Евклида

Рассматриваются многочлены над числовым полем. Говорят, что многочлен 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)).

Теорема вытекает очевидным образом из алгоритма Евклида.

Дата добавления: 2014-01-20