M(2pq) <= 3. Доказательство для отдельных случаев

[EUgeneUS]

Тема предназначена для публикации "в одном месте", и дальнейшей проверки доказательства, ранее приведенного (довольно сумбурно) в этой теме. Где-то в районе второй половины 50-х страниц - первой половины 60-х страниц.

Просьба к участникам:
а) пока не окончу набивку - в тему ничего не писать. Чтобы не разбивать публикацию. Сообщу, как закончу.
б) вопросы, не относящиеся к обсуждению приведенного доказательства, в этой теме не поднимать и не обсуждать.
Просьба к модераторам: сообщения из родительской темы сюда не переносить.

-- 23.05.2022, 16:19 --

0. Общие моменты, обозначения и используемые факты.

1. $M(2pq)$ - максимальная длина цепочки, идущих подряд, натуральных чисел, которые имеют ровно $2pq$ делителей.
2. $p, q$ - простые числа в факторизации числа делителей. $p, q \geqslant 5$, $p \ne q$.
3. $s, t$ - могут принимать значения $s=p$, $t=q$; либо $s=q$, $t=p$
4. $a, b, c, d$ - попарно различные простые числа, входящие в факторизацию натуральных чисел с заданным количеством делителей.
5. Обозначение числа в цепочки с одинаковым числом делителей: $n_i$, где $i$ - остаток по модулю $8$.
6. $B = \sqrt{n_2/2}$. Будет показано, что это целое число.
7. Если $M(2pq)=4$, то в цепочку должны входить числа $n_0$ и $n_2$. (Известный доказанный факт)
8. Число $3$ должно входить в факторизацию либо $n_0$, либо $n_2$. Возможно, в первой степени. (Известный доказанный факт)
9. Если $gcd(p-1, q-1) > 4$, то $M(2pq) \le 3$. Факт доказанный в статье Владимира Лецко и Василия Дзюбенко.
10. "Факторизации" - факторизации чисел, входящих в цепочку (если не оговорено иное).
11. "Паттерны" - уравнения, связывающие факторизации $n_0$ и $n_2$ через $n_0 + 2 = n_2$.
12. Если известна факторизация числа делителей, то известны все возможные факторизации чисел, которые имеют ровно такое число делителей. (Общую формулу не привожу, она известна).

-- 23.05.2022, 16:32 --

I. И классификация факторизаций.
Количество делителей вида $k=2pq$ дает 5 факторизаций чисел в цепочке:
1. $a b^{p-1} c^{q-1}$
2. $a b^{pq - 1}$
3. $a^{2pq-1}$
4. $a^{2p-1} b^{p-1}$
5. $a^{2q-1} b^{q-1}$

Это даёт десять мест для размещения двойки, то есть десять вариантов факторизации с двойкой. Часть является эквивалентной, с учетом перестановки $p \leftrightarrow q$.
Выпишем их все, попутно классифицируя.
Теперь $a, b, c ,d$ - различные простые нечётные числа.

1. "Группа для $n_2$".
1.1. $2 c^{p-1} d^{q-1}$
1.2. $2 c^{pq - 1}$

Эти факторизации
а) имеют вид $2B^2$, где $B$ - нечетно, поэтому:
б) могут располагаться в позиции $n_2$ и не могут в позиции $n_6$, так как $2 x^2 \equiv 2 (\mod 8)$
в) обеспечивают, что тройка может быть только в позициях $n_0$ или $n_2$, но не в $n_1$, так как $2 B^2 \equiv {0;2} (\mod 6)$

2. Группа для $n_0$ - большая нечетная степень двойки:
2.1. $2^{2p-1} a^{q-1}$
2.2. $2^{2q-1} a^{p-1}$
2.3. $2^{2pq-1}$

Эти факторизации запрещаются, так как имеют вид $2 x^2$, что приводит в уравнении $n_2 - n_0 = 2$, к тому что, разность квадратов должна быть единицей, что невозможно.

3. Группа для $n_0$ - "экзотичные"
Характеризуются тем, что с большой четной степенью двойки стоит степень только одного простого числа. А также тем (увидим ниже), что если в них и есть решения, то только ограниченное количество.

2.1. $2^{p-1} a^{2q-1}$
2.2. $2^{q-1} a^{2p-1}$
2.3. $2^{pq - 1} a$

4. Группа для $n_0$ - "каноничные"
4.1 $2^{p-1} a^{q-1} b$
4.2 $2^{q-1} a^{p-1} b$

-- 23.05.2022, 16:59 --

II. Исключение "экзотичных" факторизаций

Подробно рассмотрим на таком примере:
$2^{p-1} a^{2q-1} = 2 B^2 - 2$
$2^{p-2} a^{2q-1} = B^2 - 1 = (B-1)(B+1)$

Справа стоят два последовательных четных числа. Значит одно должно иметь остаток $2$ по модулю $4$, а другое должно быть кратно большой степени двойки.
Это можно записать так:
$2^{p-2} a^{2q-1} = (2^{p-3} n) (2^{p-3} n \pm 2)$
И после сокращения на степени двойки:
$a^{2q-1} = n (2^{p-4} n \pm 1)$
Заведомо: $n \geqslant (2^{p-4} n \pm 1)$
Тогда с необходимостью $n=1$, так как $n$ и $(2^{p-4} n \pm 1)$ не имеют общих делителей, больших единицы.
Откуда: $a^{2q-1} = (2^{p-4} n \pm 1)$

а) Для $p > 5$ это запрещено теоремой Михайлэску.
б) $p = 5$ приводит к паре уравнений $a^{2q-1} = (2 \pm 1)$, что заведомо не выполняется.

Таким образом, вариант $n_0 = 2^{p-1} a^{2q-1} = 2 B^2 - 2$ исключен.
Аналогичным образом исключаются другие "экзотичные" варианты факторизации $n_0$.

Note: приём с сокращением степени двойки будет использован ниже. Но там не будет описываться подробно.

[EUgeneUS]

Дополнение.
Теорема Михайлеску также разрешает $p=7$ (что разрешено единственным решением уравнения Каталана).
Тогда:
$a=3$ и $2q-1 = 2$, что также невозможно, в связи с ограничениями наложенными на $q$.

-- 23.05.2022, 17:46 --

III. Рассмотрение "каноничной" факторизации в $n_0$

1. После сокращения на одну двойку уравнение $n_0 = n_2 - 2$ записывается так:
$2^{p-2} a^{q-1}b = B^2 -1 $ (1)

2. Применение приёма с сокращением степени двойки приводит к четырем вариантам уравнения связывающего $b$ и $a^{q-1}$:

III.1: $b = \frac{a^{q-1} + 1}{2^{p-4}}$
Для $p>5$ этот вариант запрещается, так как $a^{q-1} + 1 \equiv 2 (\mod 4)$ и $b$ оказывается дробным числом.
Случай $p = 5$ для этого варианта должен быть рассмотрен отдельно, что будет сделано ниже.

III.2 $b = \frac{a^{q-1} - 1}{2^{p-4}}$

Запишем его так:
$2^{p-4}b = a^{q-1} - 1 = (a^{(q-1)/2} - 1)(a^{(q-1)/2} + 1)$
Тогда $2^{p-4} = (a^{(q-1)/2} \pm 1)$
Случаи $p > 7$, $q > 5$ запрещаются теоремой Михайлэску.
Случай $p = 7$, $q = 5$, согласно теореме Михайлэску, требует $a=3$. И тогда $b = 91$
Это действительно обеспечивает полный квадрат в $B^2 = n_2/2$. Но дальнейшую проверку этот случай не проходит.
Случай $p=q=5$ рассматривать не будем, так как считаем $p,q$ различными.

III.3 $b = 2^{p-4} a^{q-1} + 1$
Проверяем по модулю три:
$2^{p-4} a^{q-1} + 1 \equiv 0 (\mod 3)$, значит $b \equiv 0 (\mod 3)$.
Значит $b=3$, тогда $3 = 2^{p-4} a^{q-1} + 1$, что очевидно не может выполняться для принятых ограничений на $a, p, q$.

III.4 $b = 2^{p-4} a^{q-1} - 1$

а) подставим выражение для $b$ в (1)
$[2^{p-2}a^{q-1}] [2^{p-4} a^{q-1} - 1] = (B+1)(B-1)$

б) Перепишем его так:
$[2^{p-3}a^{q-1}] [2^{p-3} a^{q-1} - 2]= (B+1)(B-1)$

в)Справа в скобках стоят последовательные четные числа, и слева в скобках стоят последовательные четные числа.
А значит большее число слева должно быть равно большему слева (и меньшие тоже).

г)Запишем это в таком варианте:
$[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = B$ (2)

IV. Выводы из $[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = B$

а) $B$ не может быть никакой целой степенью более единицы никакого целого положительного числа.
Это запрещается теоремой Михайлэску.
Отсюда сразу
б) $n_2/2 = c^{pq-1}$ - запрещается.
в) в случае $n_2/2 = c^{s-1}d^{t-1}$:

$[2^{(p-3)/2}a^{(q-1)/2}]^2 - 1 = c^ {(s-1)/2}d^{(t-1)/2}$

Требуется, чтобы: $gcd((q-1)/2, (p-1)/2)=1$. В этом случае:

г) Случай $a=3$ проверяется конечным перебором $c$ и $d$ (с учетом перестановки $p \leftrightarrow q$ слева).
д) После исключения случая $a=3$, одно из чисел $c$ или $d$ должны быть равны $3$ (для определенности считаем, что $d$).

Тогда:
$ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}с^{(t-1)/2}$,
Слева стоит произведение чисел, у которых общий делитель равен единице. Это может быть только в случаях:

$ (2^{(p-3)/2}a^{(q-1)/2} \pm 1) = 3^{(s-1)/2}$

Так как справа стоит ограниченное число (при фиксированных $p, q$), то этот вариант проверяется конечным перебором.

[EUgeneUS]

===
Исправление опечатки выше:

EUgeneUS в сообщении #1555271 писал(а):

$ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}с^{(t-1)/2}$,

читать как $ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}c^{(t-1)/2}$
===
Отметим, что выводы выше справедливы для $p, q > 5$
Случай $p = 5$, $q > p$ должен быть рассмотрен дополнительно (к проверкам и выводам приведенным выше).

V. Случай $p = 5$, $q > p$, $b = \frac{a^{q-1} + 1}{2}$

Отметим, что $p=5$ связано именно со степенью двойки, а не со степенью $a$.

а) подставим выражение для $b$ в паттерн:
$2 a^{q-1} (2 a^{q-1} +2) = (B-1)(B+1)$, откуда:

б) $2 a^{q-1} = B-1$

в) Если $B = C^n$, где $n$ - натуральное число больше единицы, а $C$ - целое нечетное (а оно обязано быть нечётным)
то $B = C^n -1 = (C-1)(C^{n-1}...1)$, где $(C-1)$ обязательно четно.

г) Если $n$ - четно, то и $(C^{n-1}...1)$ - четно, что невозможно.
Это приводит к тому, что случай $gcd((p-1)/2, (q-1)/2) = 2$ невозможен.

д) если $n$ - нечетно. То

д1) либо $(C-1)$ и $(C^{n-1}...1)$ не имеют общих делителей больших $1$.
Тогда $C-1 = 2$. $C=3$
Откуда:
д1.1) Вариант $B = c^2 d^{(q-1)/2}$ невозможен.
д1.2) Вариант $3^n = B = 3^{(pq-1)/2}$, приводит к тому, что $pq = 7$, что несовместимо с наложенными на $p, q$ ограничениями.

д2) либо $gcd((C-1);(C^{n-1}...1)) = 3$,
Здесь достаточно рассмотреть $n=3$, так как в статье Владимира Лецко и Василия Дзюбенко уже доказано, что при $gcd((p-1), (q-1)) > 4$ $M(2qp) \le 3$
тогда $a=3$, так как $a$ - простое.
Тогда $C^2 + C +1$ должно равняться некой степени тройки, что невозможно для целого $C > 1$.

Таким образом вывод:
$M(2qp) \le 3$ при $gcd((p-1), (q-1)) > 2$ остаётся в силе и для этого варианта.

-- 23.05.2022, 18:47 --

VI Случай $p = 5$, $q = 6n +1$, $b = \frac{a^{q-1} + 1}{2}$, в том числе $p = 5, q = 7$

1. Должны быть выполнены проверки, описанные в разделе IV.
2. Должен быть исключён случай (опять же проверками с конечным перебором) $a=3$, для $b = \frac{a^{q-1} + 1}{2}$ (раздел V)
3. После исключения этих случаев, паттерны могут быть записаны так

а)$2 a^6 (2a^6 +2) = 3^6 d^4 -1$
б)$2 a^6 (2a^6 +2) = 3^4 d^6 -1$

С $p=7$ нам так повезло, что для обоих этих уравнений не выполняется сравнение по модулю $27$
(это было проверено в родительской теме уважаемым Dmitriy40.

Таким образом, для $p = 5, q = 7$ было доказано, что $M(2 \cdot 5 \cdot 7) \le 3$
(FGJ, доказано было несколько иначе, но так тоже подойдет , при выполнении всех проверок, описанных выше).

Более того, это можно расширить на все $p = 6n+1$.
У меня нет строго доказательства этого , но выборочная проверка показывает, что такие случаи всё так же будут несовместимы по модулю 27.
Конечно, для каждого такого $q$ должны быть дополнительно выполнены все проверки, описанные выше. Но таких проверок - конечное количество для каждой пары $p=5, q = 6n+1$.

С учетом того, что в случае $gcd((p-1), (q-1)) > 2$ уже доказано, что $M(2pq) \le 3$, то только для $p=5, q = 12n+10$ не имеется конечного набора проверок, что $M(2pq) \le 3$.

-- 23.05.2022, 18:48 --

Вот теперь всё.
Прошу любить и жаловать. А также проверять и критиковать

Большая просьба: если кем-то будет проверена хотя бы часть доказательства - отписаться, даже, если замечаний не найдется.
Спасибо за внимание.

[mathematician123]

EUgeneUS в сообщении #1555278 писал(а):

д2) либо $gcd((C-1);(C^{n-1}...1)) = 3$,

Это верно только для $n = 3$. В общем случае формулировка такая: если $d$ - общий делитель чисел $c-1$ и $\frac{c^n-1}{c-1}$, то $n$ делится на $d$. Но поскольку далее рассматривается только случай $n = 3$, доказательство остаётся верным.

[EUgeneUS]

mathematician123
Спасибо.

И еще одна опечатка:

EUgeneUS в сообщении #1555278 писал(а):

С учетом того, что в случае $gcd((p-1), (q-1)) > 2$ уже доказано, что $M(2pq) \le 3$, то только для $p=5, q = 12n+10$ не имеется конечного набора проверок, что $M(2pq) \le 3$.

Тут правильно:"...для $p=5, q = 12n+11$ .."

-- 23.05.2022, 20:43 --

EUgeneUS в сообщении #1555268 писал(а):

3. Группа для $n_0$ - "экзотичные"
Характеризуются тем, что с большой четной степенью двойки стоит степень только одного простого числа. А также тем (увидим ниже), что если в них и есть решения, то только ограниченное количество

Это устарело. Нет там решений.

[mathematician123]

EUgeneUS в сообщении #1555288 писал(а):

б)$2 a^6 (2a^6 +2) = 3^4 d^6 -1$

Правильно ли я понимаю, что для произвольного $q$ это уравнение записывается так:

$$2 a^{q-1} (2a^{q-1} +2) = 3^4 d^{q-1} -1$$

? Если это верно, то, используя малую теорему Ферма, получаем, что это уравнение не имеет решений по модулю $q$.

[EUgeneUS]

mathematician123 в сообщении #1555289 писал(а):

Правильно ли я понимаю, что для произвольного $q$ это уравнение записывается так:

Да, верно.

mathematician123 в сообщении #1555289 писал(а):

? Если это верно, то, используя малую теорему Ферма, получаем, что это уравнение не имеет решений по модулю $q$.

ЗдОрово!
А второе уравнение (где правая часть другая - степени у 3 и у $d$ переставлены) не исключается?

[lel0lel]

mathematician123 в сообщении #1555289 писал(а):

$$2 a^{q-1} (2a^{q-1} +2) = 3^4 d^{q-1} -1$$

Можно так: замена $t=2a^{q-1}$, ищем дискриминант, он является суммой полного квадрата и ещё чего-то малого, то есть не может являться полным квадратом. Малая теорема Ферма будет не во всех случаях проходить, а это по идее всегда должно работать для подобных уравнений.

[mathematician123]

EUgeneUS в сообщении #1555307 писал(а):

ЗдОрово!
А второе уравнение (где правая часть другая - степени у 3 и у $d$ переставлены) не исключается?

Нет. Второе уравнение разрешимо по модулю $q$. Зато у меня есть идея доказательства конечности решений этого уравнения при фиксированном $q$. Постараюсь сегодня вечером написать об этом.

lel0lel в сообщении #1555312 писал(а):

Малая теорема Ферма будет не во всех случаях проходить, а это по идее всегда должно работать для подобных уравнений.

Доказательство малой теоремой Ферма работает во всех случаях. Просто нужно рассмотреть четыре случая в зависимости от того, делятся ли $a$, $d$ на $q$.

[lel0lel]

Сори, не заметил, что там полный квадрат получается.

[mathematician123]

lel0lel в сообщении #1555312 писал(а):

Можно так: замена $t=2a^{q-1}$, ищем дискриминант, он является суммой полного квадрата и ещё чего-то малого, то есть не может являться полным квадратом.

После этой замены получаем

$$(t+1)^2 = 3^4d^{q-1}$$

. Тогда $t = \pm 9d^{\frac{q-1}{2}} + 1$. То есть, никаких проблем с дискриминантом нет.

[EUgeneUS]

mathematician123 в сообщении #1555316 писал(а):

Просто нужно рассмотреть четыре случая в зависимости от того, делятся ли $a$, $d$ на $q$.

$a, d$ - простые. Так что один случай.

mathematician123 в сообщении #1555318 писал(а):

. Тогда $t = \pm 9d^{\frac{q-1}{2}} + 1$.

причем минус не подходит, так как $t$ - положительное. И единица должна быть с минусом.
то есть: $t = \pm 9d^{\frac{q-1}{2}} - 1 = 9d^{\frac{q-1}{2}} - 1$

[mathematician123]

Доказательство проверил. В целом, считаю его верным. Но есть пара мест, которые надо поправить.

EUgeneUS в сообщении #1555271 писал(а):

III. Рассмотрение "каноничной" факторизации в $n_0$

1. После сокращения на одну двойку уравнение $n_0 = n_2 - 2$ записывается так:
$2^{p-2} a^{q-1}b = B^2 -1 $ (1)

2. Применение приёма с сокращением степени двойки приводит к четырем вариантам уравнения связывающего $b$ и $a^{q-1}$:

У меня получается шесть вариантов, а не четыре. Поэтому рассмотрим это место подробнее.

$$2^{p-2} a^{q-1}b = (B+1)(B-1) $$

Применим приём с сокращением степени двойки. Пусть $B \pm 1 = 2^{p-3}n$. Тогда $ a^{q-1}b = n(2^{p-4}n \pm 1) $. Поскольку $n$ и $2^{p-4}n \pm 1$ взаимнопросты, то возможны четыре случая:
1) $n = b$. Он у Вас рассмотрен.
2) $n = a^{q-1}$. Он у Вас рассмотрен.
3) $n = a^{q-1}b$. Невозможен, так как $2^{p-4}n \pm 1 > n$
4) $n = 1$. А вот разбор этого случая я не нашел. В этом случае $2^{p-4} \pm 1 = a^{q-1}b$. Но этот случай проверяется конечным перебором, поэтому доказательство остаётся верным.

EUgeneUS в сообщении #1555278 писал(а):

V. Случай $p = 5$, $q > p$, $b = \frac{a^{q-1} + 1}{2}$

...

д) если $n$ - нечетно. То

д1) либо $(C-1)$ и $(C^{n-1}...1)$ не имеют общих делителей больших $1$.
Тогда $C-1 = 2$. $C=3$
Откуда:
д1.1) Вариант $B = c^2 d^{(q-1)/2}$ невозможен.
д1.2) Вариант $3^n = B = 3^{(pq-1)/2}$, приводит к тому, что $pq = 7$, что несовместимо с наложенными на $p, q$ ограничениями.

д2) либо $gcd((C-1);(C^{n-1}...1)) = 3$,
Здесь достаточно рассмотреть $n=3$, так как в статье Владимира Лецко и Василия Дзюбенко уже доказано, что при $gcd((p-1), (q-1)) > 4$ $M(2qp) \le 3$
тогда $a=3$, так как $a$ - простое.
Тогда $C^2 + C +1$ должно равняться некой степени тройки, что невозможно для целого $C > 1$.

Поскольку Вы рассматриваете случай $p = 5$, то $gcd((p-1)/2, (q-1)/2) = gcd(2, (q-1)/2)$. Поэтому нужно рассмотреть только случай $n = 2$, а процитированную часть доказательства можно убрать.

[Yadryara]

mathematician123 в сообщении #1555328 писал(а):

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

Скажите пожалуйста без углубления в детали, что именно считаете доказанным?

[mathematician123]

Удалось убрать перебор в одном месте.

EUgeneUS в сообщении #1555271 писал(а):

д) После исключения случая $a=3$, одно из чисел $c$ или $d$ должны быть равны $3$ (для определенности считаем, что $d$).

Тогда:
$ (2^{(p-3)/2}a^{(q-1)/2} - 1) (2^{(p-3)/2}a^{(q-1)/2} + 1) = 3^{(s-1)/2}с^{(t-1)/2}$,
Слева стоит произведение чисел, у которых общий делитель равен единице. Это может быть только в случаях:

$ (2^{(p-3)/2}a^{(q-1)/2} \pm 1) = 3^{(s-1)/2}$

Докажем, что этот случай невозможен (и случай, получающийся перестановкой $p$ и $q$). Поскольку $a > 3$, оценками нетрудно получить, что $s$ - максимальное из чисел $p$ и $q$. Пусть для определённости $q > p$. Тогда

$$2^{(q-3)/2}a^{(p-1)/2} \pm 1 = 3^{(q-1)/2}$$

(второй случай, где $p$ и $q$ слева поменяны местами невозможен, так как тогда левая часть была бы больше правой). Рассмотрим случай со знаком минус.

$$2^{(q-3)/2}a^{(p-1)/2} = 3^{(q-1)/2} + 1$$

Этот случай невозможен при $q>7$, так как $3^{(q-1)/2} + 1$ не может делится на 8. Рассмотрим случай с плюсом.

$$2^{(q-3)/2}a^{(p-1)/2} = 3^{(q-1)/2} - 1$$

Лемма. Если $3^n-1$ делится на $2^m$, то $n$ делится на $2^{m-2}$

Применяя эту лемму, получаем, что $\frac{q-1}{2}$ делится на $\frac{q-3}{2} - 2 = \frac{q-7}{2}$, что невозможно при $q > 13$.

-- 24.05.2022, 16:35 --

Yadryara в сообщении #1555330 писал(а):

Скажите пожалуйста без углубления в детали, что именно считаете доказанным?

1) За исключением конечного перебора, $M(2pq) \le 3$ в случае, когда $p > 5$ и $q > 5$.
2) За исключением конечного перебора, $M(2pq) \le 3$ в случае, когда $p = 5$ и $q$ даёт отличный от 11 остаток от деления на 12.
3) $M(2 \cdot 5 \cdot 7) \le 3$