Простые p: x^3-3x+1 = 0 (mod p)

[Sonic86]

Существует ли бесконечно много простых $p: x^3-3x+1 \equiv 0 \pmod p$?

[maxal]

Как это понимать? Что здесь $x$?

[frankusef]

Sonic86
Я думаю, Вы имели в виду простые числа вида $x^3-3x+1$, да?

[12d3]

maxal в сообщении #296119 писал(а):

Как это понимать? Что здесь $x$?

наверно $x \in \mathbb{N}$

[Sonic86]

Блин, опять неправильно написал!
$p: (\forall x) x^3-3x+1 \not \equiv 0 \pmod p$
Ну или

12d3 писал(а):

наверно $x \in \mathbb{N}$

[maxal]

Похоже, что ответом являются все простые $p>3$, $p\not\equiv \pm 1\pmod{18}$

[Sonic86]

Ого! Такой простой ответ. Наверное для $p \equiv \pm 1 \pmod {18}$ как-то просто доказывается, что корни есть. Надо подумать...

[maxal]

Интересно, что из результата задачи 2.12 (стр. 89) в книге Прасолова "Многочлены" следует, что многочлен $x^3-3x+1$ либо неприводим над $\mathbb{Z}_p$, либо раскладывается на линейные множители. Вариант разложения в произведение неприводимых многочленов степеней 1 и 2 невозможен.

[Sonic86]

По формуле Кардано один корень уравнения $x = \sqrt[3]{-\frac{1}{2}+\frac{\sqrt{-3}}{2}} + \sqrt[3]{-\frac{1}{2}-\frac{\sqrt{-3}}{2}}$.
При $p=18k-1$ символ Лежандра $\left \frac{-3}{p} \right = -1$, поэтому $\sqrt{-3} = i \sqrt{3}$ и тогда корень уравнения равен сумме сопряженных чисел (кубический корень биективен при $p \neq 18k-1$), а значит лежит в $\mathbb{Z}_p$.
При $p=18k+1$ символ Лежандра $\left \frac{-3}{p} \right = 1$, поэтому квадратный корень извлекается. Далее, $-\frac{1}{2}-\frac{\sqrt{-3}}{2}} = \left -\frac{1}{2}+\frac{\sqrt{-3}}{2}}\right^2$ и оба числа - кубические корни из 1. Они есть поскольку $3|p-1$. Но так как $9|p-1$ то из них самих еще раз извлекается кубический корень. А значит в формуле $x=\sqrt[3]{a}+\sqrt[3]{b}$ оба корня лежат в $\mathbb{Z}_p$, и значит $x \in \mathbb{Z}_p$.
Теперь ссылаемся на Прасолова. Поэтому при $p = 18k \pm 1$ корни есть.
Осталось доказать, что в других случаях корней нету. И мне не нравится использование формулы Кардано, и вообще я какой-то простой многочлен взял, раз получились кубические корни из единицы. Надо другой взять.

[Sonic86]

(Оффтоп)

Я наврал про биективность кубического корня, а никто и не заметил а заодно неверна формула $\sqrt{-3}=i\sqrt{3}$

Корень уравнения $x = \sqrt[3]{\omega} +\sqrt[3]{\omega ^2}$, где $\omega : \omega ^2 + \omega + 1 = 0$.Обозначим также $\sqrt[3]{\omega} = \tau$, так что $x=\tau + \tau ^2$
$p \mod 18 = 1;5;7;11;13;17$. Символ Лежандра $\left( \frac{-3}{p} \right) = \left( \frac{p}{3} \right)$. Поэтому всего 2 варианта:
1. $p \mod 18= 1;7;13$ - корень из $-3$ извлекается ($\omega \in \mathbb{Z}_p$), но $\sqrt[3]{}$ не биективен на $\mathbb{Z}_p$.
2. $p \mod 18 = 5;11;17$ - корень из $-3$ не извлекается ($\omega \not \in \mathbb{Z}_p$), но $\sqrt[3]{}$ биективен на $\mathbb{Z}_p$.
Разберем случай 1. При $p \mod 18 = 1$ корень кубический извлекается из $\omega$ в $\mathbb{Z}_p$, поэтому $x \in \mathbb{Z}_p$. При $\omega \not \in \mathbb{Z}_p$ $x \in \mathbb{Z}_p[\tau]$. Неприводимый многочлен для $\tau$ есть $t^3 - \omega$. Предположим, что $x \in \mathbb{Z}_p$. Тогда $t^2-t-x|t^3 - \omega$, что противоречит неприводимости $t^3 - \omega$. Противоречие. Значит при $p \mod 18 = 7;13$ уже $(\forall x)x^3-3x+1 \not \equiv 0 \pmod p$.
В случае 2 $\omega \not \in \mathbb{Z}_p$. Ясно, что $x \in \mathbb{Z}_p \Leftrightarrow \tau \in \mathbb{Z}_p[\omega]$. Поскольку группа $\mathbb{Z}_p[\omega]$ циклична как мультипликативная группа конечного поля, и ее мощность $p^2-1$, то $\tau \in \mathbb{Z}_p[\omega] \Leftrightarrow \omega^{\frac{p^2-1}{3}}=1$. При $p \mod 18 = -1$ будет $3|\frac{p^2-1}{3}$, а при $p \mod 18 = 5;11$ - нет. Соответственно, при $p \mod 18 = -1$ уравнение $x^3-3x+1 = 0 \pmod p$ имеет решения, а при $p \mod 18 = 5; 11$ - не имеет.