Неприводимый многочлен

В математике неприводимый многочлен, грубо говоря, является многочленом, который не может быть разложенным на произведение двух непостоянных многочленов. Свойство несводимости зависит от природы коэффициентов, которые принимаются для возможных факторов, то есть от поля или кольца, к которому коэффициенты полином и его возможные множители должны принадлежать. Например, многочлен x - 2 является многочленом с целыми коэффициентами, но, поскольку каждое целое число также является действительным числом, оно также является многочленом с действительными коэффициентами. Это неприводимо, если его рассматривать как многочлен с целыми коэффициентами, но он множится как $(x\; -\; 2)\; (x\; +\; 2)\; \{\backslash \; displaystyle\; \backslash \; left\; (x\; -\; \{\backslash \; sqrt\; \{2\; \}\}\; \backslash \; right)\; \backslash \; left\; (x\; +\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; right)\}$, если он рассматривается как многочлен с действительными коэффициентами. Говорят, что многочлен x - 2 неприводим по целым числам, но не по действительным числам.

Полином, неприводимый над любым полем, содержащим коэффициенты, является абсолютно неприводимым. Согласно основной теореме алгебры, одномерный многочлен абсолютно неприводим тогда и только тогда, когда его степень равна единице. С другой стороны, с несколькими неопределенными существуют абсолютно неприводимые многочлены любой степени, например, $x\; 2\; +\; yn\; -\; 1,\; \{\backslash \; displaystyle\; x\; ^\; \{2\}\; +\; y\; ^\; \{n\}\; -1,\}$для любого положительного целого числа n.

Полином, который не является неприводимым, иногда называют приводимым . Однако этот термин следует использовать с осторожностью, так как он может относиться к другим понятиям редукции.

Неприводимые многочлены естественным образом появляются при изучении полиномиальной факторизации и расширений алгебраических полей.

Полезно сравнить неприводимые многочлены с простыми числами : простые числа (вместе с соответствующими отрицательными числами равной величины) являются неприводимыми целыми числами. Они демонстрируют многие общие свойства концепции «неприводимости», которые в равной степени применимы к неприводимым многочленам, такие как уникальная факторизация на простые или неприводимые множители. Когда кольцо коэффициентов является полем или другой уникальной областью факторизации, неприводимый многочлен также называется простым многочленом, поскольку он генерирует простой идеал.

• 1 Определение
  • 1.1 Природа множителя
• 2 Простые примеры
• 3 По комплексным числам
• 4 По действительным числам
• 5 Уникальное свойство факторизации
• 6 По целым числам и конечному полю
• 7 Алгоритмы
• 8 Расширение поля
• 9 В области целостности
• 10 См. Также
• 11 Примечания
• 12 Ссылки
• 13 Внешние ссылки

Если F - поле, непостоянный многочлен неприводим над F, если его коэффициенты принадлежат F, и он не может быть разложен на произведение двух непостоянных многочленов с коэффициентами в F.

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

Часто используется другое определение: многочлен неприводим над R, если он неприводим над полем дробей числа R (поле рациональных чисел, если R целые числа). Это второе определение не используется в этой статье.

Природа множителя

Отсутствие явного алгебраического выражения для множителя само по себе не означает, что полином неприводим. Когда многочлен сводится к множителям, эти множители могут быть явными алгебраическими выражениями или неявными выражениями. Например, $x\; 2\; +\; 2\; \{\backslash \; displaystyle\; x\; ^\; \{2\}\; +2\}$можно явно разложить на комплексные числа как $(x\; -\; 2\; i)\; (x\; +\; 2\; i);\; \{\backslash \; displaystyle\; \backslash \; left\; (x\; -\; \{\backslash \; sqrt\; \{2\}\}\; i\; \backslash \; right)\; \backslash \; left\; (x\; +\; \{\backslash \; sqrt\; \{2\}\}\; i\; \backslash \; right);\}$однако Авель– Теорема Руффини утверждает, что существуют полиномы любой степени больше 4, для которых существуют сложные множители, не имеющие явного алгебраического выражения. Такой коэффициент можно записать просто как, скажем, $(x\; -\; x\; 1),\; \{\backslash \; displaystyle\; \backslash \; left\; (x-x\_\; \{1\}\; \backslash \; right),\}$где $x\; 1\; \{\backslash \; displaystyle\; x\_\; \{1\}\}$неявно определяется как частное решение уравнения, которое устанавливает полином равным 0. Кроме того, факторы любого типа также могут быть выражены как числовые приближения, получаемые с помощью алгоритмы поиска корней, например как $(x\; -\; 1.2837\dots ).\; \{\backslash \; displaystyle\; \backslash \; left\; (x-1.2837\; \backslash \; ldots\; \backslash \; right).\}$

Следующие шесть многочленов демонстрируют некоторые элементарные свойства приводимых и неприводимых многочленов:

$p\; 1\; (x)\; =\; x\; 2\; +\; 4\; x\; +\; 4\; =\; (x\; +\; 2)\; (x\; +\; 2)\; p\; 2\; (x)\; =\; x\; 2\; -\; 4\; =\; (x\; -\; 2)\; (x\; +\; 2)\; p\; 3\; (x)\; =\; 9\; x\; 2\; -\; 3\; =\; 3\; (3\; x\; 2\; -\; 1)\; =\; 3\; (x\; 3\; -\; 1)\; (x\; 3\; +\; 1)\; p\; 4\; (x)\; =\; x\; 2\; -\; 4\; 9\; =\; (x\; -\; 2\; 3)\; (x\; +\; 2\; 3)\; p\; 5\; (\; Икс)\; знак\; равно\; Икс\; 2-2\; =\; (Икс\; -\; 2)\; (Икс\; +\; 2)\; п\; 6\; (Икс)\; =\; Икс\; 2\; +\; 1\; =\; (Икс\; -\; Я)\; (Х\; +\; Я)\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{выровнено\}\; р\_\; \{\; 1\}\; (x)\; =\; x\; ^\; \{2\}\; +\; 4x\; +\; 4\; \backslash ,\; =\; \{(x\; +\; 2)\; (x\; +\; 2)\}\; \backslash \backslash \; p\_\; \{2\}\; (x)\; =\; x\; ^\; \{2\}\; -4\; \backslash ,\; =\; \{(x-2)\; (x\; +\; 2)\}\; \backslash \backslash \; p\_\; \{3\}\; (x)\; =\; 9x\; ^\; \{2\}\; -3\; \backslash ,\; =\; 3\; \backslash \; left\; (3x\; ^\; \{2\}\; -1\; \backslash \; right)\; \backslash ,\; =\; 3\; \backslash \; left\; (x\; \{\backslash \; sqrt\; \{3\}\}\; -\; 1\; \backslash \; right)\; \backslash \; left\; (x\; \{\backslash \; sqrt\; \{3\}\}\; +\; 1\; \backslash \; right)\; \backslash \backslash \; p\_\; \{4\}\; (x)\; =\; x\; ^\; \{2\; \}\; -\; \{\backslash \; frac\; \{4\}\; \{9\}\}\; \backslash ,\; =\; \backslash \; left\; (x\; -\; \{\backslash \; frac\; \{2\}\; \{3\}\}\; \backslash \; right)\; \backslash \; left\; (x\; +\; \{\backslash \; frac\; \{2\}\; \{3\}\}\; \backslash \; right)\; \backslash \backslash \; p\_\; \{5\}\; (x)\; =\; x\; ^\; \{2\}\; -2\; \backslash ,\; =\; \backslash \; left\; (x\; -\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; right)\; \backslash \; left\; (x\; +\; \{\backslash \; sqrt\; \{2\}\}\; \backslash \; right)\; \backslash \backslash \; p\_\; \{6\}\; (x)\; =\; x\; ^\; \{2\}\; +1\; \backslash ,\; =\; \{(xi)\; (x\; +\; i)\}\; \backslash \; end\; \{align\}\}\}$

Более целых чисел, первые три полинома приводимы (третий - редукционный. cible, потому что множитель 3 не обратим в целых числах); последние два неприводимы. (Четвертый, конечно, не является многочленом от целых чисел.)

Над рациональными числами первые два и четвертый многочлены приводимы, но три других многочлена неприводимы (как полином по рациональным числам, 3 является единицей и, следовательно, не учитывается как фактор).

По действительным числам первые пять многочленов приводимы, но $p\; 6\; (x)\; \{\backslash \; displaystyle\; p\_\; \{6\}\; (x)\}$неприводимо.

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

Над комплексным полем и, в более общем смысле, над алгебраически замкнутым полем, одномерный многочлен неприводимо тогда и только тогда, когда его степень равна единице. Этот факт известен как фундаментальная теорема алгебры в случае комплексных чисел и, в общем, как условие алгебраической замкнутости.

Отсюда следует, что каждый непостоянный одномерный многочлен может быть разложен на множители как

$a\; (x\; -\; z\; 1)\; \cdots \; (x\; -\; zn)\; \{\backslash \; displaystyle\; a\; \backslash \; left\; (x-z\_\; \{1\}\; \backslash \; right)\; \backslash \; cdots\; \backslash \; left\; (x-z\_\; \{n\}\; \backslash \; right)\}$

где $n\; \{\backslash \; displaystyle\; n\}$- градус, $a\; \{\backslash \; displaystyle\; a\}$- старший коэффициент, а $z\; 1,\dots ,\; zn\; \{\backslash \; displaystyle\; z\_\; \{1\},\; \backslash \; dots,\; z\_\; \{n\}\}$- нули полинома (не обязательно разные, и не обязательно иметь явные алгебраические выражения ).

Существуют неприводимые многомерные многочлены любой степени над комплексными числами. Например, многочлен

$xn\; +\; yn\; -\; 1,\; \{\backslash \; displaystyle\; x\; ^\; \{n\}\; +\; y\; ^\; \{n\}\; -1,\}$

, который определяет кривую Ферма, неприводим для каждый положительный n.

По полю вещественного степень неприводимого одномерного многочлена равна единице или двум. Точнее, неприводимые многочлены - это многочлены первой степени и квадратичные многочлены $ax\; 2\; +\; bx\; +\; c\; \{\backslash \; displaystyle\; ax\; ^\; \{2\}\; +\; bx\; +\; c\}$имеющие отрицательный дискриминант $b\; 2\; -\; 4\; ас.\; \{\backslash \; displaystyle\; b\; ^\; \{2\}\; -4ac.\}$Отсюда следует, что любой непостоянный одномерный многочлен может быть разложен на множители как произведение многочленов степени не выше двух. Например, $x\; 4\; +\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{4\}\; +1\}$множится на действительные числа как $(x\; 2\; +\; 2\; x\; +\; 1)\; (x\; 2\; -\; 2\; х\; +\; 1),\; \{\backslash \; displaystyle\; \backslash \; left\; (x\; ^\; \{2\}\; +\; \{\backslash \; sqrt\; \{2\}\}\; x\; +\; 1\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{2\}\; -\; \{\backslash \; sqrt\; \{2\}\}\; x\; +\; 1\; \backslash \; справа),\}$и его нельзя разложить на множители, поскольку оба фактора имеют отрицательный дискриминант:

Каждый многочлен над полем F может быть разложен на произведение ненулевой константы и конечного числа неприводимых (над F) многочленов. Это разложение является уникальным до порядка факторов и умножения факторов на ненулевые константы, произведение которых равно 1.

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

Пусть F - уникальная область факторизации. Непостоянный неприводимый многочлен над F примитивен. Примитивный многочлен над F неприводим над F тогда и только тогда, когда он неприводим над полем дробей F. Каждый многочлен над F может быть разложен на произведение ненулевой константы и конечного числа непостоянных неприводимых примитивных многочленов. Сама ненулевая константа может быть разложена на произведение единицы F и конечного числа неприводимых элементов F. Обе факторизации уникальны до порядка множителей и умножение множителей на единицу F.

Это та теорема, которая мотивирует, что определение неприводимого многочлена в единственной области факторизации часто предполагает, что многочлен непостоянен.

Все алгоритмы, которые в настоящее время реализованы для разложения многочленов по целым числам и по рациональным числам, используют этот результат (см. Факторизация многочленов ).

Неприводимость полинома над целыми числами $Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\}$связана с тем, что над поле $F\; p\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{p\}\}$из $p\; \{\backslash \; displaystyle\; p\}$элементов (для простого $п\; \{\backslash \; displaystyle\; p\}$). В частности, если одномерный многочлен f над $Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\}$неприводим над $F\; p\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{p\}\}$для некоторого простого числа $p\; \{\backslash \; displaystyle\; p\}$, которое не делит старший коэффициент f (коэффициент наивысшей степени переменной), тогда f неприводимо по $Z\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\}$. критерий Эйзенштейна является вариантом этого свойства, в котором несводимость по $p\; 2\; \{\backslash \; displaystyle\; p\; ^\; \{2\}\}$равна также участвует.

Обратное, однако, неверно: существуют полиномы сколь угодно большой степени, неприводимые по целым числам и приводимые по любому конечному полю. Простой пример такого многочлена: $x\; 4\; +\; 1.\; \{\backslash \; displaystyle\; x\; ^\; \{4\}\; +1.\}$

Связь между неприводимостью целых чисел и неприводимостью по модулю p глубже, чем в предыдущем результате: На сегодняшний день все реализованные алгоритмы факторизации и неприводимости по целым числам и по рациональным числам используют факторизацию по конечным полям в качестве подпрограммы.

Число неприводимых монических многочленов степени n над полем $F\; q\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{q\}\}$для qa степень простого числа определяется как

$N\; (q,\; n)\; =\; 1\; n\; \sum \; d\; \mid \; n\; \mu \; (d)\; qnd,\; \{\backslash \; displaystyle\; N\; (q,\; n)\; =\; \{\backslash \; frac\; \{1\}\; \{n\}\}\; \backslash \; sum\; \_\; \{d\; \backslash \; mid\; n\}\; \backslash \; mu\; (d)\; q\; ^\; \{\backslash \; frac\; \{n\}\; \{d\}\},\}$

, где μ - функция Мёбиуса. Для q = 2 такие многочлены обычно используются для генерации псевдослучайных двоичных последовательностей.

В некотором смысле почти все многочлены с коэффициентами ноль или один неприводимы по целым числам. Точнее, если предполагается версия гипотезы Римана для дзета-функций Дедекинда, вероятность несократимости по целым числам для многочлена с случайными коэффициентами в {0, 1} стремится к единице, когда степень увеличивается.

Уникальное свойство факторизации полиномов не означает, что факторизация данного полинома всегда может быть вычислена. Даже неприводимость полинома не всегда может быть доказана вычислением: существуют поля, в которых не может существовать алгоритм для определения несводимости произвольных многочленов.

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

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

Пусть x будет элементом расширения L поля K. Этот элемент называется алгебраическим, если он является корнем многочлена с коэффициентами в K. Среди многочленов, у которых x является корнем, есть ровно один, который является monic и имеет минимальную степень, называемый минимальным многочленом от x. Минимальный многочлен алгебраического элемента x из L неприводим и является единственным моническим неприводимым многочленом, корнем которого является x. Минимальный многочлен от x делит каждый многочлен, имеющий x в качестве корня (это теорема Абеля о неприводимости ).

И наоборот, если $P\; (X)\; \in \; K\; [X]\; \{\backslash \; displaystyle\; P\; (X)\; \backslash \; in\; K\; [X]\}$является одномерным многочленом над полем K, пусть $L\; =\; K\; [X]\; /\; P\; (X)\; \{\backslash \; displaystyle\; L\; =\; K\; [X]\; /\; P\; (X)\}$будет частным кольцом кольца многочленов $K\; [X]\; \{\backslash \; displaystyle\; K\; [X]\}$с помощью идеала, порожденного с помощью P. Тогда L является полем тогда и только тогда, когда P неприводимо над K. In В этом случае, если x является образом X в L, минимальный многочлен x является частным от P по его ведущему коэффициенту.

Примером вышесказанного является стандартное определение комплексных чисел как $C\; =\; R\; [X]\; /\; (X\; 2\; +\; 1).\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{C\}\; =\; \backslash \; mathbb\; \{R\}\; [X]\; /\; \backslash \; left\; (X\; ^\; \{2\}\; +1\; \backslash \; right).\}$

Если многочлен P имеет неприводимый множитель Q над K, который имеет степени больше единицы, можно применить к Q предыдущую конструкцию алгебраического расширения, чтобы получить расширение, в котором P имеет по крайней мере на один корень больше, чем в K. Итерируя эту конструкцию, можно в конечном итоге получить поле, по которому P разлагается на линейные факторы. Это поле, уникальное от до изоморфизма поля , называется полем разделения P.

Если R является областью целостности, элемент f из R, который не является ни нулем, ни единицей, называется неприводимым, если нет неединиц g и h с f = gh. Можно показать, что каждый простой элемент неприводим; обратное неверно в общем случае, но верно в уникальных доменах факторизации. Кольцо полиномов F [x] над полем F (или любой областью уникальной факторизации) снова является областью уникальной факторизации. Индуктивно это означает, что кольцо многочленов от n неопределенностей (над кольцом R) является уникальной областью факторизации, если то же самое верно и для R.

• лемму Гаусса (многочлен)
• Рациональный корневая теорема, метод определения того, имеет ли многочлен линейный множитель с рациональными коэффициентами
• критерий Эйзенштейна
• метод Перрона
• теорема о неприводимости Гильберта
• критерий неприводимости Кона
• Неприводимая компонента топологического пространства
• Факторизация многочленов над конечными полями
• Функция четвертого порядка § Приводимые квартики
• Кубическая функция § Факторизация
• Casus unducibilis, неприводимая кубика с тремя действительными корнями
• Квадратное уравнение § Квадратичное разложение

• Ланг, Серж (2002), Алгебра, Тексты для выпускников по математике, 211 ( Пересмотренное третье изд.), Нью-Йорк: Springer-Verlag, ISBN 978-0-387-95385-4, MR 1878556. Эта классическая книга охватывает большую часть содержания этой статьи.
• Галлиан, Джозеф (2012), Contemporary Abstract Algebra (8-е изд.), Cengage Learning, ISBN 978-1285402734
• Лидл, Рудольф; Niederreiter, Harald (1997), Finite fields (2-е изд.), Cambridge University Press, ISBN 978-0 -521-39231-0, с. 91.
• Мак Лейн, Сондерс ; Биркгоф, Гаррет (1999), Алгебра (3-е изд.), Американское математическое общество, ISBN 9780821816462
• Менезес, Альфред Дж. ; Ван Оршот, Пол К. ; Ванстон, Скотт А. (1997), Справочник по прикладной криптографии, CRC Press, ISBN 978-0-8493 -8523-0, с. 154.

• Вайсштейн, Эрик У. «Неприводимый многочлен». MathWorld.
• Неприводимый многочлен на PlanetMath.org.
• Информация о примитивных и неприводимых многочленах, (комбинаторный) сервер объектов.