Проблемы Ландау

Просто́е число́ — это натуральное число, которое имеет ровно 2 различных делителя (только 1 и самого себя). Все остальные числа, не равные единице, называются составными. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, … (последовательность A000040 в OEIS, см. также список простых чисел)

Разложение натуральных чисел в произведение простых

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы (1), представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа — элементарные «строительные блоки» натуральных чисел.

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует (здесь и далее речь идёт о полиномиальной зависимости времени работы алгоритма от логарифма проверяемого числа, то есть от количества его цифр). На предполагаемой вычислительной сложности задачи факторизации базируется криптосистема

Тесты простоты

Основная статья: Тест простоты

Эратосфен Киренский

Решето Эратосфена, решето Сундарама и решето Аткина дают простые способы нахождения начального списка простых чисел вплоть до некоторого значения.

Однако на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. Только в 2002 году было доказано^[1], что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный алгоритм имеет довольно большую сложность, что затрудняет его практическое применение.

Для некоторых классов чисел существуют специализированные эффективные тесты простоты. Например, для проверки на простоту чисел Мерсенна используется тест Люка — Лемера, а для проверки на простоту чисел Ферма — тест Пепина.

Сколько существует простых чисел?

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма всех чисел, обратных к простым, расходится.

Известная теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растёт как n / ln(n).

Наибольшее известное простое

Наибольшим известным простым числом по состоянию на сентябрь 2008 года является 2^43112609 − 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M_43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна 37156667, было найдено 6 сентября 2007 года участником проекта нем. Hans-Michael Elvenich).

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простого числа из более чем 10⁸ десятичных цифр EFF назначила^[2] награду в 150000 долларов США.

Некоторые свойства

• Если p — простое, и p делит ab, то p делит a или b. Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется в доказательстве основной теоремы арифметики.
• Кольцо вычетов $\mathbb{Z}_n$ является полем тогда и только тогда, когда n — простое.
• Характеристика каждого поля — это ноль или простое число.
• Если p — простое, а a — натуральное, то a^p - a делится на p (малая теорема Ферма).
• Если G — конечная группа с pⁿ элементов, то G содержит элемент порядка p.
• Если G — конечная группа, и pⁿ — максимальная степень p, которая делит | G | , то G имеет подгруппу порядка pⁿ, называемую силовской подгруппой, более того, количество силовских подгрупп равно pk + 1 для некоторого целого k (теоремы Силова).
• Натуральное p > 1 является простым тогда и только тогда, когда (p - 1)! + 1 делится на p (теорема Вильсона).
• Если n > 1 — натуральное, то существует простое p, такое, что n < p < 2n (постулат Бертрана).
• Ряд чисел, обратных к простым, расходится. Более того, при $x\to\infty$

$\sum_{p&amp;amp;lt;x} \frac{1}{p}\ \sim\ \ln \ln x.$

• Любая арифметическая прогрессия вида a,a + q,a + 2q,a + 3q,..., где a,q > 1 — целые взаимно-простые числа, содержит бесконечно много простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).
• Всякое простое число, большее 3, представимо в виде 6k + 1, или в виде 6k − 1, где k - некоторое натуральное число.
• Если p > 3 — простое, то p² − 1 кратно 24.

Открытые вопросы

До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены Эдмундом Ландау на Пятом Международном математическом конгрессе^[3]:

1. Проблема Гольдбаха (первая проблема Ландау): доказать или опровергнуть, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.
2. Вторая проблема Ландау: бесконечно ли множество «простых близнецов» — простых чисел, разность между которыми равна 2?
3. Гипотеза Лежандра (третья проблема Ландау) верно ли, что между n² и (n + 1)² всегда найдётся простое число?
4. Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида n² + 1?

Открытой проблемой является также существование бесконечного количества простых чисел во многих целочисленных последовательностях, включая числа Фибоначчи, числа Ферма и т. д.

Приложения

Большие простые числа (порядка 10³⁰⁰) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ Вихрь Мерсенна).

Вариации и обобщения

• В теории колец, разделе абстрактной алгебры, определено понятие простого элемента и простого идеала.
• В теории узлов существует понятие простого узла, который, в определённом смысле, не может быть разбит на более простые узлы.

Литература

• Гальперин Г. «Просто о простых числах», «Квант», № 4, 1987
• «Алгоритмические проблемы теории чисел», глава из книги «Введение в криптографию» под редакцией В. В. Ященко
• Василенко О. Н. «Теоретико-числовые алгоритмы в криптографии»
• Черемушкин А. В. «Лекции по арифметическим алгоритмам в криптографии»
• Кноп К. «В погоне за простотой»
• Кордемский А. Б. Математическая смекалка. — М.: ГИФМЛ, 1958.
• Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker's Delight. — М.: «Вильямс», 2007. — С. 288. — ISBN 0-201-91465-4

См. также

• Список простых чисел
• Примориал
• Открытые математические проблемы

Примечания

1. ↑ Weisstein, Eric W. AKS Primality Test на сайте Wolfram MathWorld.(англ.)
2. ↑ EFF Cooperative Computing Awards(англ.)
3. ↑ Weisstein, Eric W. Landau's Problems на сайте Wolfram MathWorld.(англ.)

Ссылки

• PrimeGrid prime lists — все простые числа, найденные в рамках проекта PrimeGrid
• Геометрия простых и совершенных чисел(исп.)
• Онлайн Утилита для Проверки и Поиска Простых Чисел

Числа

натуральные | целые | рациональные | вещественные | p-адические
иррациональные | алгебраические | трансцендентные
комплексные | дуальные | двойные
кватернионы | числа Кэли (октавы) | седенионы | гиперкомплексные