Теоремы о линейном представлении НОД

Если многочлен d делит какие-либо многочлены, то он называется их общим делителем. Многочлены степени 0, т.е. постоянные, отличные от нуля, всегда являются общими делителями. Общий делитель наибольшей степени называется наибольшим общим делителем. Наибольший общий делитель d многочленов обозначается НОД или просто .

Теорема 1 (о линейном представлении наибольшего общего делителя двух многочленов). Если то существуют многочлены и и v, для которых

Доказательство: Рассмотрим множество М всех многочленов вида

Это множество непусто, в частности, ему принадлежат и многочлены f и g. Если два многочлена принадлежат множеству М, то ему принадлежит и остаток от деления одного на другой. Пусть d – ненулевой многочлен в М наименьшей степени. Легко видеть, что тогда все многочлены множества М делятся на d, т.е. d – общий делитель многочленов f и g. С другой стороны, так как то существуют многочлены и и v, для которых Отсюда следует, что d делится на любой другой общий делитель многочленов f и g, а стало быть, является их наибольшим общим делителем. ■

Следствие. Наибольший общий делитель многочленов f и g делится на их любой общий делитель.

Теорема Евклида. Если

Доказательство аналогично приведенному для чисел. ■

Теорема 2. Если то существуют многочлены и и v, для которых

Доказательство: Из теоремы 1 следует, что d можно представить в виде где По теореме о делении с остатком где v и t – некоторые многочлены из Тогда Введем обозначение Докажем, что Если предположим, что то а поэтому (степень суммы равна большей степени), т.е. что неверно. Следовательно, и теорема доказана. ■

Теорема 3. Если то существует и притом единственная пара многочленов и и v, для которых имеет место тождество Безу:

Доказательство: Пусть тогда и по теореме 2 существуют многочлены и для которых

После домножения на d обеих частей полученного равенства и получим искомое. Теорема существования доказана.

Предположим, что нашлись две пары многочленов, для которых

Тогда откуда А с учетом равенств получим

Так как , то по теореме Евклида делится на :Но поэтому а следовательно, Итак, т.е. два представления совпали. ■

Пример. Найти линейное представление НОД для многочленов и

Решение: Будем искать из условия функции и и v в следующем виде:

Приравнивая соответствующие коэффициенты, получим систему

Ответ: