Антибиективнось

[rightways]

Докажите, что для любого заданного простого $p$, существуют два целых числа $a$ и $b$, такие, что сравнение $x^3+ax+b \equiv 0 \pmod p$ неразрешимо.

[waxtep]

Утверждение: существует не менее $(p-1)$ различных по модулю $p$ пар $(a,b)$, удовлетворяющих условию

[Andrey A]

Удалил.

[Shadow]

Конечно существуют, причем много и не только по простому модулю. Годится любое $a\equiv 2 \pmod 3$
В частности, напр. при $a=-1$, $f(x)=x^3-x\pmod p$ не образует полную группу вычетов, т.к $f(0)=f(1)=f(-1)=0$

[waxtep]

Видимо, для всех $p\neq3$, количество различных по модулю $p$ пар $(a,b)$, удовлетворяющих условию, равно $\frac 1 3 (p^2-1)$. Доказать не возьмусь, результат тупого счета для $p<61$

-- 24.02.2018, 22:28 --

Shadow в сообщении #1294086 писал(а):

Годится любое $a\equiv 2 \pmod 3$

ну да, то есть таких пар, грубо говоря, треть от общего количества

[Sonic86]

rightways в сообщении #1293898 писал(а):

Докажите, что для любого заданного простого $p$, существуют два целых числа $a$ и $b$, такие, что сравнение $x^3+ax+b \equiv 0 \pmod p$ неразрешимо.

waxtep в сообщении #1294208 писал(а):

для всех $p\neq3$, количество различных по модулю $p$ пар $(a,b)$, удовлетворяющих условию, равно $\frac 1 3 (p^2-1)$.

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

(уродское доказательство)

Рассматриваем $p\geqslant 5$. $\pmod p$ я буду опускать для краткости
При $b\equiv 0$ все многочлены принимают нулевое значение - неприводимых нет.
При $a\equiv 0$ сравнение $x^3+b\equiv 0$ разрешимо при любом $b$ при $p\equiv -1\pmod 3$ и только для $\frac{p-1}{3}$ значений при $p\equiv 1\pmod 3$. Значит число неприрводимых многочленов вида $x^3+b$ равно $\frac{1+\left(\frac{p}{3}\right)}{2}\left(p-1-\frac{p-1}{3}\right) = \frac{1+\left(\frac{p}{3}\right)}{3}(p-1)$.
При $a,b\not\equiv 0$:
$x^3+ax+b= 0 \Leftrightarrow bu^3+au^2+1=0\Leftrightarrow u^3+ab^{-1}u^2+b^{-1}=0$
Можно также умножить на $c^3$: $(cu)^3+ab^{-1}c(cu)^2+c^3b^{-1}=0$. Выберем $c=ab^{-1}$, заменим $cu=t$. Свободный член $C=a^3b^{-4}$. Получим уравнение $t^3+t^2+C=0$. Т.е. неприводимость почти произвольного кубического многочлена свелась к проверке неприводимости многочлена $t^3+t^2+C$ по модулю $p$. Причем сразу заметим, что уравнение $C=a^3b^{-4}\pmod p$ имеет ровно $p-1$ решений при $a,b,C\not\equiv 0$. Классы решений не пересекаются.
$f(t):=t^3+t^2$. Многочлен $t^3+t^2+C$ неприводим $\Leftrightarrow -C \not\in \operatorname{Im}f$, а число неприводимых многочленов = $p-|\operatorname{Im}f|$.
Число различных значений кубического многочлена $|\operatorname{Im}f|=$ число всех значений $p$ минус число $N_2$ двоек одинаковых значений $f$ плюс число $N_3$ троек одинаковых значений $f$. Кубический многочлен в любом поле не может принимать более трех одинаковых значений, поэтому одинаковые четверки рассматривать не надо.
$N_2=\frac{1}{2}N(f(x)\equiv f(y), x\not\equiv y)$
$x^3+x^2\equiv y^3+y^2\Leftrightarrow$ делим на $y-x$
$y^2+xy+x^2+x+y\equiv 0$, $g(x,y):=y^2+xy+y^2+x+y$,
Выделяем полный квадрат (подробности опускаю): $g(x,y)\equiv 0\Leftrightarrow 3u^2+v^2\equiv 2$
Число решений $N(3u^2+v^2\equiv 2)$ легко вычисляется через символы Лежандра (метод подробно изложен в Айрленде, Роузене):
$N(3u^2+v^2\equiv 2)=p-\left(\frac{-3}{p}\right)=p-\left(\frac{p}{3}\right)$.
$N(g(x,y)\equiv 0, x\not\equiv y) = N(g(x,y)\equiv 0) - N(3x^2+2x\equiv 0)$.
$N_2=\frac{1}{2}\left(p-\left(\frac{p}{3}\right) - 2\right)$
$N_3=\frac{1}{3!}N(g(x,y)\equiv g(y,z)\equiv g(z,x), x\not\equiv y\not\equiv z\not\equiv x)$
Для любого условия $S=S(x,y,z)$, симметричного по всем переменным, имеем $N(S,x\not\equiv y\not\equiv z\not\equiv x) = N(S) - 3N(S, z\equiv x)+2N(S, x\equiv y\equiv z)$
$N(S)=N(f(y)\equiv f(x), f(z)\equiv f(x)) = N(g(x,y)\equiv 0, g(z,x)\equiv 0)$
Вычитаем одно уравнение из другого, получаем $x+y+z+1\equiv 0$. Выражаем $z$ и подставляем:
$g(x,z)=(z+1)(x+z)+x^2\equiv (-y-x)(-y-1)+x^2=y^2+xy+x^2+x+y$ - получаем то же самое уравнение.
$N(S, z\equiv x) = N(g(x,y)\equiv g(y,z)\equiv g(z,x), z\equiv x)=$ $N(g(x,y)\equiv 0, 3y^2+2y \equiv 0) = 3$
$N(S, x\equiv y\equiv z)=N(3y^2+2y\equiv 0)=2$
$N_3=\frac{1}{6}\left(N(g(x,y)\equiv 0) - 3\cdot 3+2\cdot 2\right)=\frac{p-\left(\frac{p}{3}\right)-5}{6}$
И тогда $|\operatorname{Im}(f)|=p-N_2+N_3=p-\frac{1}{2}\left(p-\left(\frac{p}{3}\right) - 2\right)+\frac{p-\left(\frac{p}{3}\right)-5}{6}=\frac{2p+\left(\frac{p}{3}\right)}{3}$.
Число неприводимых многочленов вида $t^3+t^2+C$ равно $p-\frac{2p+\left(\frac{p}{3}\right)}{3}=\frac{p-\left(\frac{p}{3}\right)}{3}$
Число неприводимых многочленов вида $x^3+ax+b, a,b\not\equiv 0$ равно $(p-1)\frac{p-\left(\frac{p}{3}\right)}{3}$
Общее количество неприводимых многочленов: $(p-1)\frac{p-\left(\frac{p}{3}\right)}{3}+\left(1+\left(\frac{p}{3}\right)\right)\frac{p-1}{3}=\frac{p^2-1}{3}$ - получаем требуемое.
Но там у меня еще ошибка в расчете $N_2$, искать ее сил нет.

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

Лидл, Нидеррайтер Конечные поля писал(а):

3.25. Теорема. Число $N_q(n)$ нормированных неприводимых многочленов степени $n$ в кольце $\mathbb{F}_q[x]$ задается формулой:

$$N_q(n)=\frac{1}{n}\sum\limits_{d|n}\mu(d)q^{n/d}$$

Т.е. число неприводимых многочленов степени 3 над $\mathbb{F}_p$ равно $\frac{p^3-p}{3}$. Остается только сделать замену $x\to x-\frac{a}{3}$, от которой многочлен $x^3+ax^2+bx+c$ перейдет в $x^3+px+q$, причем эта замена преобразует ровно $p$ разных многочленов вида $x^3+ax^2+bx+c$ в один многочлен вида $x^3+px+q$. В результате число таких неприводимых многочленов будет равно $\frac{p^3-p}{3p}=\frac{p^2-1}{3}$.

Add 08.03.2018
А вообще все просто: число неприводимых многочленов - это число всех многочленов минус число приводимых. Кубический многочлен приводим $\Leftrightarrow$ он имеет корень, т.е. имеет вид $(x+a)(x+b)(x+c)$ или имеет вид $(x^2+ax+b)(x+c)$, где $x^2+ax+b$ неприводим. Число обеих типов многочленов легко считается, число всех многочленов - тоже. Просто упрощаем многочлен и получаем $\frac{p^3-p}{3}$.