пары простых чисел с условием p|(2^(q-1)-1), q|(2^(p-1)-1)

[Руст]

Доказать, что существует бесконечно много пар простых чисел $(p,q)$, таких что $p|2^{q-1}-1, \ q|2^{p-1}-1.$

[juna]

Можно переформулировать так: доказать, что существует бесконечно много таких $k$, что $q=4k+1$, $p=8k+1$ - простые.

[maxal]

juna писал(а):

Можно переформулировать так: доказать, что существует бесконечно много таких $k$, что $q=4k+1$, $p=8k+1$ - простые.

Во-первых, "переформулировать" нельзя, так как это неэквивалентная формулировка. Во-вторых, в таком виде это скорее всего открытая проблема (как и родственная ей проблема бесконечности простых Софи Жермен). Исходная задача выглядит более простой.

[juna]

Согласен, что неэквивалентная. Могут существовать другие решения, приведенное лишь одно из многих возможных, позволяющее доказать бесконечность числа решений.
Если бы, конечно, это была не открытая проблема.

[Руст]

maxal писал(а):

Во-первых, "переформулировать" нельзя, так как это неэквивалентная формулировка. Во-вторых, в таком виде это скорее всего открытая проблема (как и родственная ей проблема бесконечности простых Софи Жерман). Исходная задача выглядит более простой.

Да, задача не сложная (на 5 минут размышлений). Отнюдь не открытая проблема. Сегодня кто то из Mathlinks просил меня это решит.

[Kid Kool]

Пусть r - простое, а простые различные p, q - делители $2^r-1$. Тогда p, q - искомые. Осталось понять, почему существует бесконечно много составных чисел вида $2^r-1$, где r - простое.

[maxal]

Kid Kool писал(а):

Пусть r - простое, а простые различные p, q - делители $2^r-1$. Тогда p, q - искомые. Осталось понять, почему существует бесконечно много составных чисел вида $2^r-1$, где r - простое.

Последний вопрос эквивалентен вопросу о бесконечности последовательности A122094 (хех, судя по авторству, я копал че-то похожее пару лет назад, только теперь вот уже не припомню в каком контексте).

[juna]

И что, последний вопрос тоже открыт?

[Руст]

На самом деле надо было сделать только следующий шаг. Kid Kool пытался сделать так, чтобы число 2 имело одинаковые периоды r. Но это не обязательно. Достаточно взять нечётное r>1 и взять $p$ имеющим точный период r, т.е. $p$ простой делитель $\Phi_r(2)$, который равен $2^r-1$, когда r простое и q имеющим точный период 2r, т.е. q простой делитель $\Phi_{2r}(2)$, который равен $\frac{2^r+1}{3}$, когда r простое. Из- за нечётности r, числа p-1 и q-1 делятся на 2r, т.е. $2^{p-1}-1,2^{q-1}-1$ оба делятся на $pq$. Не требуется прибегать к открытым проблемам.

[ddn]

последовательности простых чисел Софи Жерман

Рассмотрим последовательности из нечетных натуральных чисел, вида:
$a_0=4m+1$ ($m\in\mathbb{N}_0$), $a_k=2a_{k-1}+1$ ($k>0$), откуда
$a_k=(a_0+1)2^{k}-1=(2m+1)2^{k+1}-1$ ($k\geqslant 0$)
эта последовательность с непродолжаема в обратную сторону: $a_{-1}=\frac{a_0-1}{2}=2m$ - четное.

Эти последовательности распадаются на пять типов:
1) в которых все числа простые;
2) в которых бесконечное число простых и ненулевое конечное число составных;
3) в которых бесконечное число простых и бесконечное число составных;
4) в которых ненулевое конечное число простых и бесконечное число составных;
5) в которых все числа составные.

Сколько существует последовательностей каждого типа:
нулевое, ненулевое конечное, бесконечное число?

Что можно сказать об этом в свете имеющихся знаний?

Рассмотрим орбиты, которые имеет биективное отображение $i\to (2i+1\ mod\ p)$ на множестве остатков некоторого простого $p>2$. Всегда является орбитой множество $\{p-1\}$.
Гипотеза: все орбиты, кроме $\{p-1\}$, имеют одинаковое число элементов (не меньшее $[\log_2(p+1)]_+$).
Рассмотрим двухорбитные простые числа, то есть у которых только две орбиты: $\{0,1,...,p-2\}$ и $\{p-1\}$
(это простые $p$=3, 5, 11, 13, 19, 29, 37, 53, 61, 67, 83...)
Если таких простых чисел бесконечно много (гипотеза), то всякое нечетное натуральное $b_0=2m+1$ по модулю некоторого достаточного большого двухорбитного простого $p$ не равно $p-1$ и последовательность $b_k=2b_{k-1}+1$ имеет составное среди первых $p-1$ своих членов (с номерами $k=0..p-2$).
Значит последовательностей $\{a_k|_{k\geqslant 0}\}$ типа (1) и (2) не существует.
Последовательности простых чисел Софи Жерман конечны (но неограничены?)

Добавлено спустя 8 минут 22 секунды:

Числа Решеля: нечетные натуральные $b_0=2m+1$, дающие последовательности $\{b_k|_{k\geqslant 1}\}$ типа (5) - их бесконечно много http://mathworld.wolfram.com/RieselNumber.html (не сводится ли это утверждение к тривиальным подпоследовательностям?).

Теорема: последовательностей $\{a_k|_{k\geqslant 0}\}$ типа (4) бесконечно много.
Например, для $m=63650$ все числа $a_k=(2m+1)2^{k+1}-1$ ($k\geqslant 0$) составные, кроме $a_1=509203$
($509203$ - кандидат в наименьшие числа Решеля).

Предположение такое:
1) нуль;
2) нуль;
3) бесконечно;
4) бесконечно;
5) бесконечно;

[Руст]

Все ваши утверждения тривиальны кроме 3), т.е. сущесвования такого нечётного a, что в последовательности $a*2^k-1$ бесконечно много простых, при $a=2^m-1$ это эквивалентно бесконечности простых чисел Мерсена. Эта гипотеза до сих пор не доказана.

[maxal]

ddn писал(а):

простые числа Софи Жерман

Рассмотрим последовательности из нечетных натуральных чисел, вида:
$a_0=4m+1$ ($m\in\mathbb{N}_0$), $a_k=2a_{k-1}+1$ ($k>0$), откуда
$a_k=(a_0+1)2^{k}-1=(2m+1)2^{k+1}-1$ ($k\geqslant 0$)
эта последовательность с непродолжаема в обратную сторону: $a_{-1}=\frac{a_0-1}{2}=2m$ - четное.

Эти последовательности распадаются на пять типов:
1) в которых все числа простые;
2) в которых бесконечное число простых и ненулевое конечное число составных;
3) в которых бесконечное число простых и бесконечное число составных;
4) в которых ненулевое конечное число простых и бесконечное число составных;
5) в которых все числа составные.

Сколько существует последовательностей каждого типа:
нулевое, ненулевое конечное, бесконечное число?

1) и 2) таких не существует
3) такие, вероятно, есть, но доказать проблематично
4) сходу затрудняюсь ответить
5) такие есть - см. числа Ризеля

Добавлено спустя 12 минут 17 секунд:

ddn писал(а):

Числа Решеля:

Традиционно эта фамилия переводится как Ризель, и числа соответственно Ризеля.

[ddn]

Руст писал(а):

Все ваши утверждения тривиальны кроме 3), т.е. существования такого нечётного $a$, что в последовательности $a*2^k-1$ бесконечно много простых, при $a=2^m-1$ это эквивалентно бесконечности простых чисел Мерсена. Эта гипотеза до сих пор не доказана.

Тривиальны?!!

(1) и (2).
Значит, говорите, двухорбитных простых (как их правильно называть?) бесконечно много?
Заметил, что все двухорбитные простые имеют вид $p=8m+3$ и $p=8m+5$ (эквивалентно $p^2=16m+9$ - простые, имеющие $2$-ку квадратичным невычетом) - по известной нетривиальной теореме простых $p=8m+3$ и $p=8m+5$ бесконечно, но не каждое простое из этих арифметических прогрессий двухорбитно, например: $p$=43,109,157,229,251,277,283,307,331,397,499… С классом простых, имеющих $2$-ку своим квадратичным невычетом двухорбитные простые значит не совпадают – и кто может доказать что их тоже бесконечно?
А может, вы можете доказать, что последовательностей $\{a_k|_{k\geqslant 0}\}$ типа (1) и (2) не существует, не обращаясь к двухорбитным простым?

(3).
В каком смысле? Последовательность $\{p2^k-1|_{k\geqslant 1}\}$ содержит бесконечно много простых, если $p$ - простое Мерсена? Тогда существование чисел Мерсена, доказывает , что последовательностей $\{a_k|_{k\geqslant 0}\}$ типа (3) существует по крайней мере ненулевое конечное число. И бесконечное количество, если чисел Мерсена бесконечно.
Или ваше утверждение более слабое: существует некоторое натуральное $m$, что последовательность $\{(2^m-1)2^k-1|_{k\geqslant 1}\}$ содержит бесконечно много простых, если существует бесконечно много простых Мерсена?

maxal писал(а):

3) такие, вероятно, есть, но доказать проблематично

Вероятность члена последовательности $a_n$ быть простым порядка $~\frac{1}{n}$, значит по причине логарифмической расходимости, если тип (1) и (2) не существует, то последовательностей типа (3) - основная масса (тип (4) и (5) имеют меру нуль).

maxal писал(а):

4) сходу затрудняюсь ответить
5) такие есть - см. числа Ризеля

(4) и (5).
Кажется Вы, Руст, упустили одну деталь. У меня последовательности $\{a_k|_{k\geqslant 0}\}$ нечетных натуральных начинаются с нечетного $a_0=4m+1$. А начинающиеся просто с любого нечетного (как для чисел Ризеля) у меня обозначаются $\{b_k|_{k\geqslant 1}\}$.
Под числами Ризеля будем понимать только непродолжаемые: нечетные вида $4m+1$ либо простые – ибо если число Ризеля составное вида $4m+3=2(2m+1)+1$, то $2m+1$ тоже число Ризеля.
Тривиально ли доказательство, что данное нечетное натуральное является числом Ризеля?

Если числа Ризеля существуют, то их последовательности $\{b_k|_{k\geqslant 1}\}$ не содержат простых и относятся к типу (5). Но если их начало продолжаемо до начала вида $a_0=b_{-n}=4m+1$ ($n\geqslant 0$), то в полученной последовательности $\{a_k|_{k\geqslant 0}\}$ могут появится простые и последовательность получит тип (4).
Существование чисел Ризеля, таким образом, говорит о существовании последовательностей типа (4) или (5).
Чтобы существовали последовательностей именно типа (4), необходимо существование простых чисел Ризеля; чтобы именно типа (4) - существование составных чисел Ризеля вида $a_0=4m+1$.
Чтобы последовательностей типа (4) и (5) было бесконечно, необходима бесконечность чисел Ризеля двух указанных классов.
Тривиально ли доказательство бесконечности чисел Ризеля, бесконечности указанных классов чисел Ризеля?

maxal писал(а):

ddn писал(а):

Числа Решеля:

Традиционно эта фамилия переводится как Ризель, и числа соответственно Ризеля.

Спасибо за уточнение.

[Руст]

Да, все ваши гипотезы за исключением указанного тривиальны. Если 4 и 5 не тривиальны уж точно легко доказуемы, идея доказательства появляется в голове в первую же секунду (просто несколько расписать лень). То, что вы называете орбитами добавив к ним 1 (каждому элементу) превратятся в смежные классы по мультипликативной подгруппе, порождённым 2, т.е. щни являются множествами $a*2^k\mod p$. Одноэлементная орбита соответствует а=0. Количество орбит есть $\frac{p-1}{T_p}$, где $T_p$ количество элементов в подгруппе образованной 2 или минимальное натуральное число, для которого $p|2^{T_p}-1$. То, что при $p=\pm 1\mod 8$ число 2 является квадратичным вычетом было известно ещё Эйлеру, а следовательно $T_p$ является делителем $(p-1)/2$, т.е. число орбит больше 1 даже не считая вашу "одноэлементную" как видите так же тривиальна.

[ddn]

Руст писал(а):

Если 4 и 5 не тривиальны уж точно легко доказуемы, идея доказательства появляется в голове в первую же секунду (просто несколько расписать лень).

Попробую помедитировать. Хотя я в теории чисел совершенный любитель.

Руст писал(а):

То, что вы называете орбитами добавив к ним 1 (каждому элементу) превратятся в смежные классы по мультипликативной подгруппе, порождённым 2, т.е. щни являются множествами $a*2^k\mod p$. Одноэлементная орбита соответствует а=0. Количество орбит есть $\frac{p-1}{T_p}$, где $T_p$ количество элементов в подгруппе образованной 2 или минимальное натуральное число, для которого $p|2^{T_p}-1$.

Так, здесь я понял.
Простым числам с одним нетривиальным смежным классом соответствует $T_p=p-1$.

Руст писал(а):

То, что при $p=\pm 1\mod 8$ число 2 является квадратичным вычетом было известно ещё Эйлеру

Книжку про вычеты я читал очень давно, поэтому не сразу обратил внимание.
$p=\pm 1\mod 8$ эквивалентно $p^2=1 \mod 16$.
Сам вычет $(\frac{2}{p})=(-1)^{\frac{p^2-1}{8}}$

Руст писал(а):

а следовательно $T_p$ является делителем $(p-1)/2$, т.е. число орбит больше 1 даже не считая вашу "одноэлементную" как видите так же тривиальна.

Вот в это не верю! Откуда? Я проверял на компьютере. Простые числа с $T_p=p-1$ существуют!
Это $p$=3, 5, 11, 13, 19, 29, 37, 53, 61, 67, 83...
Из вашего утверждения следует, что их нет совсем.
Помоему, Вы перепутали, должно быть: $2^{(p-1)/2}=\pm 1\mod p$, для $p=\pm 1\mod 8$ действительно $2^{(p-1)/2}=1 \mod p$ и тогда $T_p|(p-1)/2$, но для $p=\pm 3\mod 8$ будет $2^{(p-1)/2}=-1 \mod p$ и это может быть не так!

Руст писал(а):

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

Вы сосредоточились почему-то на двух моих гипотезах: равенстве смежных классов - вообще побочный вопрос, и числе простых с $T_p=p-1$ - опровергается вами тривиально (но ошибочно).
Но в случае отрицательного решения (простых с $T_p=p-1$ конечное число) мы ничего не можем сказать о существовании типов (1) и (2) на этом основании.
В случае положительного решения (простых с $T_p=p-1$ бесконечное число), эта гипотеза мне не кажется простодоказуемой. Класс простых с $T_p=p-1$ есть только собственное подмножество бесконечного класса простых вида $p=\pm 3\mod 8$ и о его бесконечности сходу ничего сказать нельзя.
Впрочем, вы могли опираться на какие-то более сильные выкладки.

Да, и уточните пожалуйста формулировку вашего замечания по простым числам Мерсена и ее связи с проблемой (3).


Я для проформы спрашивал еще о неограниченности числа идущих подряд простых:
(2), 5, 11, 23, 47
89, 179, 359, 719, 1439, 2879
1122659, 2245319, 4490639, 8981279, 17962559, 35925119, 71850239
...
но это, конечно, открытая проблема.