4.2. Общий делитель и аналог алгоритма Евклида.

Пусть кольцо является и — кольцо

многочленов над от переменного Как известно (Зарисский, Самюэль [1], стр. 45, теорема 10), также является

Определение 4.4. Многочлен называется примитивным, если его коэффициенты не имеют общих делителей (отличных от обратимых элементов).

Всякий ненулевой многочлен можно записать в виде

где с является ОНД коэффициентов — примитивный многочлен. Множитель с, который определен с точностью до обратимого множителя, называется содер жанием многочлена и обозначается через с

Лемма 4.1 (Зарисский, Самюэль [1], стр. 47, лемма 2). Если делит где и — примитивный многочлен, то делит многочлен

Лемма 4.2 (лемма Гаусса, см. Зарисский, Самюэль [1], стр. 46, лемма 1). Если В частности, произведение двух примитивных многочленов примитивно.

Лемма 4.3. Пусть (ненулевой) многочлен является общим делителем многочленов — примитивный многочлен. Тогда — примитивный многочлен.

Доказательство следует из сравнения коэффициентов в равенстве

Теорема 4.2 (алгоритм деления, см. Зарисский, Самюэль стр. 43, теорема 9). Пусть многочлены причем степень не меньше степени и степень не меньше 1. Тогда существуют многочлены и элемент удовлетворяющие равенству

где либо является нулевым многочленом, либо имеет степень меньшую, чем степень

Мы приведем здесь доказательство, позволяющее находить многочлены и элемент

Пусть

где

Положим

и обозначим через степень многочлена а через — коэффициент при старшей степени Ясно, что Если то теорема доказана, и тогда

Если то положим

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

в котором многочлен имеет степень

Складывая соотношения — (4.2в), получим

Так как при переходе от степень уменьшается не менее чем на единицу, то а потому Ввиду этого мы можем в последнем равенстве отбросить множитель и тогда полученное равенство совпадет с (4.1), где

и

Случай получается, когда делит Теорема доказана.

Замечание 4.1. Если выбрать по формуле (4.3), то многочлены определятся по формулам (4.4)

однозначно. Ввиду этого мы в дальнейшем будем считать, что подобрано по формуле (4.3).

Используя доказанную теорему, напишем

где означает степень многочлена Применяя, далее, этот алгоритм к многочленам к многочленам учитывая, что степени многочленов убывают, получим

где .

Теорема 4.3. Для того чтобы общий делитель многочленов имел положительную степень, необходимо и достаточно, чтобы

Доказательство необходимости. Пусть Тогда из (4.5а) следует, что из (4.52) следует, что из следует, что Но следовательно,

Доказательство достаточности.

Пусть Так как в системе равенств (4.5г) есть первый остаток, принадлежащий кольцу а степени остатков строго убывают, то Напишем, что

где с — содержание многочлена — примитивный многочлен. Покажем, что и — общий делитель многочленов Из (4.6) и следует, что

Отсюда в силу леммы 4.1 имеем, что и так что

где Из (4.6), (4.7) и имеем

Отсюда в силу леммы 4.1 следует, что и Продолжая эти рассуждения и используя соотношения (4.5.), мы найдем, что и делит все остатки а значит, и Следовательно, и Теорема доказана.

Отметим, что вместо условия теоремы 4.3 можно пользоваться следующим равенством:

где — результант многочленов

так (см., например, Ван-дер-Варден [1], стр. 115— 117) имеет место

Теорема 4.4. Для того чтобы общий делитель многочленов которых , имел положительную степень, необходимо и достаточно равенство нулю результанта определенного формулой (4.9).

При доказательстве теоремы 4.3 было установлено, что общий делитель является примитивным многочленом. В связи с этим мы введем следующее

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

Т еорена 4.5. Общий делитель найденный при доказательстве теоремы 4.3, является примитивным ОНД.

Доказательство. Из теоремы 4.3 следует, что — примитивный общий делитель. Пусть — другой примитивный общий делитель многочленов Тогда из доказательства теоремы 4.3 следует, что делит все Отсюда согласно равенству (4.6) и лемме 4.1 мы заключаем, что Теорема доказана.