Простые числа определённого вида

[RIP]

Докажите или опровергните:
Для любого нечетного $k$ найдется натуральное $n$ такое, что число $2^nk+1$ простое.

[maxal]

Неверно. Опровержением являются т.н. числа Серпинского. Например, $k=78557.$ Чтобы это проверить, достаточно рассмотреть остатки от деления $2^n\cdot k+1$ на простые 3, 5, 7, 13, 19, 37 и 73. Для каждого $n$ обязательно найдется хотя бы один делитель из этого списка.

На данный момент неизвестно является ли число $78557$ наименьшим числом Серпинского, решением этой проблемы занимается проект Seventeen or Bust.

[RIP]

Эту задачу можно решить вообще без вычислений.

[maxal]

Какую задачу?

[RIP]

Ту, которую я запостил, конечно.

[neo66]

RIP писал(а):

Эту задачу можно решить вообще без вычислений.

Если вы имеете в виду доказательство самого Серпинского теоремы о существовании бесконечного числа чисел Серпинского, то:
1. оно довольно-таки сложное
2. использует факты, основанные на вычислениях

[RIP]

Не знаю док-ва Серпинского.
Есть очень простое док-во (по-моему, очевидное), правда оно кое-что использует (но это всем известно). В задаче же не требуется предъявлять конкретное число $k$, достаточно доказать, чо оно существует.