В поле Галуа первообразным корнем степени n из единицы называется элемент $ \mathfrak a $, который удовлетворяет условиям $$ \mathfrak a^n=\mathfrak e \ , \mathfrak a^k \ne \mathfrak e \quad npu \quad k\in \{1,2,\dots,n-1\} \ . $$ Будем также говорить, что $ \mathfrak a $ принадлежит показателю n.

Теорема 1. В поле Галуа $ \mathbf{GF} (p^m) $ существуют первообразные корни степени $ p^m-1 $ из единицы.

В поле $ \mathbf{GF} (p^m) $ первообразный корень степени $ p^m-1 $ из единицы называется примитивным элементом поля.

Лемма 1. Пусть $ \mathfrak a \in \mathbf{GF} (p^m), \mathfrak a \ne \mathfrak o $ — первообразный корень степени $ n_{} $ из единицы. Тогда $ p^m-1 $ делится на $ n_{} $.

Доказательство. Если $ p^m-1 $ не делится на $ n_{} $, т.е. $$ p^m-1 = nq+ r \quad npu \quad \{r,q\} \subset \mathbb N \quad u \ 0< r< n \ , $$ то одновременно выполняется и $ \mathfrak a^n=\mathfrak e $ и $ \mathfrak a^{p^m-1}=\mathfrak e $ ( обобщенная теорема Ферма ). Тогда $$ \mathfrak a^r=\mathfrak a^{(p^m-1)-nq}=\mathfrak a^{p^m-1} \cdot \left( \mathfrak a^{nq} \right)^{-1} = \mathfrak e \cdot \mathfrak e = \mathfrak e \ , $$ т.е. $ \mathfrak a $ является корнем из единицы степени меньшей $ n_{} $. ♦

Обозначим $ \psi (n) $ — число элементов поля $ \mathbf{GF} (p^m) $, принадлежащих показателю $ n_{} $. Согласно лемме 1, число $ n_{} $ должно быть делителем числа $ p^m-1 $. Кроме того, если $ \{1,d_1,d_2,\dots, p^m-1\} $ — множество всех делителей числа $ p^m-1 $, то $$ \psi (1)+\psi(d_1)+\psi(d_2)+\dots+\psi(p^m-1) = p^m-1 \ , $$ поскольку любой элемент поля принадлежит одному и только одному показателю.

Лемма 2. Если $ \mathfrak a $ принадлежит показателю $ n_{} $ и число $ k_{} $ взаимно просто с $ n_{} $, то и $ \mathfrak a^k $ принадлежит показателю $ n_{} $.

Доказательство. В самом деле, $ \left( \mathfrak a^{k} \right)^n = \left( \mathfrak a^{n} \right)^k = \mathfrak e $. С другой стороны, при $ n_1 < n $ равенство $ \left( \mathfrak a^{k} \right)^{n_1} = \mathfrak e $ невозможно. В самом деле, если оно все же выполнено при $ k_{} $ взаимно простом с $ n_{} $. Тогда, существуют целые числа $ u_{} $ и $ v_{} $, обеспечивающие выполнение равенства $ u\,k+v\, n =1 $. Возведем равенство $ \left( \mathfrak a^{k} \right)^{n_1} = \mathfrak a^{kn_1} = \mathfrak e $ в степень $ u_{} $: $$ \mathfrak e = \mathfrak a^{kun_1} = \mathfrak a^{n_1} \mathfrak a^{n_1(ku-1)} = \mathfrak a^{n_1} \mathfrak a^{-vnn_1} = \mathfrak a^{n_1} \ , $$ т.е. $ \mathfrak a $ является корнем из единицы степени меньшей $ n_{} $. ♦

Итак, при любом $ k<n $ таком, что $ \operatorname{HOD} (k,n)=1 $, элементы $ \mathfrak a^k $ принадлежат показателю $ n_{} $, если $ \mathfrak a $ принадлежит этому показателю. С другой стороны, множество $$ \{ \mathfrak a^k \ \mid \ k\in \{1,\dots,n-1\}, \ \operatorname{HOD} (k,n)=1 \} $$ содержит все элементы, принадлежащие показателю $ n_{} $, поскольку множество $$ \{ \mathfrak a^k \ \mid \ k\in \{0,\dots,n-1\} \} $$ содержит все решения уравнения $ \mathfrak x^n= \mathfrak e $; а при условии $ \operatorname{HOD} (k,n)>1 $ элемент $ \mathfrak a^k $ принадлежит показателю меньшему, чем $ n_{} $ (см. аналогию с первообразными корнями из единицы в поле комплексных чисел ). Число элементов в первом из этих множеств известно — оно равно значению функции Эйлера от числа $ n_{} $, т.е. $ \phi (n) $. Таким образом, для любого числа $ n \in \mathbb N $ будет либо $ \psi(n)=0 $, либо $ \psi(n) = \phi (n) $, т.е., в общем случае, $$ \psi(n) \le \phi(n) \ . $$

Лемма 3. Если $ p^m-1 $ делится на $ n_{} $, то $ \psi (n) = \phi (n) $.

Доказательство. Если $ \{1,d_1,d_2,\dots, p^m-1\} $ — множество всех делителей числа $ p^m-1 $, то, с одной стороны, имеем выведенное выше равенство: $$ \psi (1)+\psi(d_1)+\psi(d_2)+\dots+\psi(p^m-1) = p^m-1 \ ; $$ с другой же стороны, для функции Эйлера справедливо аналогичное равенство $$ \phi (1)+\phi(d_1)+\phi(d_2)+\dots+\phi(p^m-1) = p^m-1 \ . $$ Вычитаем из второго первое: $$ \sum_{d} \left[ \phi (d) - \psi (d) \right] =0 \ , $$ где суммирование идет по всем числам $ d_{} $, являющимися делителями числа $ p^m-1 $. Каждое слагаемое — по неравенству, выведенному выше, — неотрицательно. Следовательно, оно должно равняться нулю. ♦

Доказательство теоремы 1 следует из леммы 3 при $ n=p^m-1 $. Фактически мы получили и точное значение для количества первообразных корней степени $ p^m-1 $ из единицы, т.е. для количества примитивных элементов поля $ \mathbf{GF} (p^m) $ — оно равно $$ \phi (p^m-1) \ . $$ ♦

Как найти примитивный элемент поля?

Воспользуемся аналогией этого объекта с первообразным корнем по модулю простого числа $ p_{} $ из раздела ☞ ИНДЕКС (дискретный логарифм).

Теорема 2. Если каноническое разложение числа $ p^m-1 $ имеет вид:

$$ p^m-1=p_1^{{\mathfrak m}_{_1}}p_2^{{\mathfrak m}_{_2}}\times \dots \times p_{\mathfrak r}^{{\mathfrak m}_{_{\mathfrak r}}} \ , $$ то для того чтобы элемент $ \mathfrak A \in \mathbf{GF} (p^m) $, был примитивным элементом этого поля, необходимо и достаточно, чтобы $$ \mathfrak A^{(p^m-1)/p_j} \not\equiv \mathfrak e \quad npu \quad \forall j\in \{1,\dots, \mathfrak r\} \ . $$

Доказательство аналогично доказательству теоремы 5 из пункта ☞ ПЕРВООБРАЗНЫЙ КОРЕНЬ. ♦

Пример. Будет ли полином $ x^3+x^2 $ примитивным элементом поля $ \mathbf{GF}(16) $, если операция умножения в этом поле определена по двойному модулю $ 2, x^4+x^3+x^2+x+1 $?

Решение. Имеем $ 2^4-1=15=3\cdot 5 $. $$ (x^3+x^2)^{15/3} \equiv_{2} x^{15}+x^{14}+x^{11}+x^{10} \equiv x^3+x^2+1 \not\equiv 1 \quad (\operatorname{modd} \ 2,x^4+x^3+x^2+x+1) ; $$ $$ (x^3+x^2)^{15/5} \equiv_{2} x^9+x^8+x^7+x^6 \equiv 1 \quad (\operatorname{modd} \ 2,x^4+x^3+x^2+x+1) . $$

Ответ. Нет.

Лемма 2 позволяет найти все семейство примитивных элементов поля, если один уже обнаружен.

Теорема 3. Если $ \mathfrak A \in \mathbf{GF} (p^m) $ — примитивный элемент поля, то $ \mathfrak A^k $ будет примитивным элементом поля тогда и только тогда, когда показатель $ k_{} $ взаимно прост с $ p^m-1 $: $ \operatorname{HOD} (k,p^m-1)=1 $.

Пример. Определить все примитивные элементы поля $ \mathbf{GF}(16) $, если операция умножения в этом поле определена по двойному модулю $ 2, x^4+x^3+1 $.

Решение. С помощью теоремы 2 устанавливаем, что полином $ x_{} $ является примитивным элементом поля. Но тогда, в соответствии с теоремой 3, полиномы $$ x^2,x^4,\ x^7\equiv x^2+x+1,\ x^8\equiv x^3+x^2+x,\ x^{11} \equiv x^3+x^2+1,\ x^{13}\equiv x^2+x,\ x^{14}\equiv x^3+x^2 \quad (\operatorname{modd} \ 2,x^4+x^3+1) $$ также должны быть также примитивными элементами поля. Их (вместе с $ x_{} $) как раз $ \phi(15)=8 $ штук, так что больше примитивных корней нет. ♦

Будет ли полином $ x_{} $ примитивным элементом поля $ \mathbf{GF}(2^8) $, если операция умножения в этом поле определена по двойному модулю

a) $ 2, x^8+x^4+x^3+x^2+1 $;

b) $ 2, x^8+x^4+x^3+x+1 $?

Материалы этого пункта взяты (с незначительными модификациями) из
[1]. Чеботарев Н. Основы теории Галуа. Часть I. М.-Л.ОНТИ.1934