Докажите, что для любого заданного простого

, существуют два целых числа

и

, такие, что сравнение

неразрешимо.
для всех

, количество различных по модулю

пар

, удовлетворяющих условию, равно

.
Доказать можно вручную, только немного длинно получилось.
(уродское доказательство)
Рассматриваем

.

я буду опускать для краткости
При

все многочлены принимают нулевое значение - неприводимых нет.
При

сравнение

разрешимо при любом

при

и только для

значений при

. Значит число неприрводимых многочленов вида

равно

.
При

:

Можно также умножить на

:

. Выберем

, заменим

. Свободный член

. Получим уравнение

. Т.е. неприводимость почти произвольного кубического многочлена свелась к проверке неприводимости многочлена

по модулю

. Причем сразу заметим, что уравнение

имеет ровно

решений при

. Классы решений не пересекаются.

. Многочлен

неприводим

, а число неприводимых многочленов =

.
Число различных значений кубического многочлена

число всех значений

минус число

двоек одинаковых значений

плюс число

троек одинаковых значений

. Кубический многочлен в любом поле не может принимать более трех одинаковых значений, поэтому одинаковые четверки рассматривать не надо.


делим на


,

,
Выделяем полный квадрат (подробности опускаю):

Число решений

легко вычисляется через символы Лежандра (метод подробно изложен в Айрленде, Роузене):

.

.


Для любого условия

, симметричного по всем переменным, имеем


Вычитаем одно уравнение из другого, получаем

. Выражаем

и подставляем:

- получаем то же самое уравнение.



И тогда

.
Число неприводимых многочленов вида

равно

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

равно

Общее количество неприводимых многочленов:

- получаем требуемое.
Но там у меня еще ошибка в расчете

, искать ее сил нет.
С другой стороны, если нормально выучить алгебру, то достаточно знать теорему 3.25. из книги Лидла, Нидеррайтера про конечные поля:
Лидл, Нидеррайтер Конечные поля писал(а):
3.25. Теорема. Число

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

в кольце
![$\mathbb{F}_q[x]$ $\mathbb{F}_q[x]$](https://dxdy-03.korotkov.co.uk/f/e/3/4/e34dcac3847c56655735d90cf1a705ef82.png)
задается формулой:

Т.е. число неприводимых многочленов степени 3 над

равно

. Остается только сделать замену

, от которой многочлен

перейдет в

, причем эта замена преобразует ровно

разных многочленов вида

в один многочлен вида

. В результате число таких неприводимых многочленов будет равно

.
Add 08.03.2018
А вообще все просто: число неприводимых многочленов - это число всех многочленов минус число приводимых. Кубический многочлен приводим

он имеет корень, т.е. имеет вид

или имеет вид

, где

неприводим. Число обеих типов многочленов легко считается, число всех многочленов - тоже. Просто упрощаем многочлен и получаем

.