2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Двоичные представления простых чисел
Сообщение29.01.2010, 12:11 
Аватара пользователя
Верно ли, что для любого натурального $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$, которые все являются двоичными записями простых чисел. И вот как здесь получить противоречие?

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

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

 
 
 
 Re: Двоичные представления простых чисел
Сообщение29.01.2010, 13:56 
Аватара пользователя
Теорема Дирихле.

 
 
 
 Re: Двоичные представления простых чисел
Сообщение29.01.2010, 14:05 
Аватара пользователя
Спасибо за ссылку.

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

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

 
 
 
 Re: Двоичные представления простых чисел
Сообщение29.01.2010, 14:07 
Аватара пользователя
Профессор Снэйп в сообщении #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$ получаем составное число.

 
 
 
 Re: Двоичные представления простых чисел
Сообщение29.01.2010, 15:34 
Аватара пользователя
Спасибо. Решили задачу :)

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group