В алгебре содержимое ненулевого многочлена с целыми коэффициентами (или, в более общем смысле, с коэффициентами в уникальной области факторизации ) является наибольшим общим делителем его коэффициентов. Первообразная часть такого многочлена является частным от деления многочлена на его содержимое. Таким образом , многочлен является произведением своей примитивной части и своего содержимого, и это факторизация является единственной с точностью до умножения содержимого на единицу кольца коэффициентов (и умножения примитивной части на обратную единице величину) .
Многочлен является примитивным, если его содержимое равно 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 , то примитивная часть должна быть изменена путем деления ее на ту же единицу, чтобы сохранить равенство, которое называется факторизацией содержания примитивной части полинома P .
Основные свойства содержания и примитивной части являются результатами леммы Гаусса , которая утверждает, что произведение двух примитивных многочленов является примитивным, где многочлен является примитивным, если 1 является наибольшим общим делителем его коэффициентов. Это подразумевает:
Последнее свойство подразумевает, что вычисление факторизации примитивной части-содержания многочлена сводит вычисление его полной факторизации к отдельной факторизации содержания и примитивной части. Это, как правило, интересно, поскольку вычисление факторизации простой части-содержания включает только вычисление наибольшего общего делителя в R , что обычно намного проще факторизации.
Факторизацию примитивной части содержания можно распространить на многочлены с рациональными коэффициентами следующим образом.
Если задан многочлен P с рациональными коэффициентами, то, переписав его коэффициенты с тем же общим знаменателем d , можно переписать P как
где Q — многочлен с целыми коэффициентами. Содержание P — это частное от деления содержания Q на d , то есть
а примитивная часть P является примитивной частью Q :
Легко показать, что это определение не зависит от выбора общего знаменателя и что факторизация примитивной части остается справедливой:
Это показывает, что каждый многочлен над рациональными числами связан с уникальным примитивным многочленом над целыми числами и что алгоритм Евклида позволяет вычислить этот примитивный многочлен.
Следствием этого является то, что факторизация многочленов по рациональным числам эквивалентна факторизации примитивных многочленов по целым числам. Поскольку многочлены с коэффициентами в поле встречаются чаще, чем многочлены с целыми коэффициентами, может показаться, что эта эквивалентность может быть использована для факторизации многочленов с целыми коэффициентами. На самом деле, истина в точности противоположна: каждый известный эффективный алгоритм факторизации многочленов с рациональными коэффициентами использует эту эквивалентность для сокращения проблемы по модулю некоторого простого числа p (см. Факторизация многочленов ).
Эта эквивалентность также используется для вычисления наибольших общих делителей многочленов, хотя алгоритм Евклида определен для многочленов с рациональными коэффициентами. Фактически, в этом случае алгоритм Евклида требует вычисления сокращенной формы многих дробей, и это делает алгоритм Евклида менее эффективным, чем алгоритмы, которые работают только с многочленами над целыми числами (см. Наибольший общий делитель многочлена ).
Результаты предыдущего раздела остаются в силе, если кольцо целых чисел и поле рациональных чисел заменить соответственно любой уникальной областью факторизации R и ее полем дробей K.
Обычно это используется для факторизации многомерных полиномов и для доказательства того, что кольцо полиномов над уникальной областью факторизации также является уникальной областью факторизации.
Кольцо многочленов над полем является областью уникальной факторизации. То же самое верно для кольца многочленов над областью уникальной факторизации. Чтобы доказать это, достаточно рассмотреть одномерный случай, поскольку общий случай может быть выведен индукцией по числу неопределенностей.
Свойство уникальной факторизации является прямым следствием леммы Евклида : если неприводимый элемент делит произведение, то он делит один из множителей. Для одномерных многочленов над полем это следует из тождества Безу , которое само следует из алгоритма Евклида .
Итак, пусть R — уникальная факторизационная область, которая не является полем, а R [ X ] — кольцо одномерных многочленов над R. Неприводимый элемент r в R [ X ] является либо неприводимым элементом в R , либо неприводимым примитивным многочленом.
Если r принадлежит R и делит произведение двух многочленов, то он делит содержимое Таким образом, по лемме Евклида в R он делит одно из содержимых и, следовательно, один из многочленов.
Если r не является R , то это примитивный многочлен (потому что он неприводим). Тогда лемма Евклида в R [ X ] немедленно следует из леммы Евклида в K [ X ] , где K — поле дробей R .
Для факторизации многомерного многочлена над полем или над целыми числами можно рассматривать его как одномерный многочлен с коэффициентами в многочленном кольце с одним неопределенным меньше. Тогда факторизация сводится к факторизации по отдельности примитивной части и содержимого. Поскольку содержимое имеет на одно неопределенное меньше, его можно факторизовать, применяя метод рекурсивно . Для факторизации примитивной части стандартный метод состоит в подстановке целых чисел вместо неопределенных коэффициентов таким образом, чтобы не изменить степень оставшейся переменной, факторизации полученного одномерного многочлена и подъеме результата до факторизации примитивной части.
