Задача по теории чисел

[Bober2]

Добрый день, уважаемые участники форума. Нашёл интересную задачу по теории чисел, которую пока не получается решить. Условие приведено ниже.

Верно ли, что для любого натурального $n$: $4n=(p-1)k$, для какого-то простого нечётного $p$ и $k$ не делящегося на $p$?

Я уверен, что решение должно быть каким-то очень простым, но я пока его не могу увидеть. Есть ли у Вас какие-нибудь идеи?

[waxtep]

Выглядит правдоподобно: можно последовательно установить, что $n$, которое могло бы являться контрпримером, должно делиться на простые $3,5,7,11,13,23,29\ldots$ - в общем, на все простые $p$, где $p-1$ содержит в разложении на простые только двойку не более чем в квадрате и ранее установленные нечетные простые делители $n$ в не более чем первой степени. Если $n$ не делится на какое-либо из таких $p$ - его и возьмем для представления в заданном виде. Такая цепочка простых выглядит бесконечной, но легко ли это доказать, - не соображу

-- 24.02.2024, 19:56 --

Хм, то, что соответствующая цепочка простых бесконечна - лишь гипотеза, см. A229289. Значит, простого решения может и не быть

[Bober2]

waxtep в сообщении #1630770 писал(а):

Выглядит правдоподобно: можно последовательно установить, что $n$, которое могло бы являться контрпримером, должно делиться на простые $3,5,7,11,13,23,29\ldots$ - в общем, на все простые $p$, где $p-1$ содержит в разложении на простые только двойку не более чем в квадрате и ранее установленные нечетные простые делители $n$ в не более чем первой степени. Если $n$ не делится на какое-либо из таких $p$ - его и возьмем для представления в заданном виде. Такая цепочка простых выглядит бесконечной, но легко ли это доказать, - не соображу

-- 24.02.2024, 19:56 --

Хм, то, что соответствующая цепочка простых бесконечна - лишь гипотеза, см. A229289. Значит, простого решения может и не быть

Я изначально так и пытался решать, но то, что цепочка бесконечна у меня доказать не получилось. Кстати, в этой задаче важно, что n домножается именно на $4=2^2$. Потому что если брать $2n$, то можно построить контр-пример $n = 3\cdot7\cdot43$

[gris]

Просто для интереса
первое появление простого в качестве решения ( если меньшие простые нешмогли)
(3 - 1) * 2 = 4
(5 - 1) * 3 = 12
(7 - 1) * 10 = 60
(11 - 1) * 42 = 420
(13 - 1) * 385 = 4620
(17 - 1) * 15015 = 240240
(19 - 1) * 10010 = 180180
(23 - 1) * 2730 = 60060
(29 - 1) * 49335 = 1381380
all numbers from 1 to 10000000

[Andrey A]

Рассмотреть случаи $k=n,\ k=2n,$ и что-то останется на десерт.

[Bober2]

У меня была мысль о том, чтобы рассматривать алгебраические кривые вида $y = (x-1)(nx+k)$, и смотреть какие значения эти алгебраические кривые принимают при $x=p$. Но тут вряд ли что-то получится, потому что тут нет однородного уравнения, чтобы появилась какая-то красивая параметризация. Хотя можно попробовать приводить уравнения к каноническому виду и смотреть на соответствующие преобразования плоскости.

-- 24.02.2024, 20:50 --

Bober2 в сообщении #1630777 писал(а):

У меня была мысль о том, чтобы рассматривать алгебраические кривые вида $y = (x-1)(nx+k)$, и смотреть какие значения эти алгебраические кривые принимают при $x=p$. Но тут вряд ли что-то получится, потому что тут нет однородного уравнения, чтобы появилась какая-то красивая параметризация. Хотя можно попробовать приводить уравнения к каноническому виду и смотреть на соответствующие преобразования плоскости.

Или можно эти кривые рассматривать на проективной плоскости

[Bober2]

waxtep в сообщении #1630770 писал(а):

Выглядит правдоподобно: можно последовательно установить, что $n$, которое могло бы являться контрпримером, должно делиться на простые $3,5,7,11,13,23,29\ldots$ - в общем, на все простые $p$, где $p-1$ содержит в разложении на простые только двойку не более чем в квадрате и ранее установленные нечетные простые делители $n$ в не более чем первой степени. Если $n$ не делится на какое-либо из таких $p$ - его и возьмем для представления в заданном виде. Такая цепочка простых выглядит бесконечной, но легко ли это доказать, - не соображу

-- 24.02.2024, 19:56 --

Хм, то, что соответствующая цепочка простых бесконечна - лишь гипотеза, см. A229289. Значит, простого решения может и не быть

Я нашёл статью, в которой доказывается, что простых чисел $p$, таких что $p-1$ свободно от квадратов, бесконечно много. см. [Mirsky] The number of representations of an integer as the sum of a prime and a k -free integer. Это не то, о чём Вы говорите, но можно попробовать доказать, что в той последовательности встретятся все такие выше указанные $p$. Так же в этой статье говорится о плотности таких чисел $p$ в множестве простых чисел. Поэтому можно найти плотность данных простых чисел $p$ в множестве натуральных чисел.

[schmetterling]

waxtep в сообщении #1630770 писал(а):

Хм, то, что соответствующая цепочка простых бесконечна - лишь гипотеза, см. A229289.

А если она конечна, возьмём за $n$ произведение их всех, и получим контрпример: если $p - 1 \mid n$, то $p$ лежит в последовательности и $p \mid n$.

[Bober2]

schmetterling в сообщении #1630808 писал(а):

waxtep в сообщении #1630770 писал(а):

Хм, то, что соответствующая цепочка простых бесконечна - лишь гипотеза, см. A229289.

А если она конечна, возьмём за $n$ произведение их всех, и получим контрпример: если $p - 1 \mid n$, то $p$ лежит в последовательности и $p \mid n$.

Ну да. Собственно, именно так и строится контр-пример для случая $2n$

[druggist]

Bober2 в сообщении #1630766 писал(а):

ерно ли, что для любого натурального $n$: $4n=(p-1)k$, для какого-то простого нечётного $p$ и $k$ не делящегося на $p$?

Не понял, что значит простого нечётного? Может, нечетное относится к $k$, а не к $p$?

[Bober2]

druggist в сообщении #1630830 писал(а):

Bober2 в сообщении #1630766 писал(а):

ерно ли, что для любого натурального $n$: $4n=(p-1)k$, для какого-то простого нечётного $p$ и $k$ не делящегося на $p$?

Не понял, что значит простого нечётного? Может, нечетное относится к $k$, а не к $p$?

Нет, тут имеется ввиду, что простое число $p$ больше $2$. В принципе, про это можно было бы и не говорить, т.к. если $p=2$ то $k=4n$. Следовательно, $k$ делится на $2$

-- 25.02.2024, 10:42 --

druggist в сообщении #1630830 писал(а):

Bober2 в сообщении #1630766 писал(а):

ерно ли, что для любого натурального $n$: $4n=(p-1)k$, для какого-то простого нечётного $p$ и $k$ не делящегося на $p$?

Не понял, что значит простого нечётного? Может, нечетное относится к $k$, а не к $p$?

Если мы требуем нечётности от $k$, то задача имеет отрицательное решение. Т.е. можно привести контр-пример: $n=5$.
Тогда допустимые разложения будут следующими:
$20=(11-1)\cdot2$
$20=(3-1)\cdot10$
Во всех этих случаях $k$ чётно

[Yu_K]

gris в сообщении #1630773 писал(а):

Просто для интереса
первое появление простого в качестве решения ( если меньшие простые нешмогли)
(3 - 1) * 2 = 4
(5 - 1) * 3 = 12
(7 - 1) * 10 = 60
(11 - 1) * 42 = 420
(13 - 1) * 385 = 4620
(17 - 1) * 15015 = 240240
(19 - 1) * 10010 = 180180
(23 - 1) * 2730 = 60060
(29 - 1) * 49335 = 1381380
all numbers from 1 to 10000000

@maxal тут нету такого - можно добавить