Неприводимость многочлена

[Azkaban]

В общем, есть задача: "Докажите, что многочлен $f(x) = x^{p} - x - 1$ неприводим над $\mathbb{Z}p$ ($p$ - простое число)". У меня появилась идея решить данную задачу с помощью критерия Батлера, который гласит: "Многочлен $f(x) \in \mathbb{Z}p$ неприводим тогда и только тогда, когда $gcd(f(x), f'(x)) = 1$ и уравнение $h^{q} - h = 0$ имеет в факторкольце $\mathbb{R} = \mathbb{Z}p\slash(f(x))$ в точности $q$ решений".

$h = [h(x)]_{f(x)}$, где $h(x) = c_0 + c_1x + ... + c_{n-1}x^{n-1}, n = degf(x)$

Равенство $h^{q} - h = 0$ в кольце $\mathbb{R}$ равносильно сравнению $h(x)^{q} \equiv h(x) \bmod f(x)$, которое преобразуется к виду $0\cdot c_0 + (x^{q} - x)c_1 + (x^{2q} - x^2)c_2 + ... + (x^{(n-1)q} - x^{n-1}) \equiv 0 \bmod f(x) (1)$, поскольку в кольце $\mathbb{Z}p$ справедливо тождество $(c_0 + c_1x + ... + c_{n-1}x^{n-1})^{q} = c_0 + c_1x^{q} + ... + c_{n-1}x^{(n-1)q}$

Ясно, что $gcd(f(x), f'(x)) = 1$. Далее имеем $x^{jp} \equiv (x + 1)^{j} = x^j + jx^{j-1} + ... \bmod f(x)$ для любого $j = 0, 1, ..., p - 1$. А вот что делать дальше я не понимаю. Есть подозрения, что надо каким-то образом представить сравнение (1) и найти $c_{p-1}, ..., c_1$. Но как все-таки доказать неприводимость в итоге? Может кто помочь?

[RIP]

Предположим противное: пусть $f(x)=g(x)h(x)$, где $g(x)$ неприводим, $\deg g(x)<p$. Докажите, что $f(x)$ делится на $g(x)g(x+1)\dotsm g(x+p-1)$.

[RIP]

Впрочем, Ваш метод тоже рабочий. После подстановки $x^{jp}\bmod{f(x)}$ в (1) очевидно получаем $c_{p-1}=0$, $c_{p-2}=0$,…, $c_{1}=0$.

[VladimirKr]

Критерий Батлера представляет практический способ проверки неприводимости со сложностью $O(n^2)$ , что бывает полезно при генерации случайного неприводимого многочлена большой степени $n$.

Цитата:

Есть подозрения, что надо каким-то образом представить сравнение (1) и найти $c_{p-1}, ..., c_0$.

Еще совсем чуть-чуть... В выражении (1) нужно понизить степень до $p-1$, пользуясь равенством $x^{jp} \equiv (x + 1)^{j} = x^j + jx^{j-1} + ... \bmod f(x)$ и собрать коэффициенты при степенях $0,...,p-1$. Каждый коэффициент степени это линейная комбинация $c_i$. Приравняем коэффициенты при степенях к $0$. Осталось показать, что ранг получившейся линейной однородной системы уравнений от $c_0,...,c_{p-1}$ над $\mathbb{Z}p$ равен $p-1$, то есть размерность подпространства решений равна $1$, и, следовательно, количество решений равно $p$

[Azkaban]

$c_1((x + 1) - x) + c_2((x + 1)^{2} - x^{2}) + ... + c_{p - 1}((x + 1)^{p - 1} - x^{p - 1}) = c_1 + c_2(2x + ...) + ... + c_{p - 1}((p - 1)x^{p - 2} + ...) \equiv 0 \bmod f(x)$

Вы имели ввиду вот так? Но я все равно не понимаю, как из этого можно составить матрицу и как в дальнейшем с ней работать

[Azkaban]

Хотя вот еще:
$x^0(c_1 + c_2 + c_3 + ... + (p - 1)c_{p - 1})$;
$x^1(2c_2 + 3c_3 + 4c_4 + ... + (p - 1)c_{p - 2})$;
$x^2(3c_3 + 6c_4 + 10c_5 + ...)$ (тут непонятно для меня, какой будет последний член)

$...$

$x^{p-2}((p - 1)c_{p - 1})$

Матрица, вроде как, тогда будет иметь следующий вид:

$$\begin{equation*} A = \left( \begin{array}{cccc} 0 & 1 & \ldots & p - 1 \\ 0 & 0 & \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \ldots & p-1 \end{array} \right) \end{equation*}$$

Но ведь она уже приведена к ступенчатому виду, и ее ранг виден и так: $(p-1)$

Это сочтется в качестве доказательства?

[VladimirKr]

Ну да.

[Azkaban]

А как тогда RIP получил $c_{p-1}=0$, $c_{p-2}=0$,…, $c_{1}=0$? То есть, если эти коэффициенты равны нулю, то это значит, что это уравнение имеет только тривиальные решения?

[RIP]

Azkaban в сообщении #1596635 писал(а):

А как тогда RIP получил $c_{p-1}=0$, $c_{p-2}=0$,…, $c_{1}=0$?

Посмотрите на коэффициент при $x^{p-2}$. Зная, что $c_{p-1}=0$, посмотрите на коэффициент при $x^{p-3}$. И т.д. Фактически Вам нужно решить однородную систему линейных уравнений с треугольной матрицей.