Двоичные представления простых чисел

[Профессор Снэйп]

Верно ли, что для любого натурального $k$ существует простое число $p$, такое что $p-1$ делится на $2^k$?

Вопрос сам по себе заинтересовал меня вчера вечером, но возник он вот откуда. Пусть язык $L$ алфавита $\{ 0,1 \}$ состоит из всех двоичных записей простых чисел ($L = \{ 10, 11, 101, 111, 1011, 1101, \ldots \}$). Требуется определить, является ли этот язык регулярным.

Думая, что, конечно же, $L$ не регулярен. Но вот как это строго доказать? Из инструментов, вероятно, лучше всего годится теорема о накачке. Сформулировать её можно следующим образом: если $L$ регулярен, то существует число $n$ такое, что для любого слова $w$ достаточно большой длины и любого разложения $w = xyz$ этого слова с $|y| \geqslant n$ (модуль означает длину слова) существует разложение $y = y_1y_2y_3$, такое что $|y_2| > 0$ и $xy_1y_2^iy_3z \in L \leftrightarrow w \in L$ при всех натуральных $i$. Получается, что если $L$ регулярен, то существует $n$ такое, что если $w$ - двоичная запись достаточно большого простого числа, то в любом подслове слова $w$ длины $n$ можно выбрать непустую серединку $y$ и, представив $w$ в виде $w = xyz$, "накачивать" это $y$, получая слова $xy^iz$, которые все являются двоичными записями простых чисел. И вот как здесь получить противоречие?

[Профессор Снэйп]

По первому вопросу... вроде есть такая теорема, что в каждой арифметической прогрессии можно найти простое число. Если это правда, то для данного $k$ можно взять арифметическую прогрессию $\{ 1 + i2^k : i \in \mathbb{N} \}$. Действительно ли есть такая теорема?

И если ответ на первый вопрос положительный. Получается, что для некоторого $v > 0$ существует такое натуральное $n$, что числа $2^{iv}n+1$ будут простыми для всех $i \in \mathbb{N}$. Нет ли противоречия здесь?

[RIP]

Теорема Дирихле.

[Профессор Снэйп]

Спасибо за ссылку.

По основному вопросу ничего не сможете подсказать?

Вот, кстати, ещё вопрос тогда по ходу. Как насчёт простых чисел вида $2^n + 1$. Их конечное число или бесконечно много?

[RIP]

Профессор Снэйп в сообщении #284398 писал(а):

Вот, кстати, ещё вопрос тогда по ходу. Как насчёт простых чисел вида $2^n + 1$. Их конечное число или бесконечно много?

Неизвестно.

Профессор Снэйп в сообщении #284394 писал(а):

И если ответ на первый вопрос положительный. Получается, что для некоторого $v > 0$ существует такое натуральное $n$, что числа $2^{iv}n+1$ будут простыми для всех $i \in \mathbb{N}$. Нет ли противоречия здесь?

Есть. Пусть при $i=1$ получаем простое $p=2^vn+1$. Тогда, по малой теореме Ферма, $2^{pv}n+1\equiv2^vn+1\equiv0\pmod p$, поэтому при $i=p$ получаем составное число.

[Профессор Снэйп]

Спасибо. Решили задачу