Простые числа

Простое число — это натуральное число, большее единицы, которое имеет ровно два натуральных делителя: единицу и само себя. Числа, имеющие более двух делителей, называются составными. Число 1 не является ни простым, ни составным, так как имеет только один делитель. Простые числа являются фундаментальными объектами теории чисел и играют ключевую роль в математике, криптографии и других областях.

История изучения

Античность

Первые известные исследования простых чисел относятся к Древней Греции. В «Началах» Евклида (около 300 г. до н. э.) была доказана бесконечность множества простых чисел. Евклид также описал алгоритм для нахождения наибольшего общего делителя (алгоритм Евклида), который используется в теории простых чисел. Древнегреческий математик Эратосфен (III век до н. э.) разработал «решето Эратосфена» — простой и эффективный метод для нахождения всех простых чисел до заданного предела.

Средневековье и Новое время

В средние века изучение простых чисел продолжалось в арабском мире. Персидский математик Ибн аль-Хайсам (Альхазен) в XI веке сформулировал теорему, известную как малая теорема Ферма, хотя её доказательство было дано позже. В XVII веке Пьер де Ферма внёс значительный вклад, сформулировав теорему о представлении простых чисел в виде суммы двух квадратов и выдвинув гипотезу о числах Ферма (числа вида \(2^{2^n}+1\)), которые, как он предположил, все являются простыми. Позже Леонард Эйлер в XVIII веке доказал, что число Ферма \(F_5\) является составным, и установил связь между простыми числами и дзета-функцией Римана.

XIX–XX века

В XIX веке были доказаны важные теоремы: теорема Дирихле об арифметических прогрессиях (1837), утверждающая, что существует бесконечно много простых чисел в любой арифметической прогрессии \(a + kd\) с взаимно простыми \(a\) и \(d\); и теорема Чебышёва (1850) о распределении простых чисел, давшая оценки для функции \(\pi(x)\) — количества простых чисел, не превосходящих \(x\). В 1896 году Адамар и Валле-Пуссен независимо доказали асимптотический закон распределения простых чисел: \(\pi(x) \sim \frac{x}{\ln x}\). В XX веке развитие вычислительной техники позволило находить всё большие простые числа, а также привело к открытию тестов простоты (например, тест Миллера — Рабина, тест АКС).

Основные свойства

Фундаментальная теорема арифметики

Каждое натуральное число, большее единицы, может быть единственным образом (с точностью до порядка множителей) представлено в виде произведения простых чисел. Это разложение называется каноническим. Например, \(12 = 2^2 \cdot 3\), \(1001 = 7 \cdot 11 \cdot 13\). Эта теорема обосновывает роль простых чисел как «атомов» арифметики.

Бесконечность множества простых чисел

Доказательство Евклида: предположим, что множество простых чисел конечно: \(p_1, p_2, \dots, p_n\). Рассмотрим число \(N = p_1 p_2 \dots p_n + 1\). Оно не делится ни на одно из простых чисел \(p_i\), так как даёт остаток 1 при делении. Следовательно, \(N\) либо само является простым, либо имеет простой делитель, отличный от \(p_i\). В любом случае получается новое простое число, что противоречит предположению о конечности.

Распределение простых чисел

Функция \(\pi(x)\) (количество простых чисел, не превосходящих \(x\)) ведёт себя асимптотически как \(x / \ln x\). Это означает, что плотность простых чисел среди натуральных чисел убывает с ростом \(x\): примерно одно из каждых \(\ln x\) чисел вблизи \(x\) является простым. Например, среди чисел до 1000 (около 168 простых) плотность ~0,168, а среди чисел до 1 000 000 (около 78 498 простых) плотность ~0,078.

Классификация простых чисел

По форме

• Числа Мерсенна: простые числа вида \(2^p - 1\), где \(p\) — простое число. Названы в честь французского монаха Марена Мерсенна. Крупнейшие известные простые числа часто являются числами Мерсенна, так как для них существуют эффективные тесты простоты (тест Люка — Лемера). Примеры: \(M_2 = 3\), \(M_3 = 7\), \(M_5 = 31\), \(M_7 = 127\).
• Числа Ферма: числа вида \(F_n = 2^{2^n} + 1\). Известны только пять простых чисел Ферма: \(F_0 = 3\), \(F_1 = 5\), \(F_2 = 17\), \(F_3 = 257\), \(F_4 = 65537\). Все остальные проверенные числа Ферма оказались составными.
• Простые числа Софи Жермен: простые числа \(p\), такие что \(2p + 1\) также является простым. Названы в честь французского математика Софи Жермен. Примеры: 2, 3, 5, 11, 23, 29, 41, 53.
• Простые числа-близнецы: пары простых чисел, отличающихся на 2 (например, 3 и 5, 11 и 13, 17 и 19). Существует гипотеза о бесконечности таких пар, но она не доказана.

По свойствам делимости

• Простые числа Вильсона: простые числа \(p\), для которых \((p-1)! + 1\) делится на \(p^2\). Известны только три таких числа: 5, 13, 563. Существует гипотеза, что их бесконечно много.
• Простые числа Вольстенхольма: простые числа \(p\), для которых биномиальный коэффициент \(\binom{2p-1}{p-1}\) даёт остаток 1 при делении на \(p^3\). Известны только два: 16843 и 2124679.

Применение

Криптография

Простые числа лежат в основе многих криптографических систем, в частности, алгоритма RSA (1977). Безопасность RSA основана на сложности разложения больших составных чисел на простые множители. Для генерации ключей используются два больших простых числа (обычно длиной 1024–4096 бит), произведение которых составляет модуль. Другие криптосистемы, использующие простые числа: Диффи — Хеллмана, Эль-Гамаля, схемы на основе эллиптических кривых.

Генерация случайных чисел

Простые числа используются в некоторых генераторах псевдослучайных чисел, например, в алгоритме Блюма — Блюма — Шуба, где модуль является произведением двух больших простых чисел.

Теория кодирования

В кодах Рида — Соломона и других циклических кодах используются конечные поля, размер которых часто является простым числом или степенью простого числа.

Вычислительная математика

Простые числа применяются в алгоритмах хеширования, для проверки целостности данных (контрольные суммы на основе простых чисел), а также в некоторых численных методах.

Открытые проблемы

Гипотеза Римана

Одна из важнейших нерешённых проблем математики, сформулированная Бернхардом Риманом в 1859 году. Она связана с распределением простых чисел и утверждает, что все нетривиальные нули дзета-функции Римана имеют действительную часть, равную 1/2. Гипотеза входит в список проблем тысячелетия Института Клэя.

Гипотеза Гольдбаха

Утверждение, что любое чётное число, большее 2, можно представить в виде суммы двух простых чисел. Сформулирована Христианом Гольдбахом в 1742 году. Проверена для всех чётных чисел до \(4 \times 10^{18}\), но не доказана.

Гипотеза о бесконечности простых чисел-близнецов

Предполагает, что существует бесконечно много пар простых чисел, отличающихся на 2. В 2013 году Итан Чжан доказал, что существует бесконечно много пар простых чисел, расстояние между которыми не превышает 70 миллионов, что стало важным шагом, но не решило проблему полностью.

Интересные факты

• Самое маленькое простое число — 2. Оно единственное чётное простое число, так как любое другое чётное число делится на 2 и поэтому является составным.
• Крупнейшее известное простое число (по состоянию на 2025 год) — \(2^{136279841} - 1\), число Мерсенна, содержащее более 41 миллиона десятичных цифр. Оно было найдено в рамках проекта распределённых вычислений GIMPS (Great Internet Mersenne Prime Search).
• В 2004 году индийские математики Маниндра Агравал, Нирадж Каял и Нитин Саксена опубликовали тест АКС — первый детерминированный тест простоты, работающий за полиномиальное время (для любого числа).
• Простые числа встречаются в природе: например, у некоторых цикад (Magicicada) жизненный цикл составляет 13 или 17 лет — простые числа, что снижает вероятность совпадения с жизненными циклами хищников.

Источники

• А. А. Бухштаб. Теория чисел. — М.: Просвещение, 1966.
• Г. Х. Харди, Э. М. Райт. Введение в теорию чисел. — М.: Мир, 1974.
• К. Айерленд, М. Роузен. Классическое введение в современную теорию чисел. — М.: Мир, 1987.
• Д. Кнут. Искусство программирования. Том 2. — М.: Вильямс, 2001.
• Статья «Prime number» в англоязычной Википедии (версия от 2025 года).