Простые числа в математике – настоящие звёзды. С античных времён и до сих пор учёные тратят много времени и сил на их изучение. Зачем столько суеты и шумихи? Ведь даже название говорит нам, что эти числа простые!

Эта статья была опубликована в журнале OYLA №3(19). Оформить подписку на печатную и онлайн-версию можно здесь.

А вот для чего. Ещё в древние времена при передаче важного сообщения приходилось считаться с тем, что пос­лание может быть перехвачено противником. Судьба государства часто зависела от умения зашифровывать информацию и расшифровывать «тайнописи» противника.

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

Созданием и анализом методов шифрования занимается наука криптография. Существует огромное количество таких методов. Например, в 1976 году американские математики Уитфилд Диффи и Мартин Хеллман выдвинули концепцию асимметричной криптосистемы, при которой шифрование и дешифрование осуществляются с помощью двух различных ключей — открытого и закрытого (секретного). Буквально через год американцы Рональд Ривест, Ади Шамир и Леонард Адлеман разрабатывают асимметричную криптосистему RSA, названную по первым буквам фамилий её авторов (Rivest, Shamir, Adleman).

Слева направо: Ади Шамир, Рональд Линн Ривест, Леонард Макс Адлеман

В чём «хитрость» этой криптосистемы? Мы не будем углубляться в детали. Скажем лишь, что в основе ключа расшифровки лежит необходимость разложить очень большое число на два простых множителя.

Чтобы успешно вскрыть шифр, нужно уметь разложить числа на простые множители? Всего-то! Это может любой школьник!

Но хватит ли у вас терпения и времени разложить, например, число 1,409,305,684,859 на два простых множителя? Ответом будут простые числа 705,967 и 1,996,277. Чтобы их найти, придётся перебирать простые числа между числами 1 и 2,000,000, а их в этом списке немало — 148,933. Именно сложность обнаружения простых чисел стала причиной их широкого использования в криптографии.

Получается, что даже самые мощные компьютеры не в состоянии разложить очень большие числа на два простых множителя за разумное время, в то время как зашифрованная информация устаревает относительно быстро. И то, что сегодня было секретом, через год, а порой и через день, секретом уже не является. Благодаря этому, асимметричная криптосистема RSA получила повсеместное распространение, а потребность в новых простых числах для создания секретных кодов существует постоянно. А теперь давайте разбираться с простыми числами.

Удивительная вещь таблица умножения! Благодаря ей видно, что чётные числа всегда чередуются с нечётными, а каждое третье число всегда кратно трём. Если же число оканчивается на «ноль» или «пять» –оно кратно «пяти». При делении чисел мы также замечали, что есть очень «удобные» числа, с которыми «приятно» иметь дело. Например, когда надо поровну разделить конфеты.

На вопрос «Какие числа являются делителями числа 60?» можно ответить, что это числа 2, 3, 4, 5, 6, 10, 12, 15, 20 и 30. Что же касается чисел 59 и 61, то они имеют только два делителя — единицу и самого себя. Эти числа называются простыми.

Уверены, вы без особых усилий смогли обнаружить закономерность в первых двух рядах (степени 2-ки и ряда Фибоначчи) и продолжить их. А вот так будет выглядеть четвёртый ряд:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,

37, 41, 43, 47, 53, 59, 61…

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

Поиск простых чисел всегда занимал умы великих математиков. Самый первый и самый простой метод приписывают древнегреческому математику Эратосфену (273–194 до н.э.). Метод называется «решето Эратосфена». 

На примере чисел от 1 до 100 покажем, как при помощи этого метода «просеиваются» простые числа.

1. Составим таблицу натуральных чисел от 1 до 100.
2. Вычеркнем единицу и все числа, кратные двум: 4, 6, 8, 10…
3. Вычеркнем все числа, кратные трём: 6 (уже вычеркнули), 9, 12, 15…
4. Аналогично вычеркнем числа, кратные пяти, семи и т. д.

Невычеркнутыми остались простые числа.

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

В первой тысяче натуральных чисел находится всего 168 простых чисел. Можно предположить, что в каждой следующей тысяче количество простых чисел не будет сильно изменяться. Но это далеко не так. Например, среди чисел в промежутке между числами 10 ¹⁰⁰ и 10¹⁰⁰+1000 существует только два простых числа. Более того, существуют еще бóльшие пробелы, например, 20 000 идущих подряд чисел, среди которых нет ни одного простого числа. Как такое возможно?

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

Аналогично можно составить ряд из ста (миллиона, триллиона) последовательных чисел, не содержащих простых чисел. А это значит, что по мере продвижения по ряду натуральных чисел, простые числа встречаются всё реже и реже.

Означает ли то, что простые числа встречаются всё реже и реже, то, что может наступить момент, когда простые числа больше не появятся? Нет, не означает. Античный математик Евклид очень элегантно и остроумно доказал, что множество простых чисел бесконечно.

Доказательство. Предположим, что нам известны только следующие простые числа:

{2, 3, 5}.

Перемножим их и добавим к результату единицу:

2×3×5 + 1 =31

Ясно, что число 31 не делится ни на одно простое число (2, 3, 5). А это означает, что мы нашли новое простое число.

Если взять ряд последовательных простых чисел, перемножить их и добавить единицу, то полученное число не будет делиться ни на одно из исходных простых чисел.

Возьмём теперь следующий ряд простых чисел:

{2, 3, 5, 7, 11, 13}

Перемножим их и добавим единицу:

2×3×5×7×11×13 + 1 = 30 031

Полученное число также не будет делиться ни на одно из исходных простых чисел. Но это ещё не значит, что оно простое.

Согласно «Основной теореме арифметики», которую сформулировал Евклид, «любое натуральное число может быть единственным образом разложено в произведение простых множителей».

Действительно, число 30 031 может быть разложено в произведение двух других простых чисел:

30 031 = 59 × 509

В этом случае мы также нашли два новых простых числа —

59 и 509

Каким бы ни был первоначальный ряд простых чисел, при их перемножении и добавлении единицы получится:

1. либо новое простое число, которого нет в первоначальном ряду;
2. либо составное число, при разложении которого на простые множители получаются новые простые числа, которых также нет в первоначальном ряду.

К сожалению, этот метод не позволяет найти все простые числа.