Простий многочлен над скінченним полем та поле остач від ділення на цей многочлен

Допоміжні означення для означення поля:

Групоїд — це алгебра типу <2> без тотожностей.

Група (вільна) — це моноїд, в якому .

Кільце — це алгебра (A; +,*), в якій: (A; +) — комутативна група, (A; *) — групоїд, * дистрибутивна відносно +. Кільце називається комутативним, якщо * комутативна; кільцем з одиницею, якщо за * є одиниця; асоціативним, якщо (A; *) — півгрупа. Одиниця за додаванням позначається 0, за множенням (якщо є) — 1.

Тіло — це кільце (A; +,*), в якому (A \{0}; *) — група.

Поле — це тіло з комутативною операцією *, тобто це кільце, в якому (A \{0}; *) — комутативна група.

Означення. Многочлен a (x) над полем F — незвідний, якщо ділиться тільки на f*a (x) та f, де f — ненульовий елемент поля F. Простий многочлен над полем F — це зведений незвідний над F. Елемент f поля F — корінь многочлена a (x), якщо a (f)=0.

Нехай F_q — скінченне поле з q елементів. Многочлен a (x) з F_q [ x ] визначає множину остач F_q [ x ]/ a (x) від ділення на нього. Якщо deg a (x) = m, то кількість остач дорівнює q^m.

Означимо додавання елементів F_q [ x ]/ a (x) як b (x)+ c (x) = R_{a (x )}(b (x)+ c (x)). Оскільки F_q є полем, аналогічно можна означити віднімання та множення: b (x)– c (x)= R_{a (x)}(b (x)– c (x)), b (x)* c (x)= R_{a (x)}(b (x)* c (x)). Неважко переконатися, що F_q [ x ]/ a (x) є кільцем, у якому 0 — многочлен 0, 1 — многочлен 1.

Твердження. F_q [ x ]/ a (x) є полем тоді й тільки тоді, коли a (x) є простим над полем F_q.

Доведення. Необхідність. Припустимо супротивне: нехай F_q [ x ]/ a (x) є полем, але a (x) — не простий над F_q. Нехай a (x)= s (x)* r (x), де deg s (x)>0, deg r (x)>0. Звідси s (x) і r (x) є елементами кільця й є дільниками нуля, а це суперечить тому, що F_q [ x ]/ a (x) є полем.

Достатність. Нехай a (x) є простим над полем F_q. Достатньо довести, що кожен елемент кільця остач має обернений елемент за множенням. Нехай b (x) — довільний елемент кільця остач. Оскільки a (x) — простий над полем, усі остачі від ділення на нього взаємно прості з ним. Тоді за висновком з алгоритму Евкліда існують многочлени над цим полем u (x) та v (x), за яких D (a (x), b (x))= a (x) u (x)+ b (x) v (x). Отже,

1 = R_{a (x)}(a (x) u (x)+ b (x) v (x)) = R_{a (x)}(b (x) v (x)) = R_{a (x)}(b (x) R_{a (x)}(v (x))).

Звідси R_{a (x)}(v (x)) = b ^–1(x).

Висновок. Простий многочлен степеня m над скінченним полем F_q визначає поле остач від ділення на нього, яке має q^m елементів.