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

[EUgeneUS]

del

-- 24.05.2022, 18:13 --

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

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$

Ещё была попытка доказать, что $M(2pq) \le 3$ всегда для $gcd(p-1, q-1) > 2$ всегда (без необходимости конечных переборов).
Но похоже, она прикрылась этим:

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

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

[EUgeneUS]

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

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

Подставим выражение для $a^{q-1}b$ в уравнение $2^{p-2} a^{q-1}b = B^2 -1 $ (1):
$2^{p-2} (2^{p-4} \pm 1) = B^2 -1$

Запишем так:
$2^{p-3} (2^{p-3} \pm 2) = (c^{(p-1)/2} d^{(q-1)/2} -1)(c^{(p-1)/2} d^{(q-1)/2} +1)$

Тогда (с учетом того, что справа и слева произведение последовательных четных чисел).
$2^{p-3} = (c^{(p-1)/2} d^{(q-1)/2} \pm 1)$

Тогда $gcd((p-1)/2, (q-1)/2) >1$ опять запрещается теоремой Михайлэску.

То есть утверждение
$M(2pq) \le 3$ при $gcd((p-1)/2, (q-1)/2) >1$ опять остаётся доказанным без переборов.

[EUgeneUS]

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

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

(иллюстрация на примерах)

1. $p=5, q=7$
Доказано, что $M(2 \cdot 5 \cdot 7) \le 3$
Более того, доказательство, что для проверки $M(2 \cdot p \cdot q) \le 3$ требуется конечное число проверок, распространено на случаи:
$p=5, q=6n+1$

2. $p=5, q=11$
а) $gcd ((5-1)/2, (11-1)/2) = 1$
б) и $ 11 \mod 12 = 11$
Значит
а) $M(2 \cdot 5 \cdot 7) \le 3$ не доказано.
б) более того: конечных проверок, что $M(2 \cdot 5 \cdot 11) \le 3$ (пока) не предъявлено.

3. $p=5, q=13$
а) $gcd ((5-1)/2, (13-1)/2) = 2 > 1$, значит $M(2 \cdot 5 \cdot 13) \le 3$

4. $p=5, q=17$
а) $gcd ((5-1)/2, (17-1)/2) = 2 > 1$, значит $M(2 \cdot 5 \cdot 17) \le 3$

7. $p=5, q=19$
а) $gcd ((5-1)/2, (19-1)/2) = 1$,
б) $19 \mod 6 = 1$
значит требуется конечное число проверок, что $M(2 \cdot 5 \cdot 19) \le 3$

Для $p \geqslant 7$ ещё проще:

8) $p=7, q=11$
$gcd ((7-1)/2, (11-1)/2) = 1$
требуется конечное число проверок, что $M(2 \cdot 7 \cdot 11) \le 3$

9) $p=7, q=13$
$gcd ((7-1)/2, (13-1)/2) = 3$, значит $M(2 \cdot 7 \cdot 13) \le 3$

И т.д.

[mathematician123]

Продолжаю заниматься сокращением перебора.

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

Тогда (с учетом того, что справа и слева произведение последовательных четных чисел).
$2^{p-3} = (c^{(p-1)/2} d^{(q-1)/2} \pm 1)$

Рассмотрим это уравнение подробнее. Если $p < q$, то левая часть уравнения меньше правой. Пусть $p > q$. Тогда, если $c \ge 5$, то левая часть уравнения меньше правой. Поэтому единственная возможность - это $c = 3$. Тогда

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

. Случай с $+1$ невозможен по модулю 3.

-- 24.05.2022, 22:55 --

Лемма. Если $2^x-1$ делится на $3^y$, то $x$ делится на $2 \cdot 3^{y-1}$

Применяя эту лемму получаем, что $p-3$ делится на $2 \cdot 3^{\frac{p-3}{2}}$, что невозможно при достаточно большом $q$.

-- 24.05.2022, 22:59 --

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

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

Здесь я неверно применяю лемму. Правильно так: применяя эту лемму, получаем, что $\frac{q-1}{2}$ делится на $2^{\frac{q-7}{2}}$, что невозможно при достаточно большом $q$.

[Yadryara]

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

Доказано, что $M(2 \cdot 5 \cdot 7) \le 3$

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

Значит
а) $M(2 \cdot 5 \cdot 7) \le 3$ не доказано.

Опять опечатка? Когда же это прекратится-то. И я ведь ещё не на все ошибки указал.

$M(2 \cdot 5 \cdot 11) \leqslant 3$ не доказано ?

$M(2 \cdot 5 \cdot 7) = 3$ доказано ?

[EUgeneUS]

Yadryara

(Оффтоп)

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

Опять опечатка?

Конечно, Вы же видите, к каким $p,q$ относится тот и другой вывод.

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

Когда же это прекратится-то.

Наверное, никогда.

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

И я ведь ещё не на все ошибки указал.

Указывать на опечатки в тексте, который в офф-топике - смысла нет никакого. Этот текст приведен Вам для иллюстрации. Нашли там опечатки - вот и хорошо, разобрались значит.

[EUgeneUS]

Свел случай $p=5, q > 5, gcd(2, (q-1)/2) =1$ к конечному перебору.
В этом случае возможно только $a=11$.
Для этого потребовалось три факта, для которых у меня (пока) нет доказательства :
1. доказательство одного из них точно существует.
2. два других установлены численным моделированием, и скорее всего тоже доказываются.
подробности вечером.

[mathematician123]

Удалось убрать перебор ещё в одном месте. Если всё верно, то $M(2pq) \le 3$ при $p > 5$ и $q > 5$ верно без необходимости какого-либо перебора! Чтобы всё было в одном месте: в сообщениях https://dxdy.ru/post1555331.html#p1555331 и https://dxdy.ru/post1555356.html#p1555356 разбираются два других места с перебором (если кто-то захочет проверить: начинать чтение нужно со второго сообщения, так как там написано об ошибке в первом).

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

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

Вернёмся немного назад к равенству:

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

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

Подставим $a = 3$ и получим

$$(2^{\frac{p-3}{2}} \cdot 3^{\frac{q-1}{2}} + 1)(2^{\frac{p-3}{2}} \cdot 3^{\frac{q-1}{2}} - 1) = c^{\frac{s-1}{2}}d^{\frac{t-1}{2}}$$

Пусть для определённости $q > p$. Так как сомножители в левой части взаимнопросты и отличны от единицы, то один из них равен $d^{\frac{t-1}{2}}$, а второй - $c^{\frac{s-1}{2}}$. Тогда

$$2^{\frac{p-3}{2}} \cdot 3^{\frac{q-1}{2}} \pm 1 = u^{\frac{q-1}{2}}$$

, где $u = c$ или $u = d$ в зависимости от того, какое из этих чисел возводится в степень $\frac{q-1}{2}$ (также будет ещё одно аналогичное уравнение, где $p$ и $q$ переставлены местами). Заметим, что при $u \ge 7$ левая часть меньше правой. Поэтому единственый вариант, который надо рассмотреть - это $u = 5$. Тогда получим четыре уравнения.

$$2^{\frac{p-3}{2}} \cdot 3^{\frac{q-1}{2}} \pm 1 = 5^{\frac{q-1}{2}}$$

$$2^{\frac{q-3}{2}} \cdot 3^{\frac{p-1}{2}} \pm 1 = 5^{\frac{q-1}{2}}$$

Со знаком минус эти уравнения неразрешимы по модулю 8. Со знаком плюс эти уравнения можно решить, применив леммы, аналалогичные леммам из разборов других случаев: чтобы $5^{\frac{q-1}{2}}-1$ делилось на большую степень двойки или тройки, $\frac{q-1}{2}$ должно быть слишком большим, что невозможно.

[EUgeneUS]

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

Пусть для определённости $q > p$

$p$ "прибито гвоздями к двойке. Поэтому нужно рассматривать оба случая: $q< p$ тоже.

[mathematician123]

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

$p$ "прибито гвоздями к двойке. Поэтому нужно рассматривать оба случая: $q< p$ тоже.

Я в скобках дальше написал пояснение.

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

(также будет ещё одно аналогичное уравнение, где $p$ и $q$ переставлены местами)

-- 25.05.2022, 11:43 --

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

Тогда

$$2^{\frac{p-3}{2}} \cdot 3^{\frac{q-1}{2}} \pm 1 = u^{\frac{q-1}{2}}$$

, где $u = c$ или $u = d$ в зависимости от того, какое из этих чисел возводится в степень $\frac{q-1}{2}$

Возможно так будет понятнее: в правой части уравнения берётся $u^{(p-1)/2}$, если $p > q$ и берётся $u^{(q-1)/2}$, если $q > p$. В первом случае рассуждения такие же как и во втором с точностью до замены $p$ и $q$ друг на друга.

[EUgeneUS]

mathematician123
ок, понятно.
Кстати, у меня похоже сложилось доказательство $M(2pq) \le 3$ без переборов для случая $p=5$. Вечером напишу.

[VAL]

Эту тему обнаружил случайно
В "Пентадекатлоне", где она была анонсирована, нет ни ссылки, ни названия, ни даже раздела форума!
Вот я и жду, когда она появится. А она, оказывается уже, есть.

Пока осилил только первый пост.
Но уже в нем есть и опечатки, и какие-то странные выкладки
Правда, насколько я понимаю, это не влияет на окончательный вывод. Но в чем тогда смысл?

[mathematician123]

EUgeneUS
Надеюсь, что Ваше доказательство окажется верным. Я вчера писал, что у меня есть идея для случая $p = 5$, но возникли трудности. Это последний случай который надо рассмотреть для доказательства $M(2pq) \le 3$ для любых различных нечётных простых $p \ge 5$ и $q \ge 5$.

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

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

Возможны случаи $a = q$ или $d = q$.

[EUgeneUS]

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

Надеюсь, что Ваше доказательство окажется верным.

Про отсутствие конечных переборов было излишне оптимистичное заявление.
Там понадобится перебор для исключения $a=3$. Но как понимаю, Вы с таким успешно справляетесь.

-- 25.05.2022, 15:24 --

VAL в сообщении #1555431 писал(а):

Эту тему обнаружил случайно

Вот жеж А я жду и удивляюсь - чего же Вы не приходите...
Приношу извинения за отсутствие анонса.

-- 25.05.2022, 15:25 --

VAL в сообщении #1555431 писал(а):

Пока осилил только первый пост.
Но уже в нем есть и опечатки, и какие-то странные выкладки

Про опечатки - прошу понять и простить. Не смотря на попытки их вычистить, часть осталась
А вот со странными выкладками надо разбираться. Готов отвечать на вопросы.

[Yadryara]

VAL в сообщении #1555431 писал(а):

Эту тему обнаружил случайно
В "Пентадекатлоне", где она была анонсирована, нет ни ссылки, ни названия, ни даже раздела форума!

Ну Вы даёте!! 14-й год на форуме. Неужели Вы не пользуетесь кнопкой "Активные темы" ?

Тема появилась примерно через час после анонса. И я тоже недоумевал почему Вы не комментируете. И ведь ссылку на стартовый пост темы я давал(пост, где про Дзюбанова).

VAL в сообщении #1555431 писал(а):

нет ни ссылки, ни названия, ни даже раздела форума!

Ну так и не нужны ни ссылка, ни название, ни раздел.

"Активные темы" позволяют сразу увидеть то что нужно. В последние годы активность на форуме весьма низка и потому на одной-единственной странице помещаются все-все темы форума, где был хоть один новый пост за последние 5-6 дней, а то и за неделю.

Так что у меня никаких претензий к автору темы в этом аспекте. Ну невозможно её не увидеть.