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

[Руст]

ddn писал(а):

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

То, что при $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...
Из вашего утверждения следует, что их нет совсем.

Я писал о том, что если $p =\pm 1\mod 8$, то число орбит не меньше 2, даже не считая тривиальную. Поэтому, число орбит равно 2 (т.е. 2 есть образующая мультипликативной группы) может быть только в случае, когда $p=\pm 3 \mod 8$. Вы хотя бы проверили, что все ваши "контрпримеры" действительно относятся к $p=\pm 3\mod 8$, о чём по существу я написал.
По простым числам Мерсена. Если $a=2^p-1$ простое число Мерсена, то образуемая им последовательность есть $(a+1)2^k-1=2^{p+k}-1}$, т.е. простыми могут быть только числа когда p+k соответствует новому простому числу $q=p+k$, которое даёт простое число Мерсена.

[ddn]

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

Я писал о том, что если $p =\pm 1\mod 8$, то число орбит не меньше 2, даже не считая тривиальную. Поэтому, число орбит равно 2 (т.е. 2 есть образующая мультипликативной группы) может быть только в случае, когда $p=\pm 3 \mod 8$. Вы хотя бы проверили, что все ваши "контрпримеры" действительно относятся к $p=\pm 3\mod 8$, о чём по существу я написал.

Это значит я неправильно Вас понял, мне показалось, что утверждение $T_p|(p-1)/2$ Вы относите ко всем простым. Извиняюсь.

Из $p=\pm 3\mod 8$ до трех тысяч $167$ относятся к $T_p=p-1$, но $52$ - раза в три меньше - к $T_p=p-1$ не относятся. Бесконечность простых $T_p=p-1$ очевидна, но не доказана.

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

По простым числам Мерсена. Если $a=2^p-1$ простое число Мерсена, то образуемая им последовательность есть $(a+1)2^k-1=2^{p+k}-1$, т.е. простыми могут быть только числа когда p+k соответствует новому простому числу $q=p+k$, которое даёт простое число Мерсена.

Что то я с дуру стал думать сначала про $a2^k-1=2^{p+k}-2^k-1$. Теперь все понятно. Лишь бесконечность простых Мерсена дает существование хотя бы одной $a$-последовательности типа (3).

Насчет типа (4) и (5).
У меня конечно была идея рассмотреть остатки по нескольким простым $p_i$, и если число элементов в их классах смежности одинаково, можно синхронизировать остатки так, чтобы всегда получалось составное. Это эквивалентно рассмотрению классов смежности составного - произведения этих простых. Я сразу проверил классы смежности по небольшим составным основаниям, но во всех классах (уже разной длины) встречались остатки взаимно простые с основанием, и я бросил. А напрасно. Сейчас понял почему.
У простого только один остаток всегда отвечает составному - нуль. Если имеется период из остатков длины $n$, то необходимо $n$ разных простых $p_i$ с числом элементов в классах смежности равным $n$ (если ослабить требование, и брать простые с числом элементов в классах смежности - делителем $n$, требуемое число простых может быть уменьшено). Значит составное число, равное произведению этих простых, у которого найдется класс смежности (теорема об остатках) с не взаимнопростыми ему остатками, будет очень большим. Тем более, что искомое $n$ и сами простые $p_i$ ($p_i\leqslant 2^n-1$) будут очень большими.
$n$: простые - максимальное число остатков не взаимнопростых со всеми простыми.
2: 3 (2) - 1
3: 5 (3) - 1
4: 3 (2), 7 (4) - 3
5: 31 (5) - 1
6: 3 (2), 5 (3) - 4
7: 127 (7) - 1
8: 3 (2), 7 (4), 17 (8) - 7
9: 5 (3), 73 (9) - 4
10: 3 (2), 31 (5), 11 (10) - 7
11: 23 (11), 89 (11) - 2
12: 3 (2), 5 (3), 7 (4), 13 (12) - 11
13: 8191 (13) - 1
14: 3 (2), 127 (7), 43 (14) - 9
15: 5 (3), 31 (5), 151 (15) - 8
16: 3 (2), 7 (4), 17 (8), 257 (16) - 15
17: 131071 (17) - 1
18: 3 (2), 5 (3), 73 (9), 19 (18) - 14
19: 524287 (19) - 1
20: 3 (2), 7 (4), 31 (5), 11 (10), 41 (20) - 18
21: 5 (3), 127 (7), 337 (21) - 10
22: 3 (2), 23 (11), 89 (11), 683 (22) - 14
23: 47 (23), 178491 (23) - 1
24: 3 (2), 5 (3), 7 (4), 17 (8), 13 (12), 241 (24) - 23
пока не получается найти число доказанное Ризеля

[Руст]

Ваши последовательности можно считать начинающими с чётного $a_0$, тогда они представляются в виде $a_n=a2^n-1$, где $a=a_0+1$ нечётное число.
Очевидно,что $p|a2^k-1$ тогда и только тогда, когда а является некоторой степенью $a=2^{x_p}\mod p$ двойки по модулю p. Обозначим через $T_p$ точный порядок числа 2 по модулю р и через $N(d)$ количество различных простых чисел имеющих точный порядок d для числа 2, т.е. d число простых делителей числа $2^d-1$ или $\Phi_d(2)$ кроме делителей, у которых порядок является собственным делителем d. Тогда покрывая натуральные числа арифметическими прогрессиями, начинающими с $T_p-x_p$ и c шагом $T_p$, получаем такие нечётные а, что все $a2^n-1$ составные. Наиболее простой способ это сделать получается, когда $d=2^m$, Тогда простые имеющие точный порядок $d=2^m$ есть простые делители числа Ферма $F_{m-1}=2^{2^{m-1}+1$. Пусть $p_i$ простой делитель $F_{i-1}$, i=1,...m и $q|F_{m-1}$ другой простой делитель. Тогда можно взять $p_i|a*2^{2^{i-1}}-1$ и $q|a*2^{2^m}-1$ и это даст такое a.
У меня есть подозрение, что можно доказать что для любого нечётного $a>1$ имеется возможность покрытия натуральных чисел больше некоторого, указанными выше арифметическими прогрессиями. Это не удается только при $a=1$, когда все арифметические последовательности начинаются согласованно с 0 ($x_p=0 \ \forall p$). Если это доказать, то получиться, что в (3) может попасть только простые Мерсена.