Найдите все счастливейшие числа

[Ktina]

Натуральное число $n$ называется счастливейшим тогда и только тогда, когда любое простое число даёт при делении на $n$ остаток, равный простому числу или единице.

Найдите все счастливейшие числа и докажите, что других нет.

[waxtep]

Это, видимо, только $4,6,8,12,18,24,30$
Насчет доказательства...вероятным противопоказанием для (составного) числа $n$ быть счастливейщим является существование составного же числа $m<n$, взаимнопростого с $n$. И, достаточно поглядывать только на примориалы (квадрат или большая степень одного из простых множителей только понижают шансы числа быть счастливейшим). А за пределами тридцатки такое всегда будет. Тут еще слелано смелое предположение, что при взаимнопростых $m<n$, всегда найдется какое-нибудь простое вида $k\cdot n+m$; наверное, это можно доказать, но я чего-то туплю

[wrest]

http://oeis.org/A048597

[Someone]

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

Тут еще слелано смелое предположение, что при взаимнопростых $m<n$, всегда найдется какое-нибудь простое вида $k\cdot n+m$; наверное, это можно доказать, но я чего-то туплю

Это теорема Дирихле о простых числах в арифметической прогрессии.

[Ktina]

wrest
А что там делают 1, 2 и 3?

[wrest]

Ktina
Удовлетворяют требованию для всех простых начиная с 5...
Единица за компанию. Не высаживать же на остановке...

В вашем условии меняем "любое простое" на "любое взаимно простое с $n$" и получаем A048597

[waxtep]

Someone в сообщении #1347846 писал(а):

Это теорема Дирихле о простых числах в арифметической прогрессии.

Спасибо! Ее доказательство, похоже, за рамками моего текущего понимания (смотрел в Гельфанд, Линник "Элементарные методы в аналитической теории чисел")