гипотеза о 3 как примитивном корне

[maxal]

Интересная гипотеза, утверждает, что для простого $p=16q^4+1$, где $q>3$ также является простым, число 3 является примитивным корнем по модулю $p$.
Формулировка кажется простенькой, а как доказать не понятно.

Таких простых, кстати, довольно много и для всех $q<10^9$ гипотеза справедлива.

[Sonic86]

Пытался в лоб по Лемеру:
$g$ - образующая по простому модулю $p$ $\Leftraightarrow (\forall r \in \mathbb{P})r|p-1\Rightarrow g^{\frac{p-1}{r}}\not\equiv 1\pmod p$. У нас $p-1=(2q)^4, r\in\{2,q\}$. Берем, например, $g=3=2+1$ и получаем для $r=2$, что надо доказать, что$\sum\limits_{k=0}^{\frac{p-1}{2}}\binom{\frac{p-1}{2}}{k}2^k \equiv -1\pmod p$. Сумму удается преобразовать до $a_n=\sum\limits_{k=0}^{n}\frac{(-1)^k\binom{2k}{k}}{2^k}$ для $n=\frac{p-1}{2}$, вычислить ее не получилось . ПФ для последовательности $a_n$ равна $\frac{1}{(1-x)\sqrt{1+2x}}$.

ИМХО, гипотеза выглядит неестественно. Критерий Лемера не различает $16q^4+1$ и, например, $4q^2+1$. Почему же такой достаточно сложный вид у многочлена? Хотя для простых Жермен не проходит...

upd: еще можно написать при $p\equiv 1 \pmod p$? что $3^{\frac{p-1}{2}}\equiv\sum\limits_{k=0}^{\frac{p-1}{2}}\binom{2k}{k}\pmod p$. Только сумма тоже не сворачивается...

[maxal]

То, что $3^{\frac{p-1}2}\not\equiv 1\pmod p$ (т.е. 3 является квадратичным невычетом по модулю $p$), легко следует из квадратичного закона взаимности.

[Sonic86]

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

То, что $3^{\frac{p-1}2}\not\equiv 1\pmod p$ (т.е. 3 является квадратичным невычетом по модулю $p$), легко следует из квадратичного закона взаимности.

Да, действительно, переусложнил.

[Sonic86]

Обобщающая гипотеза: для любых натуральных $a,k\geqslant 2$ и простых $q$ если $p=2^aq^k+1$ простое, то $3$ - образующая по модулю $p$.
Проверил для нескольких $a,k$ для $q\leqslant 10^7$.

[Руст]

То, что 3 не является квадратичным вычетом легко проверяется. Вероятность того, что его порядок делится q стремится к нулю как $\frac 1q$, поэтому вполне возможно, что
исключений очень мало или даже конечно.

[Коровьев]

У Виноградова в книге "Основы теории чисел" в главе VI (Вопросы к главе VI, вопрос 5)
даны примеры подобной задачи.
Попробуем применить идею решений и к этой задаче.
Пусть $p$ простое и для некоторого $g$ и делителя $p-1$ выполняется
$$ \[ g^{\frac{{p - 1}}{d}} \equiv 1\left( {\bmod p} \right) \] $
тогда $g$ не первообразный корень.

В нашей задаче все делители $p-1$ суть
$$ \[ {2^k q^t } \to k,t \le 4 \] $
если $g$ не первообразный корень, то для некоторого делителя ${2^k q^t } \to k,t \le 4$
имеем
$$ \[ g^{\frac{{p - 1}}{{2^k q^t }}} \equiv 1\left( {\bmod p} \right) \] $
Отсюда
$$ \[ 1 \equiv \left( {g^{\frac{{p - 1}}{{2^k q^t }}} } \right)^{2^{k - 1} q^t } \equiv g^{\frac{{p - 1}}{2}} \left( {\bmod p} \right) \] $
Следовательно, $g$ есть квадратичный вычет по модулю $p$.

Возьмём простое $3$
$$ \[ \left( {\frac{3}{p}} \right) = \left( {\frac{p}{3}} \right) = \left( {\frac{{16q^4 + 1}}{3}} \right) = \left( {\frac{{\left( { \pm 1} \right)^4 + 1}}{3}} \right) = \left( {\frac{2}{3}} \right) = - 1 \] $
Следовательно $3$ квадратичный невычет, и, если нигде не напорол, является первообразным корнем по модулю
$ \[p = 16q^4 + 1\] $, где $p,q$ простые

[nnosipov]

Коровьев в сообщении #1005463 писал(а):

Следовательно $3$ квадратичный невычет, и, если нигде не напорол, является первообразным корнем по модулю
$ \[p = 16q^4 + 1\] $, где $p,q$ простые

Ну, не всякий же невычет обязан быть первообразным корнем. (А Вы всего лишь показали, что всякий вычет обязан им не быть.)

[whitefox]

nnosipov в сообщении #1005481 писал(а):

Ну, не всякий же невычет обязан быть первообразным корнем.

Имхо, доказано прямо противоположное (если доказано):

Коровьев в сообщении #1005463 писал(а):

если $g$ не первообразный корень, то . . . $g$ есть квадратичный вычет по модулю $p$.

Откуда по правилу контрапозиции следует:
если $g$ квадратичный невычет по модулю $p$, то $g$ первообразный корень по модулю $p$

Но если порядок $g$ кратен 16, то это доказательство не пройдёт.

[nnosipov]

whitefox в сообщении #1005510 писал(а):

Имхо, доказано прямо противоположное (если доказано):

То есть была попытка доказать, что для простых чисел $p$ указанного вида любой квадратичный невычет будет первообразным корнем? Вряд ли это можно доказать: первообразных корней мало ($\varphi(p-1)$ штук), а квадратичных невычетов много ($(p-1)/2$ штук).

Впрочем, такое бывает, но только тогда, когда $p$ --- число Ферма.