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

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

Определение и основные свойства

Формально, простое число \( p \) удовлетворяет следующим условиям:

• \( p > 1 \)
• Если \( p = a \cdot b \), где \( a \) и \( b \) — натуральные числа, то либо \( a = 1 \), либо \( b = 1 \)

Из этого определения вытекают ключевые свойства:

• Единственность разложения: любое натуральное число большее 1 может быть единственным образом (с точностью до порядка множителей) представлено в виде произведения простых чисел. Это утверждение называется основной теоремой арифметики.
• Бесконечность множества: простых чисел бесконечно много. Первое доказательство этого факта принадлежит Евклиду (III век до н. э.) и приведено в его «Началах». Доказательство строится от противного: если бы существовало конечное множество всех простых чисел, то число \( p_1 \cdot p_2 \cdot ... \cdot p_n + 1 \) не делилось бы ни на одно из них, что противоречит предположению.
• Простые числа-близнецы: пары простых чисел, разность между которыми равна 2 (например, 3 и 5, 11 и 13, 17 и 19). Гипотеза о бесконечности таких пар до сих пор не доказана.
• Распределение: количество простых чисел, не превосходящих \( x \), обозначается как \( \pi(x) \). Асимптотический закон распределения простых чисел, доказанный в конце XIX века, утверждает, что \( \pi(x) \sim \frac{x}{\ln x} \). Это означает, что с ростом \( x \) простые числа встречаются всё реже.

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

Древность и Средневековье

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

В Средние века и эпоху Возрождения изучение простых чисел продолжалось, но без принципиальных прорывов. Пьер Ферма (XVII век) сформулировал малую теорему Ферма, которая лежит в основе многих современных тестов на простоту.

Новое время

Леонард Эйлер (XVIII век) внёс огромный вклад в теорию простых чисел. Он доказал, что ряд обратных величин к простым числам расходится (\( \sum \frac{1}{p} \) расходится), что является ещё одним доказательством бесконечности их множества. Эйлер также открыл формулу, генерирующую простые числа: \( n^2 + n + 41 \) даёт простые числа для всех \( n \) от 0 до 39.

В XIX веке были заложены основы аналитической теории чисел. Бернхард Риман в 1859 году сформулировал гипотезу о распределении нулей дзета-функции, которая до сих пор остаётся одной из важнейших нерешённых проблем математики (Гипотеза Римана). Асимптотический закон распределения простых чисел был независимо доказан Адамаром и Валле-Пуссеном в 1896 году.

XX и XXI века

С развитием вычислительной техники поиск больших простых чисел стал отдельной областью. В 1951 году было найдено первое простое число, состоящее из более чем 1000 десятичных знаков. В 1996 году был запущен проект распределённых вычислений GIMPS (Great Internet Mersenne Prime Search), нацеленный на поиск простых чисел Мерсенна (чисел вида \( 2^p - 1 \)). По состоянию на 2024 год крупнейшее известное простое число, найденное в рамках GIMPS, — \( 2^{82589933} - 1 \), содержащее более 24 миллионов десятичных знаков.

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

Простые числа классифицируются по различным признакам. Наиболее известные классы:

По форме

• Простые числа Мерсенна: числа вида \( M_p = 2^p - 1 \), где \( p \) — простое число. Не все такие числа просты (например, \( M_{11} = 2047 = 23 \cdot 89 \)). На сегодняшний день известно 51 простое число Мерсенна. Они играют важную роль в поиске больших простых чисел, так как для них существует эффективный тест простоты (тест Люка — Лемера).
• Простые числа Ферма: числа вида \( F_n = 2^{2^n} + 1 \). Ферма предполагал, что все такие числа просты, но это оказалось неверно. Известны только пять простых чисел Ферма: 3, 5, 17, 257, 65537.
• Простые числа Софи Жермен: простое число \( p \), такое что \( 2p + 1 \) также является простым. Например, 2, 3, 5, 11, 23. Такие числа используются в криптографии.

По свойствам

• Простые числа-близнецы: пары \( (p, p+2) \), где оба числа просты.
• Простые числа Вильсона: числа \( p \), для которых \( (p-1)! \equiv -1 \pmod{p^2} \). Известно всего три таких числа: 5, 13, 563.
• Простые числа-палиндромы: простые числа, которые читаются одинаково слева направо и справа налево (например, 11, 101, 131, 151).

Тесты на простоту

Определение, является ли данное число простым, — одна из классических задач теории чисел. Для малых чисел достаточно проверить делимость на все простые числа, не превышающие квадратного корня из проверяемого числа. Для больших чисел (сотни и тысячи знаков) используются более сложные алгоритмы:

• Детерминированные тесты: дают абсолютно точный ответ. Примеры: тест АКС (2002 год, первый полиномиальный детерминированный тест), тест Люка — Лемера для чисел Мерсенна.
• Вероятностные тесты: дают ответ с некоторой вероятностью ошибки, которая может быть сделана сколь угодно малой. Наиболее распространённые: тест Миллера — Рабина, тест Соловея — Штрассена. Они широко используются в криптографии из-за высокой скорости работы.

Применение

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

Наиболее важное практическое применение простых чисел — в криптографии с открытым ключом. Алгоритм RSA (1977 год) основан на сложности разложения большого составного числа на два простых множителя. Для генерации ключей используются два больших (сотни десятичных знаков) простых числа. Безопасность многих современных систем шифрования (включая протоколы HTTPS, SSH, PGP) напрямую зависит от того, что нахождение простых множителей для чисел длиной в тысячи бит является вычислительно неразрешимой задачей.

Теория чисел

Простые числа являются «атомами» арифметики. Они используются в доказательствах многих теорем, в теории кодирования, в алгоритмах хеширования (например, в хеш-таблицах для уменьшения коллизий).

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

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

Нерешённые проблемы

Несмотря на многовековую историю изучения, многие вопросы о простых числах остаются открытыми. Наиболее известные:

• Гипотеза Римана: о распределении нетривиальных нулей дзета-функции. Её доказательство (или опровержение) входит в список «Проблем тысячелетия» Института Клэя.
• Гипотеза Гольдбаха: любое чётное число больше 2 можно представить в виде суммы двух простых чисел. Проверена для всех чисел до \( 4 \cdot 10^{18} \), но не доказана.
• Гипотеза о бесконечности простых чисел-близнецов.
• Вопрос о существовании простых чисел в арифметических прогрессиях определённого вида (например, бесконечно ли много простых чисел вида \( n^2 + 1 \)).

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

• Число 2 — единственное чётное простое число. Все остальные простые числа нечётны.
• Самое маленькое простое число — 2. Самое большое известное на 2024 год — \( 2^{82589933} - 1 \).
• Простые числа используются в некоторых культурах для гадания и в нумерологии, хотя научного обоснования этому нет.
• Простые числа встречаются в природе: например, некоторые виды цикад (Magicicada) имеют жизненный цикл в 13 или 17 лет — простые числа, что, как предполагается, снижает вероятность совпадения с циклами хищников.

Источники

• Виноградов И. М. «Основы теории чисел»
• Дэвенпорт Г. «Мультипликативная теория чисел»
• Айерленд К., Розен М. «Классическое введение в современную теорию чисел»
• Материалы проекта GIMPS (Great Internet Mersenne Prime Search)
• Статьи из журнала «Успехи математических наук»