2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 гипотеза о 3 как примитивном корне
Сообщение04.03.2012, 09:44 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение04.03.2012, 12:44 
Заслуженный участник


08/04/08
8556
Пытался в лоб по Лемеру:
$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$. Только сумма тоже не сворачивается...

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение04.03.2012, 17:38 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение05.03.2012, 06:25 
Заслуженный участник


08/04/08
8556
maxal в сообщении #545230 писал(а):
То, что $3^{\frac{p-1}2}\not\equiv 1\pmod p$ (т.е. 3 является квадратичным невычетом по модулю $p$), легко следует из квадратичного закона взаимности.
Да, действительно, переусложнил.

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение17.04.2015, 10:24 
Заслуженный участник


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

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение17.04.2015, 13:01 
Заслуженный участник


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

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение19.04.2015, 02:22 
Заслуженный участник
Аватара пользователя


18/12/07
762
У Виноградова в книге "Основы теории чисел" в главе 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$ простые

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение19.04.2015, 07:53 
Заслуженный участник


20/12/10
8858
Коровьев в сообщении #1005463 писал(а):
Следовательно $3$ квадратичный невычет, и, если нигде не напорол, является первообразным корнем по модулю
$  \[p = 16q^4  + 1\]  $, где $p,q$ простые
Ну, не всякий же невычет обязан быть первообразным корнем. (А Вы всего лишь показали, что всякий вычет обязан им не быть.)

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение19.04.2015, 09:32 
Заслуженный участник
Аватара пользователя


19/12/10
1546
nnosipov в сообщении #1005481 писал(а):
Ну, не всякий же невычет обязан быть первообразным корнем.

Имхо, доказано прямо противоположное (если доказано):
Коровьев в сообщении #1005463 писал(а):
если $g$ не первообразный корень, то . . . $g$ есть квадратичный вычет по модулю $p$.
Откуда по правилу контрапозиции следует:
если $g$ квадратичный невычет по модулю $p$, то $g$ первообразный корень по модулю $p$

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

 Профиль  
                  
 
 Re: гипотеза о 3 как примитивном корне
Сообщение19.04.2015, 10:29 
Заслуженный участник


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group