Неприводимые многочлены над конечными полями и их число

Определение 1. Многочлен f Î F [ x ] называется нормированным, если старший член многочлена f равен 1.

Определение 2. Многочлен f Î F [ x ] степени большей нуля называется приводимым над полем F, если его можно представить в виде произведения двух многочленов степени > 0 c коэффициентами из поля F.

Определение 3. Многочлен f Î F [ x ] степени большей нуля называется неприводимым над полем F, если его нельзя представить в виде произведения двух многочленов степени > 0 c коэффициентами из поля F.

Обозначим через a_q (n) число нормированных неприводимых многочленов (ННМ) степени n с коэффициентами из поля F_q.

Пример 1. Нормированные многочлены первой степени над Z ₂ есть

x, x +1                                                             (1)

и оба эти многочлена неприводимы над Z ₂. Следовательно,   a ₂(1) = 2.

2. Нормированные многочлены второй степени над Z ₂ есть

x ², x ² + x, x ² +1, x ² + x +1.                                             (2)

Первый, второй и третий многочлены из (2) приводимы над Z ₂, например,       x ² +1 = x ² + 2 x +1  = (x +1)², а последний многочлен не делится ни на один из многочленов (1) и поэтому неприводим над Z ₂. Следовательно,   a ₂(2) = 1.

3. Нормированные многочлены третьей степени над Z ₂ есть

x ³, x ³ + x, x ³ +1, x ³ + x +1, x ³ + x ², x ³ + x ² + x, x ³ + x ² +1, x ³ + x ² + x +1.   (3)

Первый, второй и третий, пятый, шестой, восьмой многочлены из (3) приводимы над Z ₂, четвертый и седьмой последний многочлен не делится ни на один из многочленов (1) и поэтому неприводимы над Z ₂. Следовательно,   a ₂(3) = 2.

Теорема 1. Поле разложения H многочлена

                                                          (4)

над полем F_p есть конечное расширение поля F_p степени n.

Доказательство. Поле H – конечное расширение поля F_p, так как любое конечное поле является конечным расширением любого своего под поля. Пусть [ H, F_p ] = k. Тогда число элементов поля H равно p^k, а другой стороны, поле разложения H многочлена (4) имеет элементов pⁿ. Отсюда p^k  = pⁿ и k = n. ÿ

Теорема 2. Любой неприводимый над полем F_p многочлен f степени n делит многочлен (4).

Доказательство. Утверждение теоремы справедливо при n = 1. Действительно, любой многочлен первой степени ax + b имеет в поле F_p корень     x = - ba ^-1, который по теореме Ферма является корнем многочлена x^p - x и по теореме Безу последний многочлен делится на многочлен ax + b.

Пусть теперь n >1. Пусть f – неприводимый над F_p многочлен и q - его корень, F_p (q) – простое алгебраическое расширение, полученное присоединением к полю F_p  корня q. Поле F_p (q) содержит элементов pⁿ, а его мультипликативная группа состоит из pⁿ -1 элементов. Поэтому q – корень многочлена

                                                          (5)

Так как многочлен f – неприводимый над F_p и имеет общий корень с многочленом (5), то многочлен (5) делится на f. Следовательно, многочлен (4) делится на f. ÿ

Теорема 3. Пусть f неприводимый над полем F_p многочлен степени n. Многочлен f делит многочлен

                                                           (6)

тогда и только тогда, когда n делит m.

Доказательство. Утверждение теоремы справедливо при n = 1. Действительно, любой многочлен первой степени ax + b Î F_p [ x ] делит многочлен x^p - x, а последний многочлен делит многочлен (6), при этом 1 делит m.

Поэтому будем предполагать, что n >1.

Необходимость. Пусть неприводимый над полем F_p многочлен f степени n   делит многочлен (6), и H - поле разложения H многочлена (6), q - его корень многочлена f. Тогда

F_p Í F_p (q) Í H.

По теореме 1, поле H – конечное расширение поля F_p степени m, [ H: F_p ] = m. По теореме о строении простого алгебраического расширения поле F_p (q) - конечное расширение поля F_p степени n, [ F_p (q): F_p ] = m. По теореме о степенях расширений

m = [ H: F_p ] = [ H: F_p (q)]×[ F_p (q): F_p ] = [ H: F_p (q)]× n.

Из этого равенства следует, что n делит m.

Достаточность. Пусть n делит m, т.е. m = nk, где k Î N. Тогда имеем

m ₁ = p^m -1 = p^nk -1 = (pⁿ) ^k -1 ^k = (pⁿ -1)((pⁿ) ^{k - 1} + (pⁿ) ^{k – 2} + …+  1 ^k) = n ₁ k ₁, где k ₁ Î N.

Тогда

 и многочлен (6) делится на многочлен

Так как по теореме 2 последний многочлен делится на многочлен f, то многочлен (6) делится на f. ÿ

Теорема 4. Число нормированных неприводимый над полем F_p многочленов степени n равно

.                                                  (7)

Доказательство. Рассмотрим многочлен

                                                          (8)

Число различных корней многочлена (8) в его поле разложения равно pⁿ. Каждый корень многочлена (8) является корнем некоторого неприводимого над F_p многочлена f  степени m. При этом каждый такой многочлен f имеет m различных корней и по теореме 3 m делит n. Далее каждый неприводимый многочлен f степени m, где m делит n, является делителем многочлена (8) и все его корни являются корнями многочлена (8). Отсюда

.                                                 (9)

Применяя к этому равенству формулу обращения Мебиуса получим формулу (7).

Пример 4.

5. С одной стороны имеем   и по формуле (9)

2⁴ = 1× a ₂(1) + 2× a ₂(2) + 4× a ₂(4) = 1× 2 + 2×1 + 4×3. С другой стороны, многочлен

делится на неприводимй над F ₂ многочлен 2-й степени x ² + x +1 и неприводимые над F ₂ многочлены 4-й степени x ⁴ + x +1 и x ⁴ + x ³+1. Тогда

.

Теорема 5. Для любого простого числа p и для любого натурального числа n существует хотя бы один нормированных неприводимый над полем F_p многочлен степени n равно

. Доказательство. Для n =1 равенство (7) дает

,

поэтому утверждение теоремы верно.

Докажем теорему при n >1. Пусть  - каноническое разложение числа n, тогда все делители m числа n имеют вид:

.

Тогда выводим

Из этой формулы находим, что .ÿ