Задача по теории чисел

[Noct]

Задача такая. Пусть $p > 3$ - простое, нужно доказать, что если сравнение $x^2 + x + 1 \equiv 0 \pmod{p}$ имеет решение, то $p = 6n + 1$. И вывести отсюда что простых вида $p = 6n + 1$ бесконечно. Проблема у меня уже в первой части.
Я рассуждал так:

$$x^2 + x + 1 \equiv (x+4^{-1})^2 + 3 \cdot 4^{-1} \equiv 0 \pmod{p}$$

$$(x+4^{-1})^2 \equiv -3 \cdot 4^{-1} \pmod{p}$$

Имеет решение, а значит $-3 \cdot 4^{-1}$, есть квадратичный вычет по модулю $p$
Имеем

$$ \left( \frac{-3 \cdot 4^{-1}}{p} \right) = \left( \frac{-1}{p} \right) \left( \frac{3 }{p} \right) \left( \frac{4^{-1}}{p} \right) = 1$$

$$ (-1)^{\frac{p-1}{2}} (-1)^\left \lfloor {\frac{p+1}{6}} \right \rfloor \left( \frac{4^{-1}}{p} \right) = 1$$

Вопрос, что делать с $\left( \frac{4^{-1}}{p} \right)$?

[Noct]

Кажись разобрался $\left( \frac{4^{-1}}{p} \right) = \left( \frac{(2^{-1})^2}{p} \right) = 1 $
Потом получил, что $p$должно удовлетворять любой из следующих 4 систем сравнений

$$\left\{ \begin{array}{rcl} p &=& 4k_1 + 3\\ p &=& 12k_2 + 5\\ \end{array} \right.$$

$$\left\{ \begin{array}{rcl} p &=& 4k_1 + 3\\ p &=& 12k_2 + 7\\ \end{array} \right.$$

$$\left\{ \begin{array}{rcl} p &=& 4k_1 + 1\\ p &=& 12k_2 + 1\\ \end{array} \right.$$

$$\left\{ \begin{array}{rcl} p &=& 4k_1 + 1\\ p &=& 12k_2 + 11\\ \end{array} \right.$$

Решая которые я получил что $p = 12v + 1$ или $p = 12v + 7$.
В любом случаи $p = 12v + 1 = 6(2v) + 1 = 6n+1$ или $p = 12v + 7 = 6(2v+1) + 1 = 6n+1$
Однако как отсюда вывести бесконечность множества простых вида $6n+1$, мне пока не ясно
И можно ли решить первую часть задачи без привлечения символа Лежандра, ибо следующее задание аналогичное, но с многочленом 4 степени

-- 08.07.2017, 14:05 --

А можно вот это предложение $x^2 + x + 1 \equiv 0 \pmod{p}$, перевести на русский как
"Число $x^2 + x + 1$ имеет в своем разложении на простые множителе только $2$, $3$ и простые числа вида $6n+1$". Тогда можно повторить доказательства Евклида
Пусть все простые числа вида $6n+1$ это $p_1, p_2, \dots, p_n$. Тогда обозначим
$N = 2 \cdot 3 \cdot p_1 \cdots p_n$ и рассмотрим $N^2 + N + 1$
Оно не делится на $p_1, p_2, \dots$ а значит делится на еще одно простое такого вида.
А, что делать если многочлен у нас такой
$x^4 + x^3 + x^2 + x + 1 \equiv 0 \pmod{p}$, нужно доказать что такое сравнение может иметь решения лишь для простых вида $5n+1$

[Andrey A]

Хорошо бы для начала показать, что значение функции $x^2+x+1$ есть число вида $m^2+3n^2$ и дать ограничение $p$ $\neq 2\mod3$ вместо $p=1\mod6$ с вытекающими последствиями.
Сравнение $x^2+x+1=0\mod(a^2+3b^2)$ имеет решение $x=\frac{ay+3bz-1}{2}\mod(a^2+3b^2)$, где $y,z$ - корни уравнения $az-by=\pm 1.$

Noct в сообщении #1232195 писал(а):

Однако как отсюда вывести бесконечность множества простых вида $6n+1$, мне пока не ясно

И мне не ясно.

Noct в сообщении #1232195 писал(а):

"Число $x^2 + x + 1$ имеет в своем разложении на простые множителе только $2$, $3$ и простые числа вида $6n+1$".

На счет двойки Вы погорячились.

[Sonic86]

Noct в сообщении #1232179 писал(а):

Пусть $p > 3$ - простое, нужно доказать, что если сравнение $x^2 + x + 1 \equiv 0 \pmod{p}$ имеет решение

Noct в сообщении #1232195 писал(а):

А, что делать если многочлен у нас такой
$x^4 + x^3 + x^2 + x + 1 \equiv 0 \pmod{p}$, нужно доказать что такое сравнение может иметь решения лишь для простых вида $5n+1$

Обе задачи решаются одинаково умножением на некий несложный многочлен, после чего получается сравнение вида $x^r\equiv 1 \pmod p$. Дальше рассматривается мультипликативная группа поля по умножению $\mathbb{Z}_p^\times$, из чего делается нужный вывод. ИМХО, этот способ сильно легче, даже чем квадратичные вычеты (и обобщение очевидно).

Noct в сообщении #1232179 писал(а):

Вопрос, что делать с $\left( \frac{4^{-1}}{p} \right)$?

$\left( \frac{4^{-1}}{p} \right)=\left( \frac{4^{-1}\cdot 4^2}{p} \right)=\left( \frac{4}{p} \right)=1$

[Noct]

Sonic86 в сообщении #1232217 писал(а):

Обе задачи решаются одинаково умножением на некий несложный многочлен, после чего получается сравнение вида $x^r\equiv 1 \pmod p$

Полагаю на $x - 1$. После чего получим $x^r \equiv 1 \pmod{p}$ и $x \ne 1$.
Дальше рассмотрим $\mathbb{Z}^*_p$
$|\mathbb{Z}^*_p| = \varphi(p) = p-1$, и значит по теореме Лагранжа, ($x$ - порождает циклическую подгруппу порядка $r$) $r | p-1$
Значит $p-1 = r \cdot k$, а значит $p= r \cdot k + 1$, $k \in \mathbb{Z}$
Для первой задачи получаем $p= 3 \cdot k + 1$, которое может быть простым только при четном $k$, а значит получаем искомый ответ $p= 6n + 1$
Для многочлена 4 степени аналогично: $p= 5 \cdot k + 1$, которое может быть простым только при четном $k$, и опять получаем $p= 10n + 1$
Отсюда же следует, что в арифметической последовательности вида $N \cdot k + 1$ - бесконечно много простых чисел?

[Sonic86]

Noct в сообщении #1232226 писал(а):

Отсюда же следует, что в арифметической последовательности вида $N \cdot k + 1$ - бесконечно много простых чисел?

Ну именно отсюда конечно не следует. Т.е. если Вы это напишете в общем виде, то получите доказательство только при всех простых $N$, но не для всех $N$.
Но Вы же написали рассуждение:

Noct в сообщении #1232195 писал(а):

Тогда можно повторить доказательства Евклида
Пусть все простые числа вида $6n+1$ это $p_1, p_2, \dots, p_n$. Тогда обозначим
$N = 2 \cdot 3 \cdot p_1 \cdots p_n$ и рассмотрим $N^2 + N + 1$
Оно не делится на $p_1, p_2, \dots$ а значит делится на еще одно простое такого вида.

Вроде как все верно для $N=3;5$.
В самом общем виде Вы можете найти это доказательство в книге Хассе Лекции по теории чисел или просто Теория чисел (забываю уже). Там используются круговые многочлены и доказывается утверждение для простых вида $Nk\pm 1$. Дальше - только теорема Дирихле. Видели наверное.