немного о делителях составных чисел

[GogalNikolay]

$\textbf{Задача.} Рассмотрим числа вида $n = a^2 - d$, где $a \geq 5$ — натуральное число, а $d$ выбирается по правилу: \begin{itemize} \item если $a$ нечётное, то $d \in \{2,6,8,10,12\}$; \item если $a$ чётное, то $d \in \{3,5,7,12,14\}$. \end{itemize} Положим $\tau = a - \sqrt{2a} + 2$, понимая это выражение как $a - (\sqrt{2a}) + 2$ (а не $a - \sqrt{2a+2}$). Докажите или опровергните следующее утверждение: если число $n = a^2 - d$ составное, то: \begin{enumerate} \item у него существует простой делитель $p \leq \tau$; \item не существует простого делителя $q$ такого, что $\tau < q < a$. \end{enumerate} Таким образом, для любого составного $n$ множество его простых делителей не пересекается с интервалом $(\tau, a)$, а наименьший простой делитель не превосходит $\tau$. В случае опровержения достаточно предъявить хотя бы одну пару $(a,d)$, при которой $n$ — составное число, нарушающее одно из этих двух условий (то есть либо все простые делители $n$ строго больше $\tau$, либо у $n$ есть простой делитель в интервале $(\tau,a)$). Для всех проверенных $a \leq 500$ контрпримеров не обнаружено (эмпирическая проверка выполнена скриптом). $

[Dmitriy40]

Фигня Ваш скрипт, контрпримеров полно:

1. $a=9, d=4, n=77, r=6.757 : p=7$ - наименьший простой делитель больше $r$.
Ещё пример, с округлением $r$ в худшую сторону: $a=15, d=4, n=221, r=11.52 : p=13$.

2. $a=6, d=6, n=30, r=4.536 : q=5$ - простой делитель в интервале $r<q<a$.
Ещё пример, с округлением $r$ в худшую сторону: $a=8, d=8, n=56, r=6.000 : q=7$.

-- добавлено через 3 минуты --

GogalNikolay
Не стоит так уж полагаться на вычисления ИИ, они слишком часто ошибаются, и обычно по глупому.
И не нужно убирать весь текст под тег math (его невозможно нормально цитировать), под него нужно только формулы, вот как у меня выше.

[GogalNikolay]

Dmitriy40 в сообщении #1736610 писал(а):

Фигня Ваш скрипт, контрпримеров полно:

где вы у меня 4 видели и 8 при а 8

[Booker48]

Dmitriy40
У ТС в условии очень странные ограничения на $a, d$. )))
Ваши контрпримеры им не удовлетворяют.

[GogalNikolay]

Dmitriy40 в сообщении #1736610 писал(а):

И не нужно убирать весь текст под тег math (его невозможно нормально цитировать), под него нужно только формулы, вот как у меня выше.

Спасибо, я если не вставляю, высвечивается типа ошибка в формулах, буду стараться правильно делать.

[Dmitriy40]

Booker48
Это он поправил на лету, я считал предыдущий/исходный вариант, где на взаимность a и d ограничений не было, только a>4, 1<d<9.

GogalNikolay в сообщении #1736612 писал(а):

где вы у меня 4 видели и 8 при а 8

А нечего было столь кардинально править условия.
Впрочем, контрпримеры всё равно есть:
2. $a=12, d=12, n=132, r=9.101: q=11$.
Ещё:
a=14, d=14
a=76, d=14
a=118, d=14
a=120, d=12
a=170, d=12
a=226, d=14
a=294, d=12
a=366, d=14
a=368, d=12

[GogalNikolay]

Booker48 в сообщении #1736614 писал(а):

Dmitriy40
У ТС в условии очень странные ограничения на $a, d$. )))
Ваши контрпримеры им не удовлетворяют.

Блин, вы правы, там среди чётных ошибка, не 12, 14, а 11, 13, но правка что-то не высвечивается.

-- добавлено через 3 минуты --

Dmitriy40 в сообщении #1736617 писал(а):

Booker48
Это он поправил на лету, я считал предыдущий/исходный вариант, где на взаимность a и d ограничений не было, только a>4, 1<d<9.

GogalNikolay в сообщении #1736612 писал(а):

где вы у меня 4 видели и 8 при а 8

А нечего было столь кардинально править условия.
Впрочем, контрпримеры всё равно есть:
2. $a=12, d=12, n=132, r=9.101: q=11$.

Там ошибка 11 и 13, а не 12 и 14, но править не высвечивается, блин, как вы писали. ИИ попросил оформить формулы, чтобы вставить, и не проверил, просто тупая подстава. Ясно, что при чётном, а вычет только нечётный.

[Dmitriy40]

GogalNikolay в сообщении #1736618 писал(а):

Там ошибка 11 и 13, а не 12 и 14,

С такой правкой контрпримеров не находится вплоть до a<1млн.

Ну теперь желающие могут поупражняться в доказывании ... Я пас.

[Booker48]

Так-то вроде понятно, что контрпример надо искать среди $n = p_1 \cdot p_2$, где $p_1, p_2$ - близкие простые (близнецы, или разность которых равна $4$.
Но ни те, ни другие не могут удовлетворять условию, для таких нельзя подобрать $a, d$, т.к. произведение близнецов отличается от большего квадрата на $1$, а произведение простых, разность которых равна $4$ - и вовсе на $16$, а $ 2 \leqslant d \leqslant 14$

[Dmitriy40]

Booker48 в сообщении #1736620 писал(а):

Так-то вроде понятно, что контрпример надо искать среди $n = p_1 \cdot p_2$, где $p_1, p_2$ - близкие простые (близнецы, или разность которых равна $4$.

Нифига, товарищ заботливо исключил квадратные $d$ из списков, так что $n=p_1 \cdot p_2=a^2-d=(a-\sqrt{d})(a+\sqrt{d})$ не подходят по условию на $d$.

[GogalNikolay]

Dmitriy40 в сообщении #1736621 писал(а):

Нифига, товарищ заботливо исключил квадратные $d$ из списков,

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

[tolstopuz]

Попросил Астру обобщить теорему, чтобы убрать эти списки чисел.

Пусть $n>1$ — нечётное число, $a=\lceil\sqrt n\rceil$, и $a^2-n$ не является квадратом целого числа. Тогда $n$ не имеет делителей в диапазоне $(a+1-\sqrt{(a+1)^2-n},a)$.

[Booker48]

GogalNikolay в сообщении #1736607 писал(а):

Докажите или опровергните следующее утверждение: если число $n = a^2 - d$ составное, то:
у него существует простой делитель $p \leq \tau$;
не существует простого делителя $q$ такого, что $\tau < q < a$.

Кажется, достаточно доказать второе утверждение. И если при этом число $n$ составное (по условию), то получается, что один из его делителей таки меньше $\tau$.
А второе утверждение доказывается тем, что написано выше: искомое $n$ может отличаться от квадрата $a^2$ на $1, 4, 9, 16, ...$, что запрещено условием.
Тогда, правда, не очень понятно, зачем нужно именно такое сложноустроенное $\tau$.

[GogalNikolay]

Booker48 в сообщении #1736624 писал(а):

Тогда, правда, не очень понятно, зачем нужно именно такое сложноустроенное $\tau$.

Теорема доказывается на числах между двумя рядом стоящими квадратами. Чтобы было проще прийти к доказательству, для тех, кто это попробует, там в моих числах прямая подсказка.

[tolstopuz]

Даже еще проще:

Пусть $n=pq>1$ - разложение нечетного числа на множители, $a=\lceil\sqrt n\rceil$, и $a^2-n$ не является квадратом целого числа. Тогда $p+q\ge2a+2$.

Доказательство: $\frac{p+q}2\ge\sqrt{pq}=\sqrt{n}$, а так как оно целое, то и $\ge a$. Но если $p+q=2a$, то $a^2-n=a^2-p(2a-p)=(a-p)^2$.

Если $p<a$, то $p(2a+2-p)\le pq<a^2$, из чего получаем $(a+1-p)^2>2a+1$, то есть $p<a-\sqrt{2a+1}+1$.