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

Критерий Эйзенштейна.

Если для многочлена q с целыми коэффициентами q = удается найти такое простое число p, что

1.ОНД( p , ) = 1 2. 3. не делит то этот многочлен неприводим.

Доказательство.

Предположим, что q приводимый многочлен : q = uv. Тогда . По условию теоремы =a, где a 0. Значит, , , где k<n и m<n. Поэтому все коэффициенты многочленов u и v, кроме старших, делятся на p, а тогда свободный член многочлена q, ( то есть ), равный делится на , что противоречит условию.

Примеры.

1. Многочлен неприводим над полем Q. Достаточно взять p = 3 и применить критерий Эйзенштейна.

2. Для всякого n>0 многочлен неприводим над Q. Достаточно взять p=2 в предыдущей теореме. Отсюда вытекает, что над полем рациональных чисел существуют неприводимые многочлены любой степени.

4. Случай конечного поля GF(q).

Особенностью этого случая является тот факт, что имеется только конечное число многочленов данной степени и, в частности, неприводимых многочленов. Будем рассматривать унитарные многочлены степени n над GF(q). Такой многочлен имеет вид: , где , . Значит, количество таких многочленов Обозначим через количество унитарных неприводимых многочленов степени n . Можно указать алгоритм, позволяющий последовательно перечислять все такие многочлены в порядке возрастания их степеней. Для n=1 все многочлены (x - a ) неприводимы, поэтому . Если все неприводимые многочлены степени меньше n уже перечислены, составим всевозможные произведения некоторых степеней таких многочленов, так чтобы эти произведения имели степень n. Все те многочлены степени n, которые не вошли в это множество, и будут неприводимыми многочленами степени n. Разумеется, практическое применение этого алгоритма требует умения совершать арифметические действия в поле GF(q). Кроме того, количество вычислений быстро растет с ростом n (а также q ). В следующей таблице указаны некоторые неприводимые многочлены над полями GF(p) для простых p = 2,3,5.

Можно также указать способ вычисления числа . Обозначим через , набор всех неприводимых унитарных многочленов степени n над полем GF(q), а через , набор всех вообще унитарных многочленов степени n над тем же полем. Рассмотрим следующее выражение:

(Здесь и далее автор использует сокращенные обозначения. Настоятельно советуем читателю для большей наглядности использовать развернутую запись.) F =. Здесь количество слагаемых в каждой скобке и

количество самих скобок выбрано таким образом, чтобы степень каждого многочлена, входящего в F была не выше n. Если раскрыть все скобки то получится сумма всевозможных выражений вида: , где m - степень выписанного многочлена и все . Соберем вместе в сумму все слагаемые с данным значением m. Полученная сумма при mn представляет собой в точности сумму всех вообще унитарных многочленов степени m поскольку каждый такой многочлен однозначно представим в виде произведения неприводимых : . Таким образом, F = + ., где точки отвечают слагаемым, в которых многочлены имеют степень выше n. Положим теперь для всех i и m. Тогда и все , так что получаем: F= = .