В 1742 году немецкий математик Кристиан Гольдбах написал письмо своему коллеге Эйлеру: «Мне кажется, любое чётное число больше двух — это сумма двух простых». Прошло почти 300 лет. Никто так и не доказал, что Гольдбах прав. И никто не нашёл число, которое бы это опровергло. Простые числа — самые упрямые объекты в математике: их легко найти, но почти невозможно понять.
Короткий ответ: простое число — это натуральное число больше единицы, которое делится без остатка только на 1 и на само себя. Первые простые: 2, 3, 5, 7, 11, 13, 17, 19, 23. Все остальные числа (кроме единицы) можно разложить на произведение простых — это и есть «атомы» арифметики.
Когда вы оплачиваете покупку картой, простые числа защищают ваши деньги. Алгоритм RSA, на котором держится почти вся защита в интернете, ломается в один момент — если кто-то научится быстро раскладывать большие числа на простые множители. Уже 50 лет лучшие математики и спецслужбы мира пытаются найти такой способ. Никто не нашёл. Поэтому ваш онлайн-банк всё ещё работает.
Шоколадка, которую нельзя разломать поровну
Представьте плитку шоколада, состоящую из 12 квадратиков в один ряд. Её можно разломать на 2 куска по 6, на 3 куска по 4, на 4 куска по 3, на 6 кусков по 2 — много способов поделить честно. А теперь представьте плитку из 13 квадратиков. Её нельзя разломать ровно: либо целиком одному, либо на 13 одинаковых квадратиков. Никаких промежуточных вариантов. Число 13 — простое. Простые числа — это те, что не делятся «красиво». В этом и состоит вся их магия: они не подчиняются.
Почему 1 не считается простым числом
Это любимая ловушка школьных учебников. По формальному определению («делится только на 1 и на само себя») единица вроде бы подходит. Но математики специально вынесли её за скобки. Причина — в основной теореме арифметики: любое число можно разложить на простые множители единственным способом. Например, 30 = 2·3·5, и других вариантов нет. Если бы единица была простой, то 30 = 1·2·3·5 = 1·1·2·3·5 — и так до бесконечности. Единственность ломалась бы. Чтобы теорема осталась красивой, единицу исключили.
Решето Эратосфена: как поймать все простые числа
В III веке до нашей эры александрийский библиотекарь Эратосфен придумал способ найти все простые числа сразу — без перебора. Метод так и называется: решето. Логика проста: запиши числа от 2 до 100, оставь 2, вычеркни всех её «потомков» (4, 6, 8…). Перейди к следующему невычеркнутому — это 3, оставь её, вычеркни 6, 9, 12… Дойди до 5, до 7. Всё, что осталось невычеркнутым к моменту, когда квадрат текущего числа превысил 100, — простые.
Между 1 и 100 ровно 25 простых чисел. Между 1 и 1000 — уже 168. Между 1 и миллионом — почти 78 500. Они становятся всё реже, но никогда не заканчиваются.
Доказательство Евклида: простых чисел бесконечно много
Самое красивое доказательство в школьной математике принадлежит Евклиду — оно использует приём «от противного» и умещается в три строки.
Допустим, простых чисел конечное количество — например, всего N штук: p₁, p₂, …, pₙ. Перемножим их все и прибавим 1: получится новое число M = p₁·p₂·…·pₙ + 1. Это число либо само простое (но его нет в нашем списке — противоречие), либо делится на какое-то простое число — но при делении на любое из p₁…pₙ оно даёт остаток 1, значит это новое простое (опять противоречие). Значит, наше «всего N» — ложь. Простых чисел бесконечно много.
Три способа проверить, простое ли число
Способ 1. Перебор делителей до √n. Чтобы проверить число n, нужно попробовать поделить его на все простые числа от 2 до √n. Если ни одно не делит — n простое. Например, для 97: √97 ≈ 9.8, проверяем делимость на 2, 3, 5, 7 — ни одно не подходит. 97 простое. Этот метод работает для чисел до миллиона; дальше уже долго.
Способ 2. Решето Эратосфена. Хорош, когда нужно найти все простые числа в диапазоне сразу. Не годится для одного огромного числа.
Способ 3. Тест Миллера — Рабина. Вероятностный метод XX века. Не даёт стопроцентной гарантии, но для числа в 200 цифр вероятность ошибки можно сделать меньше, чем шанс, что ваш компьютер сломается в момент проверки. Именно так на практике проверяют простые числа в шифровании.
Как простые числа спасают ваш онлайн-банк
Возьмите два очень больших простых числа p и q — каждое примерно по 300 цифр. Перемножьте: получите число N = p·q длиной около 600 цифр. Зная p и q, вычислить N легко (минута на бумаге, миллисекунды на компьютере). А вот обратная задача — зная только N, восстановить p и q — настолько сложная, что у самого мощного суперкомпьютера на это уйдёт триллионы лет.
На этой асимметрии и построен алгоритм RSA, придуманный в 1977 году. Когда ваш браузер устанавливает защищённое соединение с сайтом банка, сервер посылает вам N, а оба простых числа p и q знает только он. Мошенник, перехвативший N в открытом виде, не может из него ничего извлечь — потому что не существует быстрого способа разложить большое число на простые множители. Если такой способ когда-нибудь найдут, рухнет защита всей мировой цифровой инфраструктуры за один день. Поэтому за простыми числами очень внимательно следят математики, ЦРУ и хакеры одновременно.
Распределение простых чисел: ритм без правила
Если посмотреть, как простые числа разбросаны по числовой прямой, видно, что они становятся всё реже. Между 1 и 100 — 25 простых, между 100 и 200 — уже 21, между 1000 и 1100 — только 16. Французский математик Лежандр и юный Гаусс независимо заметили: количество простых до n приблизительно равно n / ln(n). Эту формулу позже строго доказали — она называется теоремой о распределении простых чисел.
Иногда простые встречаются совсем рядом: пары вроде (11, 13), (17, 19), (29, 31) называют простыми-близнецами. Бесконечно ли таких пар? Никто не знает. Это ещё одна нерешённая задача про простые числа.
Попробуй сам
Задача 1. Сколько простых чисел между 1 и 30? Перечислите их.
Показать решение
10 чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Проверьте по методу Эратосфена — все остальные числа в диапазоне делятся на 2, 3 или 5.
Задача 2. Является ли число 91 простым?
Показать решение
Не является. √91 ≈ 9.5. Проверяем делимость на 2 (нет, нечётное), на 3 (9+1=10, на 3 не делится), на 5 (нет), на 7: 91 ÷ 7 = 13. Получили 91 = 7 · 13 — это составное число. Хитрость: 91 выглядит «простым», потому что оканчивается на 1, но у него есть делители.
Задача 3. Найдите наименьшее простое число, большее 100.
Показать решение
101. Проверка: √101 ≈ 10.05. Делителями могут быть только 2, 3, 5, 7. Ни одно не подходит — 101 простое. Кстати, 102 = 2·3·17, 103 тоже простое (это пара близнецов с 101).
История: от Эратосфена до GIMPS
Около 240 года до нашей эры Эратосфен Киренский, главный библиотекарь Александрийской библиотеки, описал своё «решето» в работе, которая до нас не дошла, — мы знаем о нём из пересказов современников. Чуть раньше Евклид доказал бесконечность простых чисел (книга IX «Начал», предложение 20). После этого почти две тысячи лет простыми числами интересовались скорее как курьёзом.
Всё изменилось в XVII веке, когда французский монах Марен Мерсенн начал изучать числа вида 2ⁿ−1. Если такое число оказывается простым, его называют простым числом Мерсенна. Они растут невероятно быстро: M₂=3, M₃=7, M₅=31, M₇=127, M₁₃=8191. Простые Мерсенна используют, чтобы искать рекордные простые числа.
Сегодня этим занимается распределённый проект GIMPS (Great Internet Mersenne Prime Search), в котором участвуют тысячи добровольцев со всего мира. Ваш домашний компьютер ночью может проверять очередное число-кандидата на простоту. В 2018 году нашли M₈₂₅₈₉₉₃₃ — рекордное простое число длиной 24 862 048 цифр. Если напечатать его обычным шрифтом, лента бумаги протянется примерно на 12 километров.
Гипотеза Римана: миллион долларов за простые числа
В 1859 году Бернхард Риман в коротком письме Берлинской академии наук сформулировал гипотезу о том, как именно расположены простые числа. Если она верна, мы получим невероятно точную формулу для их распределения. Если нет — придётся переписывать учебники по теории чисел.
В 2000 году Институт Клэя включил гипотезу Римана в список «семи задач тысячелетия» и пообещал миллион долларов любому, кто её докажет (или опровергнет). Прошло 26 лет — приз не получен. Компьютеры проверили первые 10 триллионов нулей и не нашли исключений, но это не доказательство. Простые числа всё ещё хранят свою главную тайну.
Часто задаваемые вопросы
Является ли 1 простым числом?
Нет. По современному определению простое число должно иметь ровно два делителя (1 и само себя). У единицы только один делитель. Это сделано специально, чтобы основная теорема арифметики (единственность разложения) работала без исключений.
Является ли 2 простым числом?
Да. 2 — единственное чётное простое число. Все остальные чётные числа делятся на 2, поэтому простыми быть не могут.
Сколько всего простых чисел?
Бесконечно много. Это доказал Евклид более 2300 лет назад. Какое бы конечное множество простых вы ни взяли, всегда можно построить новое простое число, которого там нет.
Какое самое большое известное простое число?
На данный момент рекорд держит число 2⁸²⁵⁸⁹⁹³³ − 1 — простое число Мерсенна, найденное в 2018 году. В нём почти 25 миллионов десятичных цифр. Поиск ведёт распределённый проект GIMPS.
Где простые числа применяются на практике?
Главная сфера — криптография. Алгоритмы RSA, Диффи — Хеллмана и большинство современных способов шифрования основаны на свойствах простых чисел. Также они используются в хеш-функциях, генераторах случайных чисел и кодах исправления ошибок.