Главная > Математика > Основы компьютерной алгебры с приложениями
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.2.3. Неприводимые сомножители полиномов

Неприводимые полиномы играют ту же роль, что и простые числа в теории разложения на множители целых чисел, поэтому исследуем некоторые их свойства. Мы должны знать, какие полиномы неприводимы в когда ; случай — простое число, будет рассмотрен отдельно в разд. 3.3 и гл. 6. (В гл. 6 мы также исследуем, как вычислять неприводимые сомножители данного полинома с целыми коэффициентами, — весьма нелегкая задача.)

Мы знаем, что поле С было изобретено, чтобы включать корни неприводимых полиномов из мы видели, что — корень полинома . Из следующей теоремы мы заключаем, что единственные отличные от констант неприводимые полиномы в — полиномы степени 1.

Основная теорема алгебры. Каждый полином из степени 1 имеет корень в С.

Доказательство. Имеются различные доказательства этой теоремы, принадлежащие разным знаменитым математикам. Эти доказательства можно найти в большинстве учебников по алгебре [см., например, (Childs, 1979)].

С помощью основной теоремы алгебры мы можем теперь легко определять неприводимые полиномы в Однако отметим, что знание того, какие полиномы в (или в ) неприводимы, не облегчает разложение данного полинома.

Теорема 3.2.7. Отличный от константы полином из неприводим, если и только если либо имеет степень 1, либо

Доказательство. Очевидно, что любой полином степени 1 неприводим.

Предположим теперь, что . Тогда разлагается в на множители:

Мы знаем, что если то корни полинома комплексные, а значит, неприводим в . Таким образом, мы доказали, что два типа полиномов, которые по нашему утверждению неприводимы в действительно неприводимы.

Докажем теперь обратное утверждение теоремы. Предположим, что — неприводимый в полином, Следовательно, нет вещественных корней. Однако по основной теореме алгебры у него есть комплексный корень где — вещественные числа, 60. Образуем теперь полином второй степени где получим , где . Ясно, что — полином степени 1, т.е. . Рассматриваем равенство как равенство функций на С и полагаем Получаем по построению и, значит, Однако, поскольку — не вещественное число, равенство может иметь место, только если а тогда Таким образом, значит, не является неприводимым, если — не константа. Но если — константа, то — неприводимый полином степени 2, что и требовалось доказать.

Сформулируем теперь некоторые результаты, имеющие место для полиномов над полем.

Теорема 3.2.8. Пусть J — поле и . Если неприводимый полином делит произведение , то должен делить или или

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

Умножал на получаем

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

Теорема 3.2.9. (теорема о разложении на простые множители для полиномов). Пусть J — поле и Тогда полином может быть однозначно разложен в произведение неприводимых нормированных полиномов над , т.е. Разложение является единственным с точностью до порядка сомножителей.

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

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

Так же как для целых чисел, мы можем записать разложение на множители полинома в виде

Если какое-либо из чисел - больше единицы, то мы будем говорить, что у полинома есть кратный сомножитель. Например, имеет кратный сомножитель, а таковых не имеет. В первом случае мы говорим, что есть кратный корень в J, а во втором — что имеет только простые корни. Мы видим, таким образом, что разлажение на множители в или в эквивалентно нахождению корней полинома. Имеет место следующая

Теорема 3.2.10. (Гаусс). Пусть J — область целостности и Тогда полином может быть единственным образом разложен в произведение неприводимых: нормированных полиномов над при условии, что каждый элемент в кольце J может быть единственным образом разложен в произведение неразложимых элементов.

Доказательство. Локазательство достаточно длинное, и мы его опускаем; детали см. в книге (Sims, 1984, pp. 229-234).

Следствием теоремы 3.2.10 является тот факт, что — область с однозначным разложением на множители, хотя она не является евклидовой.

В качестве примера области, не являющейся областью с однозначным разложением на множители, рассмотрим область целостности, состоящую из чисел вида - целые числа. (Проверьте, что это действительно область целостности.) Число 21 имеет два разложения на неразложимые множители:

Сформулируем общий результат.

Теорема 3.2.11. Если J — евклидова область, то она является областью с однозначным разложением на множители, т.е. каждый ее отличный от нуля элемент или обратим, или может быть представлен в виде конечного произведения неразложимых элементов.

Доказательство. Локазательство достаточно длинное, и мы его опускаем; детали см. в книге (Sims, 1984, pp. 214-221).

Мы продолжаем обсуждение неприводимых над полиномов.

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

станут понятными ниже). Основной пункт нашего обсуждения состоит в том, что разложение на множители в это то же самое, что разложение на множители в

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

Мы называем полином примитивным, если его коэффициенты — целые числа и их наибольший общий делитель равен 1. Тогда любой полином в с целыми коэффициентами ассоциирован с примитивным полиномом. [Чтобы в этом убедиться, рассмотрим полином с целыми коэффициентами, и пусть d — наибольший общий делитель его коэффициентов. Тогда — все еще полином с целыми коэффициентами, но теперь наибольший общий делитель его коэффициентов — единица. Следовательно, ассоциированы в

Теорема 3.2.12. Произведение двух примитивных полиномов из снова является примитивным полиномом.

Локазательство. Ясно, что произведение двух полиномов с целыми коэффициентами — снова полином с целыми коэффициентами. Пусть — два примитивных полинома. По определению примитивности для любого простого числа

Поэтому

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

Теорема 3.2.13. (Гаусс). Пусть — полином из с целыми коэффициентами. Если , то , где — полиномы с целыми коэффициентами, ассоциированные с соответственно.

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

6, такие, что - примитивные полиномы. По I предыдущей теореме полином примитивен. Но примитивен и и, пользуясь тем, что если г — рациональное число, такое, что — примитивные полиномы, то или —1, получаем Для завершения доказательства положим

Мы говорим, что полином в неприводим, если он не разлагается в произведение двух полиномов степеней 1 с целыми коэффициентами. В силу теоремы 3.2.13 мы видим, что полином неприводим в если и только если он неприводим как полином в Следующая теорема помогает нам в вопросе о неприводимости.

Теорема 3.2.14. Если — полином в

— его корень, такой, что , то

Доказательство. Так как корень полинома то

Умножая на , получаем откуда для некоторого . Следовательно, и поскольку то . Аналогично для некоторого так как , то

Пример. Единственные возможные рациональные корни полинома суть , поскольку они являются единственными делителями числа 8; действительно, два корня суть 2 и 4.

Заметим, что если — корень полинома то линейный сомножитель полинома Полезен следующий критерий для обнаружения неприводимых полиномов в

Теорема 3.2.15. (критерий Эйзенштейна, 1850). Пусть — полином из Если существует простое число , такое, что не делит и делит остальные целые коэффициенты но не делит то полином неприводим.

Доказательство. Будем доказывать от противного. Предположим, что

далее, положим . Тогда, поскольку ровно одно из чисел делится на пусть, например, Кроме того, так как где то однако, поскольку мы будем иметь Таким же образом мы покажем, что делит а также коэффициент а о, который равен 1. Однако это противоречие, и, следовательно, полином неприводим.

Теорема 3.2.15 верна также, когда коэффициенты полинома принадлежат области целостности, которая является областью с однозначным разложением на множители.

Пример. Согласно теореме 3.2.15, полином неприводим при любом .

Теорема 3.2.15 показывает, что в имеются неприводимые полиномы любой степени. Заметим также, что имеются полиномы, к которым критерий Эйзенштейна неприменим; например, для полинома критерий Эйзенштейна абсолютно бесполезен, но тем не менее полином неприводим.

Пример. В полином неприводим. В он имеет корень, а именно 21/3, и

где второй сомножитель имеет два комплексных корня.

Другой тест неприводимости состоит в редукции полинома по модулю , т.е. вычисляем , где m не делит старший коэффициент полинома и проверяем на неприводимость. [Заметим, что Проверка неприводимости полинома — конечная задача (поскольку имеется только конечное число возможных делителей); в гл. 6 мы детально разбираем метод разложения полиномов в конечных полях.

Имеет место следующая

Теорема 3.2.16. Если для некоторого , не делящего старший коэффициент полинома и полином неприводим в , то неприводим в

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

<< Предыдущий параграф Следующий параграф >>
Оглавление