Тайна простых чисел.
они бесконечны. они непредсказуемы. они везде. простые числа — атомы математики: любое натуральное число раскладывается в них единственным образом, но сами они не раскладываются ни во что.
Простые числа — числа, у которых нет делителей, кроме 1 и самого себя. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Они кажутся случайными. Но это не так.
Основная теорема арифметики говорит: любое натуральное число больше 1 единственным образом раскладывается в произведение простых. 12 = 2 × 2 × 3. 100 = 2 × 2 × 5 × 5. 97 = 97. Простые — атомы. Остальные числа — молекулы.
Первый вопрос: сколько их? Евклид ответил в ~300 до н.э.: бесконечно много. Доказательство изящно. Допустим, простых конечное число: p₁, p₂, …, pₙ. Возьмём N = p₁ × p₂ × … × pₙ + 1. N не делится ни на одно из простых — значит либо N простое, либо у него делитель, которого нет в списке. Противоречие. Простых бесконечно.
Второй вопрос: как они распределены? Здесь всё сложнее.
Простые редеют с ростом чисел. Среди первых 10 чисел — 4 простых (40%). Среди первых 100 — 25 (25%). Среди первых 1000 — 168 (16.8%). Среди первых миллиона — 78 498 (7.8%).
Теорема о простых числах (Адамар и де ла Валле-Пуссен, независимо, 1896): количество простых до N примерно равно N / ln(N). При больших N — очень точно. Но не точно. Разница между реальным количеством и N / ln(N) — это погрешность. Насколько мала эта погрешность? Вот здесь начинается тайна1.
«Простые числа растут как сорняки среди натуральных чисел, и кажется, что никакой закономерности в них нет. И при этом они подчиняются удивительно правильным статистическим законам.» — Дон Загье.
В 1859 году Риман написал статью. Восемь страниц. Одна из самых важных в истории математики. Он ввёл дзета-функцию: ζ(s) = 1 + 1/2ˢ + 1/3ˢ + 1/4ˢ + …2
И заметил: точность теоремы о простых числах зависит от того, где находятся нули ζ(s). Риман высказал гипотезу: все нетривиальные нули лежат на прямой Re(s) = 1/2. Это и есть гипотеза Римана.
Если она верна — мы знаем, насколько точно простые числа описываются формулой N / ln(N). Если нет — распределение простых может быть хаотичнее, чем мы думаем.
Гипотеза Римана не доказана. Уже 165 лет. Проверены первые 10 триллионов нулей — все на прямой. Но доказательства нет. Это первая из проблем тысячелетия Клэя. Миллион долларов за решение.
Простые числа скрывают другие тайны. Гипотеза Гольдбаха (1742): любое чётное число > 2 есть сумма двух простых. 4 = 2 + 2. 6 = 3 + 3. 100 = 3 + 97. 1000 = 3 + 997. Проверено до 4 × 10¹⁸. Не доказано3.
Гипотеза о простых близнецах: простых пар (p, p+2) бесконечно много. 3 и 5. 11 и 13. 17 и 19. 1 000 000 007 и 1 000 000 009. Не доказано.
И при этом — простые числа лежат в основе современной криптографии. RSA шифрует данные, используя то, что перемножить два больших простых легко, а разложить произведение обратно — вычислительно невозможно. Каждый раз, когда вы заходите на сайт по https, — вы используете тайну простых чисел4.
Атомы математики защищают интернет.