В алгебре содержание ненулевого многочлена с целыми коэффициентами (или, в более общем плане, с коэффициентами в уникальной области факторизации ) является наибольшим общим делителем его коэффициентов. Примитивной частью такого многочлена является частное многочлена по его содержимому. Таким образом, многочлен является произведением его примитивной части и его содержания, и эта факторизация уникальна с точностью до умножения содержания на единицу кольца коэффициентов (и умножения примитивной части на обратную единицу) . .
Полином является примитивным , если его содержимое равно 1. Таким образом, примитивная часть многочлена является примитивным многочленом.
Лемма Гаусса для многочленов утверждает, что произведение примитивных многочленов (с коэффициентами в одной и той же уникальной области факторизации) также является примитивным. Это означает, что содержание и примитивная часть произведения двух многочленов являются соответственно продуктом содержания и произведения примитивных частей.
Поскольку вычисление наибольших общих делителей обычно намного проще, чем полиномиальная факторизация , первым шагом алгоритма полиномиальной факторизации обычно является вычисление его примитивной факторизации части-содержимого (см. Факторизация полиномов § Примитивная факторизация части-содержания ). Тогда задача факторизации сводится к факторизации отдельно содержимого и примитивной части.
Содержимое и примитивная часть могут быть обобщены до полиномов над рациональными числами и, в более общем смысле, до полиномов над полем дробей уникальной области факторизации. Это делает по существу эквивалентными задачи вычисления наибольших общих делителей и факторизации многочленов по целым числам и многочленов по рациональным числам.
Для многочлена с целыми коэффициентами содержимым может быть либо наибольший общий делитель коэффициентов, либо его аддитивный обратный элемент . Выбор произволен и может зависеть от дальнейшего соглашения, которое обычно заключается в том, что старший коэффициент примитивной части должен быть положительным.
Например, содержимое может быть либо 2, либо -2, поскольку 2 является наибольшим общим делителем -12, 30 и -20. Если в качестве содержимого выбрать 2, примитивная часть этого многочлена будет равна
и, таким образом, факторизация примитивной части содержания
По эстетическим соображениям часто предпочитают выбирать отрицательное содержание, здесь -2, что дает факторизацию содержания примитивной части.
В оставшейся части этой статьи мы рассматриваем полиномы в уникальной области факторизации R , которая обычно может быть кольцом целых чисел или кольцом полиномов над полем . В R максимальные общие делители четко определены и уникальны с точностью до умножения на единицу R .
Содержимое c ( P ) многочлена P с коэффициентами из R является наибольшим общим делителем его коэффициентов и, как таковое, определяется с точностью до умножения на единицу . Примитивная часть pp( P ) P — это частное P / c ( P ) P по его содержимому; это многочлен с коэффициентами из R , который уникален с точностью до умножения на единицу. Если содержимое изменяется путем умножения на единицу u , то примитивную часть необходимо изменить путем деления ее на ту же единицу, чтобы сохранить равенство
Основные свойства содержания и примитивной части являются результатами леммы Гаусса , которая утверждает, что произведение двух примитивных многочленов является примитивным, где многочлен является примитивным, если 1 является наибольшим общим делителем его коэффициентов. Из этого следует:
Последнее свойство подразумевает, что вычисление факторизации полинома по примитивной части-содержимому сводит вычисление его полной факторизации к отдельной факторизации содержания и примитивной части. В целом это интересно, поскольку вычисление факторизации содержания простых частей включает в себя только вычисление наибольшего общего делителя в R , что обычно намного проще, чем факторизация.
Факторизация содержания примитивных частей может быть расширена до полиномов с рациональными коэффициентами следующим образом.
Учитывая многочлен P с рациональными коэффициентами, переписывая его коэффициенты с тем же общим знаменателем d , можно переписать P как
где Q — многочлен с целыми коэффициентами. Содержимое P — это частное по d содержимого Q , то есть
а примитивная часть P является примитивной частью Q :
Легко показать, что это определение не зависит от выбора общего знаменателя и что факторизация примитивной части-содержания остается справедливой:
Это показывает, что каждому многочлену рациональных чисел соответствует уникальный примитивный многочлен целых чисел и что алгоритм Евклида позволяет вычислить этот примитивный многочлен.
Следствием этого является то, что факторизация полиномов по рациональным числам эквивалентна факторизации примитивных многочленов по целым числам. Поскольку полиномы с коэффициентами в поле встречаются чаще, чем полиномы с целыми коэффициентами, может показаться, что эту эквивалентность можно использовать для факторизации полиномов с целыми коэффициентами. На самом деле, правда как раз наоборот: каждый известный эффективный алгоритм факторизации многочленов с рациональными коэффициентами использует эту эквивалентность для сведения задачи по модулю некоторого простого числа p (см. Факторизация многочленов ).
Эта эквивалентность также используется для вычисления наибольших общих делителей многочленов, хотя алгоритм Евклида определен для многочленов с рациональными коэффициентами. Фактически, в этом случае алгоритм Евклида требует вычисления приведенной формы многих дробей, и это делает алгоритм Евклида менее эффективным, чем алгоритмы, которые работают только с полиномами над целыми числами (см. Полиномиальный наибольший общий делитель ).
Результаты предыдущего раздела остаются в силе, если кольцо целых чисел и поле рациональных чисел соответственно заменяются любой уникальной областью факторизации R и ее полем дробей K .
Обычно это используется для факторизации многомерных полиномов , а также для доказательства того, что кольцо многочленов в уникальной области факторизации также является уникальной областью факторизации.
Кольцо полиномов над полем является уникальной областью факторизации. То же самое верно и для кольца полиномов в уникальной области факторизации. Чтобы доказать это, достаточно рассмотреть одномерный случай, так как общий случай можно вывести индукцией по числу неопределенных.
Уникальное свойство факторизации является прямым следствием леммы Евклида : если неприводимый элемент делит произведение, то он делит один из множителей. Для одномерных полиномов над полем это следует из тождества Безу , которое само по себе является результатом алгоритма Евклида .
Итак, пусть R — уникальная область факторизации, которая не является полем, а R [ X ] — кольцо одномерных многочленов над R. Неприводимый элемент r в R [ X ] — это либо неприводимый элемент в R , либо неприводимый примитивный полином.
Если r находится в R и делит произведение двух многочленов, то он делит содержимое. Таким образом, по лемме Евклида в R он делит одно из содержимого и, следовательно, один из многочленов.
Если r не R , это примитивный полином (поскольку он неприводим). Тогда лемма Евклида в R [ X ] непосредственно следует из леммы Евклида в K [ X ] , где K — поле частных R.
Для факторизации многомерного многочлена по полю или целым числам его можно рассматривать как одномерный многочлен с коэффициентами в кольце многочленов с одним неопределенным меньше. Тогда факторизация сводится к факторизации отдельно примитивной части и содержимого. Поскольку в содержании на одну неопределенную величину меньше, его можно факторизовать, применив метод рекурсивно . Для факторизации примитивной части стандартный метод состоит из замены целых чисел неопределенными коэффициентами таким образом, чтобы не изменить степень оставшейся переменной, факторизации полученного одномерного многочлена и поднятия результата до факторизации примитивной части. .
