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

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

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