Часть I · Числа Глава 3 из 60

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

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

5–9 класс 40 минут

Опирается на: 2 · Ноль и минус

Вы научитесь

быстро проверять, простое ли число, и выписывать все простые до заданного решетом Эратосфена
раскладывать числа на простые множители и понимать, почему такое разложение единственно
доказывать, что простых чисел бесконечно много, и оценивать, сколько их до заданного числа

Линия I · Числа

Вы здесь: 3 · Простые числа

Пересадки 44 · Дзета и кривые

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

Начнём с плиток. Двенадцать квадратных плиток можно сложить в прямоугольник $3 \times 4$, можно в $2 \times 6$, а можно вытянуть в полоску $1 \times 12$. С тринадцатью плитками так не получится: в два ряда одна плитка окажется лишней, в три — тоже, и так до самого конца. Остаётся только полоска.

Меняйте число плиток. Для каких чисел, кроме полоски, ничего не складывается?

Числа-«полоски» и есть наша добыча. Эта глава — охота на них: как их опознать, как выловить всех сразу, сколько их всего, где они прячутся и какие из них до сих пор никому не дались.

Кого ловим

Сначала договоримся о словах. Прямоугольник из $n$ плиток со сторонами $a$ и $b$ — это запись $n = a \cdot b$.

Делитель числа $n$ — такое число $d$, что $n = d \cdot k$ для некоторого целого $k$, то есть $n$ делится на $d$ без остатка. Пишут $d \mid n$ и читают «$d$ делит $n$». Само $n$ при этом называют кратным числа $d$. У натурального числа есть и отрицательные делители ($-3$ делит $12$), но, говоря о делителях натурального числа, мы будем иметь в виду натуральные.

У двенадцати шесть делителей: $1, 2, 3, 4, 6, 12$. Единица и само число делят его всегда, это делители «бесплатные». Интересно, есть ли другие.

Натуральное число называется простым, если оно больше единицы и делится только на $1$ и на себя. Число больше единицы, у которого есть и другие делители, называется составным.

Простые числа до пятидесяти: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$. Двойка — единственное чётное простое: любое другое чётное число делится на два. А единица не попала ни в простые, ни в составные. Так договорились нарочно, и у договорённости есть веская причина. Мы до неё доберёмся, когда станет видно, что без неё сломалось бы.

Какое из этих чисел простое?

$51 = 3 \cdot 17$, $57 = 3 \cdot 19$, $91 = 7 \cdot 13$ — все три только притворяются простыми. По известному анекдоту, Александр Гротендик, один из самых глубоких математиков XX века, на вопрос о конкретном простом числе назвал $57$; с тех пор его в шутку зовут «простым Гротендика». Честно простое здесь только $97$.

Как опознать одно простое

Проверить, простое ли число $97$, можно в лоб: делить его на $2, 3, 4, \dots, 96$ и смотреть, не разделится ли. Это девяносто пять делений. Почти все они лишние, и чтобы это увидеть, нужны два наблюдения.

Наименьший делитель натурального числа $n > 1$, больший единицы, — простое число.

Идея: будь этот делитель составным, у него самого нашёлся бы делитель поменьше, и он тоже делил бы $n$.

Обозначим через $d$ наименьший делитель $n$, больший единицы. Он существует, потому что само $n$ — делитель $n$, больший единицы. Предположим, что $d$ составное. Тогда $d = e \cdot f$, где $1 < e < d$. Раз $d$ делит $n$, то $n = d \cdot k$ для некоторого целого $k$, и тогда $n = e \cdot (f k)$: число $e$ тоже делит $n$. Получился делитель $n$, больший единицы и меньший $d$, — а $d$ мы выбрали наименьшим. Противоречие, значит, $d$ простое.

Отсюда первое сокращение: делить стоит только на простые. Если $97$ не делится на $2$, то не делится и на $4$, $6$, $8$: всё, что делится на четвёрку, делится и на двойку. Второе сокращение важнее: хватает дойти до корня.

Если натуральное число $n > 1$ не делится ни на одно простое $p$, для которого $p^2 \le n$, то $n$ — простое.

Хитрость в том, чтобы увидеть составное число прямоугольником: его короткая сторона не бывает длиннее корня.

Пусть $n$ составное. Тогда $n = a \cdot b$, где $1 < a \le b$: из двух множителей $a$ — меньший. Выложим $n$ плиток прямоугольником $a \times b$.

Раз $a \le b$, квадрат $a \times a$ помещается внутри прямоугольника, поэтому его площадь не больше: $\p1{a^2} \le a \cdot b = n$.

Пусть $p$ — наименьший делитель числа $a$, больший единицы; по лемме выше он простой. Строки прямоугольника разбиваются на полосы по $p$ штук, значит, $p$ делит и всё $n$. А так как $p \le a$, то $p^2 \le a^2 \le n$.

У каждого составного $n$ нашёлся простой делитель $p$ с $p^2 \le n$. Поэтому, если такого делителя нет, $n$ не составное, то есть простое.

Для $97$ корень меньше $10$ ($10^2 = 100$), так что проверяем $2, 3, 5, 7$. Ни одно не делит $97$ — оно простое. Четыре деления вместо девяноста пяти.

Найдите наименьший простой делитель числа $221$.

$\sqrt{221}$ чуть меньше $15$ ($15^2 = 225$), поэтому проверяем $2, 3, 5, 7, 11, 13$. На $2$, $3$, $5$ число не делится (оно нечётное, сумма цифр $5$, последняя цифра не $0$ и не $5$). $221 = 7 \cdot 31 + 4$, $221 = 11 \cdot 20 + 1$, а вот $221 = 13 \cdot 17$. Ответ: $13$.

Решето: ловим всех сразу

Проверять числа по одному медленно, если нужны все простые подряд. Способ получше придумал Эратосфен Киренский (около 276 — около 194 до н. э.), хранитель Александрийской библиотеки, тот самый, что измерил окружность Земли. Его собственные сочинения почти не сохранились, и метод дошёл до нас в пересказе Никомаха Герасского, писавшего около 100 года н. э.

Выпишем числа от $2$ до $120$. Первое число, $2$, простое: обведём его и вычеркнем все чётные. Первое невычеркнутое после двойки — $3$. Его не вычеркнула двойка, значит, на $2$ оно не делится, а меньших простых нет: $3$ простое. Обводим, вычёркиваем кратные трём. Следующее уцелевшее — $5$, потом $7$. Каждый раз первое уцелевшее число простое: его не делит ни одно из меньших простых, иначе его бы уже вычеркнули.

Жмите «Следующее простое» и следите, откуда решето начинает вычёркивать. Переключитесь на шесть столбцов: куда попадают простые?

Решето экономит дважды. Кратные пятёрки оно вычёркивает не с $10$, а с $25$: числа $10$, $15$ и $20$ уже вычеркнуты двойкой или тройкой, потому что у каждого есть множитель меньше пяти. И останавливается решето на семёрке. Следующее уцелевшее, $11$, в квадрате даёт $121 > 120$, а у составного числа до $120$ обязательно есть простой делитель не больше $\sqrt{120} < 11$. Все такие делители уже отработали, так что всё невычеркнутое — простое. До $120$ таких чисел тридцать.

В раскладке по шесть видна ещё одна примета добычи. После $2$ и $3$ простые стоят только в двух столбцах: они на единицу меньше или больше числа, кратного шести. Остальные четыре столбца заняты числами вида $6k$, $6k + 2$, $6k + 3$, $6k + 4$, а те делятся на $2$ или на $3$. Обратное неверно: $25 = 6 \cdot 4 + 1$ и $35 = 6 \cdot 6 - 1$ стоят в «правильных» столбцах и всё равно составные.

Решето Эратосфена — способ выписать все простые числа до $N$: берём наименьшее невычеркнутое число $p$, объявляем его простым, вычёркиваем кратные $p$, начиная с $p^2$, и повторяем, пока $p^2 \le N$. Всё, что осталось, — простые.

После работы решета Эратосфена на числах от $2$ до $N$ невычеркнутыми остаются все простые числа до $N$, и только они.

Нужно проверить две вещи: простое число решето не вычёркивает, а каждое составное вычёркивает.

Решето вычёркивает только числа вида $m \cdot p$, где $p$ — одно из обработанных простых и $m \ge p \ge 2$. У такого числа есть делитель $p$, отличный и от единицы, и от самого числа (оно больше $p$, ведь $m \ge 2$). Значит, вычеркнутые числа составные, и простое решето не тронет.

Теперь возьмём составное $n \le N$, и пусть $p$ — его наименьший простой делитель: $n = p \cdot m$. Здесь $m > 1$, и любой простой делитель $m$ делит $n$, а потому не меньше $p$; значит, $m \ge p$ и $n = p \cdot m \ge p^2$. Тем более $p^2 \le N$, поэтому решето дойдёт до $p$: по доказанному только что $p$ никто не вычеркнул, и оно будет первым уцелевшим после меньших простых. Кратные $p$ решето вычёркивает от $p^2$ до $N$, а $n$ — кратное $p$ из этого промежутка. Значит, $n$ будет вычеркнуто.

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

Атомы умножения

Составное число по определению распадается в произведение двух меньших: $360 = 4 \cdot 90$. Если какой-то множитель снова составной, режем дальше: $4 = 2 \cdot 2$, $90 = 9 \cdot 10$, $9 = 3 \cdot 3$, $10 = 2 \cdot 5$. Числа всё время уменьшаются, так что рано или поздно резать станет нечего. Останутся одни простые — атомы, из которых собрано число.

Коснитесь составного числа и выберите, как его разрезать. Потом склейте и разрежьте по-другому: изменится ли набор листьев?

Сколько бы раз вы ни разбирали $360$, внизу окажутся три двойки, две тройки и одна пятёрка. Одинаковые множители удобно собирать в степени.

Различные простые числа, из которых состоит $n$. Обычно их пишут по возрастанию: $p_1 < p_2 < \dots < p_k$.

Показатели — сколько раз каждое простое входит в разложение. Все они натуральные: простое, которое не входит, просто не пишут.

Примеры: $360 = 2^3 \cdot 3^2 \cdot 5$, $1001 = 7 \cdot 11 \cdot 13$, $2024 = 2^3 \cdot 11 \cdot 23$, $1024 = 2^{10}$. У простого числа разложение состоит из него самого: $97 = 97$.

Разложение на простые множители — запись числа в виде произведения простых. Мы только что убедились, что оно есть у каждого числа больше единицы. Главное утверждение этой главы в том, что оно ещё и одно.

Пример: раскладываем 2024 «столбиком»

В тетради разложение удобно записывать так: слева то, что осталось, справа — наименьший простой делитель этого числа.

$$\begin{array}{r|l} 2024 & 2 \\ 1012 & 2 \\ 506 & 2 \\ 253 & 11 \\ 23 & 23 \\ 1 & \end{array}$$

Число $253$ не делится на $2$, $3$, $5$ и $7$, зато $253 = 11 \cdot 23$. Число $23$ простое: $5^2 = 25 > 23$, а на $2$ и $3$ оно не делится. Итог: $2024 = 2^3 \cdot 11 \cdot 23$.

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

Идея: резать, пока режется, и убедиться, что резать бесконечно нельзя.

Если $n$ простое, разложение уже есть: оно состоит из одного множителя. Если составное, то $n = a \cdot b$, где оба множителя больше $1$ и потому меньше $n$. На чертеже $360 = 4 \cdot 90$.

С каждым составным множителем поступаем так же: $4 = 2 \cdot 2$, $90 = 9 \cdot 10$. Простые множители больше не режем. Произведение всех листьев после каждого разреза по-прежнему равно $n$: мы лишь заменяем число произведением, которое ему равно.

Продолжаем, пока среди листьев есть составные: $9 = 3 \cdot 3$, $10 = 2 \cdot 5$. Каждый разрез добавляет один лист.

Бесконечно резать нельзя. Каждый лист не меньше $2$, а произведение листьев равно $n$, поэтому, если листьев $L$, то $2^L \le n$: листьев не может быть сколько угодно (для $360$ — не больше восьми, потому что $2^9 = 512 > 360$). Раз каждый разрез добавляет лист, а начинали мы с одного, разрезов меньше, чем листьев, — конечное число. Когда резать нечего, все листья простые, и их произведение — разложение $n$: $360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5$.

С существованием просто. Единственность кажется столь же очевидной, но это обманчивое чувство. Вот мир, где она ломается.

Пусть в этом мире живут только числа $1, 5, 9, 13, 17, 21, 25, 29, \dots$ — те, что при делении на $4$ дают остаток $1$. Произведение двух таких снова такое: $(4a + 1)(4b + 1) = 4(4ab + a + b) + 1$. Значит, умножать внутри мира можно, и можно спросить, какие его числа «простые», то есть не раскладываются на меньшие числа этого же мира. Число $9$ простое здесь: тройки в этом мире нет. Так же обстоят дела с $21 = 3 \cdot 7$ и $49 = 7 \cdot 7$: их настоящих делителей $3$ и $7$ в мире нет. А теперь смотрите:

$$441 = 9 \cdot 49 = 21 \cdot 21.$$

Два разных разложения на «простые». Этот пример приписывают Давиду Гильберту. Он показывает, что единственность — свойство именно целых чисел, и его нужно доказывать, а не принимать на веру.

Доказательство единственности держится на одном факте о простых числах. В мире Гильберта он неверен: «простое» $9$ делит $21 \cdot 21$, но не делит $21$.

Если простое число $p$ делит произведение $a \cdot b$ натуральных чисел, то $p$ делит $a$ или $p$ делит $b$.

Идея: найти самое маленькое натуральное $x$, для которого $x \cdot b$ делится на $p$, и показать, что оно делит и $p$, и $a$.

Пусть $p$ делит $ab$, но не делит $a$; докажем, что тогда $p$ делит $b$. Назовём натуральное $x$ подходящим, если $x \cdot b$ делится на $p$. Подходящие числа есть: это $p$ (число $pb$ делится на $p$) и $a$ (по условию). Пусть $m$ — наименьшее подходящее число.

Покажем, что $m$ делит каждое подходящее $x$. Разделим $x$ на $m$ с остатком: $x = q m + r$, где $0 \le r < m$ (подробно о делении с остатком — в следующей главе). Тогда $r b = x b - q \cdot (m b)$. Оба числа $xb$ и $mb$ делятся на $p$, значит, и разность $rb$ делится на $p$. Если бы $r$ было больше нуля, оно оказалось бы подходящим числом меньше $m$, а $m$ — наименьшее. Поэтому $r = 0$, и $m$ делит $x$.

В частности, $m$ делит $p$ и $m$ делит $a$. Делители простого $p$ — только $1$ и $p$. Если $m = p$, то $p$ делит $a$, а мы предположили обратное. Значит, $m = 1$: число $1 \cdot b = b$ делится на $p$.

В следующей главе у леммы появится второе, совсем короткое доказательство — через алгоритм Евклида. А пока выведем из неё единственность.

Единственность разложения. Пусть у числа два разложения на простые: $p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_m$ (множители могут повторяться). Простое $p_1$ делит левую часть, а значит, и правую, то есть произведение $q_1 \cdot (q_2 \cdots q_m)$. По лемме Евклида $p_1$ делит $q_1$ или делит $q_2 \cdots q_m$; во втором случае применим лемму к $q_2 \cdot (q_3 \cdots q_m)$, и так далее. В конце концов $p_1$ делит одно из $q_j$. У простого $q_j$ делители только $1$ и $q_j$, а $p_1 > 1$, поэтому $p_1 = q_j$.

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

Теперь понятно, за что единицу выгнали из простых. Будь она простой, у шести нашлось бы бесконечно много разложений: $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3 = \dots$, и главную теорему пришлось бы произносить с оговоркой «не считая единиц». Удобнее исключить единицу один раз, в определении.

Разложение сразу рассказывает о числе всё, что касается делимости. Например, сколько у него делителей.

Если $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ — разложение на различные простые, то у $n$ ровно $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$ делителей.

Идея: каждый делитель — это «кусок» разложения $n$, и куски легко пересчитать.

Пусть $d$ делит $n$, то есть $n = d \cdot e$. Разложим $d$ и $e$ на простые и перемножим: получится разложение $n$. По единственности оно совпадает с $p_1^{a_1} \cdots p_k^{a_k}$. Поэтому в разложение $d$ входят только простые $p_1, \dots, p_k$, и каждое $p_i$ — не больше $a_i$ раз: $d = p_1^{b_1} \cdots p_k^{b_k}$, где $0 \le b_i \le a_i$. Обратно, каждое такое число делит $n$: частное равно $p_1^{a_1 - b_1} \cdots p_k^{a_k - b_k}$. Разные наборы показателей дают разные числа — снова по единственности разложения. Показатель $b_1$ можно выбрать $a_1 + 1$ способом (от $0$ до $a_1$), $b_2$ — $a_2 + 1$ способом, и так далее; все наборы вместе дают $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$ делителей.

Для $360 = 2^3 \cdot 3^2 \cdot 5$ это $4 \cdot 3 \cdot 2 = 24$ делителя. У $60 = 2^2 \cdot 3 \cdot 5$ делителей двенадцать, и одно из объяснений, почему вавилоняне считали шестидесятками, — как раз это обилие делителей.

Сколько делителей у числа $72$ (вместе с $1$ и $72$)?

$72 = 2^3 \cdot 3^2$. Делитель — это $2^i \cdot 3^j$, где $i \in \{0, 1, 2, 3\}$, $j \in \{0, 1, 2\}$: всего $4 \cdot 3 = 12$ вариантов. Вот они: $1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72$.

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

Им нет конца

Чем дальше по числовой прямой, тем реже попадаются простые. Среди первых десяти чисел их четыре, а среди чисел от $91$ до $100$ только одно, $97$. Может быть, где-то далеко они кончаются совсем, и после последнего простого все числа составные?

Нет. Ответ дал Евклид около 300 года до н. э., в девятой книге «Начал» (предложение 20). Его доказательство до сих пор приводят как образец: оно умещается в несколько строк и не требует ничего, кроме деления с остатком.

Простых чисел бесконечно много.

Идея: по любому конечному списку простых построить число, которое ни на одно из них не делится.

Возьмём любой конечный список простых чисел $p_1, p_2, \dots, p_n$ и составим число $N = p_1 p_2 \cdots p_n + 1$.

Разделим $N$ на любое $p_i$ из списка. Произведение $p_1 p_2 \cdots p_n$ делится на $p_i$ — это один из сомножителей. Значит, $N$ на единицу больше числа, кратного $p_i$: остаток равен $1$, и $p_i$ не делит $N$.

При этом $N \ge 2 + 1 > 1$, поэтому у $N$ есть делители, большие единицы (хотя бы само $N$), а наименьший из них — простое число $q$ по лемме о наименьшем делителе.

Простое $q$ делит $N$, а ни одно число из списка $N$ не делит. Значит, $q$ в списке нет. Какой бы конечный список простых мы ни составили, найдётся простое вне его, поэтому простых бесконечно много.

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

Убирайте и добавляйте простые в списке. Машина каждый раз находит простое, которого в списке нет. Нажмите «Начать с одной двойки» и добавляйте то, что она выдаёт.

Верно ли, что число $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ простое?

$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30\,031 = 59 \cdot 509$. Евклид не утверждает, что $N$ простое. Он утверждает, что у $N$ есть простой делитель вне списка. Здесь таких делителей даже два.

Что будет, если запускать машину снова и снова

Начнём с одной двойки и каждый раз будем добавлять в список наименьший простой делитель числа $N$. Получится последовательность $2, 3, 7, 43, 13, 53, 5, 6\,221\,671, 38\,709\,183\,810\,571, \dots$ Её называют последовательностью Евклида — Маллина. В 1963 году Альберт Маллин спросил, встретится ли в ней рано или поздно каждое простое число. Ответа нет до сих пор, хотя поиск прошёл уже несколько десятков её членов. Одно из самых простых доказательств в математике приводит к вопросу, на который никто не знает ответа.

Пустыни и близнецы

Простых бесконечно много, но стоят они очень неровно. После $113$ следующее простое — $127$: между ними тринадцать составных чисел подряд. Между $1327$ и $1361$ простых нет на протяжении тридцати трёх чисел.

Пустыню любой длины можно построить нарочно. Обозначим через $n!$ произведение $1 \cdot 2 \cdot 3 \cdots n$ (читается «эн факториал»).

Для любого натурального $n \ge 2$ числа $n! + 2,\ n! + 3,\ \dots,\ n! + n$ — это $n - 1$ составных чисел подряд.

Идея: $n!$ делится на каждое число от $2$ до $n$, и прибавка $j$ этого не портит. На чертеже $n = 4$; для любого $n$ рассуждение то же.

Возьмём $4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$ и выложим его полоской из $24$ клеток.

Пусть $j$ — одно из чисел от $2$ до $n$ (здесь $2$, $3$ или $4$). Оно входит в произведение $n!$ сомножителем, поэтому $n!$ делится на $j$: полоска режется на $j$ равных частей, по $\frac{n!}{j}$ клеток.

Добавим $j$ клеток — по одной в конец каждой части. Частей по-прежнему $j$, и все они равны: $n! + j = j \cdot \bigl(\frac{n!}{j} + 1\bigr)$. Значит, $j$ делит $n! + j$.

У числа $n! + j$ есть делитель $j$, больший единицы и меньший самого числа, — оно составное. Это верно для каждого $j$ от $2$ до $n$, и числа $n! + 2, \dots, n! + n$ идут подряд: $n - 1$ составных подряд. При $n = 4$ это $26, 27, 28$.

Возьмём $n = 10$: $10! = 3\,628\,800$, и все девять чисел от $3\,628\,802$ до $3\,628\,810$ составные. При $n = 1000$ получится пустыня из $999$ составных чисел. Рецепт расточителен: настоящие пустыни такой длины встречаются гораздо раньше. Но он доказывает главное: промежутки между соседними простыми бывают сколь угодно длинными.

Число $7! + 5 = 5045$ заведомо составное. На какое число от $2$ до $7$ оно делится? Ответ получите, не деля.

$7! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7$ делится на $5$, и слагаемое $5$ тоже. Значит, и сумма делится на $5$: $5045 = 5 \cdot 1009$.

И в то же время простые то и дело ходят парами через одно число: $3$ и $5$, $5$ и $7$, $11$ и $13$, $17$ и $19$, $29$ и $31$, $41$ и $43$. Ближе стоять не могут: из двух соседних чисел одно чётное, а чётное простое только одно — двойка, так что соседями бывают лишь $2$ и $3$.

Простые-близнецы — пары простых чисел, отличающихся на $2$. До ста их восемь пар, до тысячи — тридцать пять.

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

Перепись: сколько простых до x

Раз по одному простые непредсказуемы, посчитаем их оптом, как считают население.

Функция $\pi(x)$ — количество простых чисел, не превосходящих $x$. Например, $\pi(10) = 4$ (это $2, 3, 5, 7$), $\pi(100) = 25$. Буква $\pi$ здесь не имеет отношения к числу $3{,}14\ldots$ — просто так сложилось.

$x$	$\pi(x)$	$x / \ln x$	$\pi(x) : \dfrac{x}{\ln x}$
$10^2$	$25$	$22$	$1{,}151$
$10^3$	$168$	$145$	$1{,}161$
$10^4$	$1229$	$1086$	$1{,}132$
$10^6$	$78\,498$	$72\,382$	$1{,}084$
$10^8$	$5\,761\,455$	$5\,428\,681$	$1{,}061$
$10^{10}$	$455\,052\,511$	$434\,294\,482$	$1{,}048$

В третьем столбце стоит догадка, которую сделал Карл Фридрих Гаусс. В письме астроному Иоганну Энке (1849) он вспоминал, что задумался о распределении простых ещё в 1792 или 1793 году, подростком, и составлял таблицы: сколько простых приходится на каждую тысячу чисел. Он заметил, что возле числа $x$ простые встречаются примерно с частотой $1/\ln x$.

Здесь $\ln x$ — натуральный логарифм; подробно о нём в главе о степенях и логарифмах. Сейчас достаточно знать, что он растёт очень медленно и для $x = 10^k$ примерно равен $2{,}3\,k$. Около тысячи $\ln x \approx 6{,}9$, и простое попадается примерно каждое седьмое число; около миллиона $\ln x \approx 13{,}8$ — каждое четырнадцатое; около миллиарда — каждое двадцать первое. Если каждое $\ln x$-е число простое, то до $x$ их около $x / \ln x$.

Сколько простых чисел не превосходит $x$.

Сколько всего чисел мы перебрали.

Средний промежуток между соседними простыми возле $x$: в среднем одно простое на $\ln x$ чисел.

Пример: при $x = 10^6$ получаем $\frac{1\,000\,000}{13{,}8155\ldots} \approx 72\,382$, а на самом деле простых $78\,498$. Ошибка около $8\,\%$.

Значок $\approx$ здесь надо читать осторожно. Разность между $\pi(x)$ и $x/\ln x$ не уменьшается, а растёт: при $x = 10^6$ это $6\,116$, при $x = 10^{10}$ — уже больше двадцати миллионов. К единице стремится отношение: $1{,}084$, $1{,}061$, $1{,}048$ — медленно и не монотонно (от $10^2$ к $10^3$ оно даже подросло), но стремится. Это и утверждает теорема.

Отношение $\pi(x)$ к $x / \ln x$ стремится к единице, когда $x$ неограниченно растёт.

Гаусс так и не смог это доказать. Доказательство появилось примерно через сто лет после его наблюдения: в 1896 году, независимо друг от друга, его нашли Жак Адамар и Шарль-Жан де ла Валле-Пуссен. Оба опирались на идеи Бернхарда Римана и на комплексный анализ; этот путь мы пройдём в главе о дзета-функции.

Почему доказательства здесь нет. Оценить $\pi(x)$ грубо можно элементарными средствами, без комплексных чисел: Пафнутий Чебышёв около 1850 года доказал, что при больших $x$ отношение $\pi(x) : \frac{x}{\ln x}$ зажато между $0{,}92$ и $1{,}11$. Но чтобы показать, что оно стремится именно к единице, нужен другой уровень. Адамар и Валле-Пуссен связали $\pi(x)$ с дзета-функцией Римана и вывели теорему из того, что у этой функции нет нулей на прямой $\operatorname{Re} s = 1$ комплексной плоскости; для этого нужен комплексный анализ. В 1949 году Атле Сельберг и Пал Эрдёш нашли доказательство без комплексных чисел, но и оно держится на длинных и тонких оценках. Идею пути через дзета-функцию разберём в главе 44.

Двигайте точку по лестнице $\pi(x)$ и сравнивайте с кривой $x / \ln x$. В режиме «как часто» столбики показывают долю простых на каждом отрезке — Гаусс считал именно так.

Уточнение Гаусса: интегральный логарифм

Сам Гаусс предлагал приближение точнее. Если вероятность «быть простым» возле числа $t$ равна $1 / \ln t$, то простые до $x$ надо не умножать на одну частоту, а складывать по кусочкам: $\mathrm{Li}(x) = \int_2^x \frac{dt}{\ln t}$ (что такое интеграл, расскажет глава 28). При $x = 10^6$ получается около $78\,626$ против настоящих $78\,498$: ошибка меньше $0{,}2\,\%$. При $x = 10^{10}$ ошибка — около трёх тысяч на четыреста пятьдесят пять миллионов. Насколько маленькой она остаётся всегда, зависит от гипотезы Римана — самой знаменитой открытой задачи математики.

Узор на скатерти

По рассказу самого Станислава Улама, в 1963 году он скучал на длинном докладе и от нечего делать начал писать на листке числа по спирали: $1$ в центре, $2$ справа, $3$ над ней, дальше против часовой стрелки, виток за витком. Потом обвёл простые. И увидел то, чего никто не ждал: простые выстраивались в диагональные линии.

Узор разглядели на компьютере в Лос-Аламосе, где тогда работал Улам, на спиралях из десятков тысяч чисел. Весной 1964 года картинка попала на обложку журнала Scientific American, в колонку Мартина Гарднера, и с тех пор её называют скатертью Улама.

Увеличьте сторону до сотни и больше: видны диагонали. Переключитесь на «случайные» — это нечётные числа, выбранные наугад с той же густотой. Включите подсветку многочлена Эйлера.

Отчасти узор объяснить легко. Числа на одной диагонали спирали — значения многочлена вида $4n^2 + bn + c$. Если все его значения чётные, диагональ пустая. Если же многочлен не делится ни на $2$, ни на $3$, ни на другие маленькие простые ни при каких $n$, его значения чаще других оказываются простыми, и диагональ густеет.

Рекордсмен среди таких многочленов известен со времён Леонарда Эйлера, который писал о нём в 1772 году: $n^2 + n + 41$. При $n = 0, 1, 2, \dots, 39$ он даёт сорок простых подряд: $41, 43, 47, 53, 61, 71, \dots, 1601$. Если начать спираль с $41$, все они лягут на одну диагональ.

Сорок простых подряд. Значит ли это, что $n^2 + n + 41$ простое при любом $n$?

При $n = 40$ выходит $1600 + 40 + 41 = 1681 = 41^2$. А при $n = 41$ все три слагаемых делятся на $41$: $41 \cdot 43$. Та же ловушка, что с кругом Мозера из вступления, только длиннее. Более того, ни один многочлен $f$ с целыми коэффициентами (кроме постоянного) не даёт одни только простые. Если $f(1) = p$ — простое, то разность $f(1 + kp) - f(1)$ делится на $(1 + kp) - 1 = kp$, поэтому каждое значение $f(1 + kp)$ делится на $p$; а равняться самому $p$ многочлен может лишь при конечном числе значений $k$.

Дальше объяснения кончаются. Почему одни диагонали гуще других, описывает гипотеза Годфри Харди и Джона Литлвуда (1923), но она не доказана. Неизвестно даже, бесконечно ли много простых вида $n^2 + 1$: $2, 5, 17, 37, 101, \dots$ Этот вопрос Эдмунд Ландау ещё в 1912 году включил в список четырёх задач о простых, которые считал недоступными. В тот же список вошли два вопроса из следующего раздела.

Добыча, которая ушла

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

Близнецы

Бесконечно ли много пар простых-близнецов? Никто не знает. Долго не удавалось доказать даже, что бесконечно много пар простых стоят ближе хоть какого-нибудь фиксированного расстояния. В 2013 году Итан Чжан, тогда почти неизвестный математик, доказал: пар простых, отличающихся не больше чем на $70$ миллионов, бесконечно много. Семьдесят миллионов вместо двух — но это было первое конечное число. Совместный интернет-проект «Полимат» и Джеймс Мейнард довели границу до $246$. От двойки её отделяет барьер, который нынешние методы, по-видимому, преодолеть не могут.

Гольдбах

В 1742 году Кристиан Гольдбах в письме Эйлеру высказал догадку, которую сегодня формулируют так: всякое чётное число больше двух — сумма двух простых. $4 = 2 + 2$, $28 = 5 + 23 = 11 + 17$, а сто раскладывается шестью способами: $3 + 97$, $11 + 89$, $17 + 83$, $29 + 71$, $41 + 59$, $47 + 53$. Компьютеры проверили гипотезу для всех чётных чисел до $4 \cdot 10^{18}$, но доказательства нет. Для нечётных чисел доказано похожее: в 2013 году Харальд Хельфготт показал, что каждое нечётное число больше пяти — сумма трёх простых.

Разложите $98$ в сумму двух простых. Каким окажется меньшее слагаемое, если выбрать его как можно меньше?

Перебираем простые $p$ по возрастанию и проверяем, простое ли $98 - p$: $96$, $95 = 5 \cdot 19$, $93 = 3 \cdot 31$, $91 = 7 \cdot 13$, $87 = 3 \cdot 29$, $85 = 5 \cdot 17$, $81 = 3^4$ — всё составные. Только при $p = 19$ получается простое $79$. Ответ: $98 = 19 + 79$, меньшее слагаемое $19$. Всего способов три: ещё $31 + 67$ и $37 + 61$.

Самое большое известное простое

Простых бесконечно много, но известно в каждый момент конечное число, и среди них есть самое большое. На момент написания главы это $2^{136\,279\,841} - 1$, найденное в октябре 2024 года проектом GIMPS, где тысячи добровольцев отдают поиску мощность своих компьютеров. В нём $41\,024\,320$ цифр: если печатать по три тысячи цифр на странице, выйдет больше тринадцати тысяч страниц.

Рекордсмены почти всегда имеют вид $2^p - 1$ — это числа Мерсенна, по имени французского монаха и учёного XVII века Марена Мерсенна. Для них есть особенно быстрая проверка на простоту. Но и здесь ловушка: показатель $p$ обязан быть простым, а вот обратное неверно. $2^2 - 1 = 3$, $2^3 - 1 = 7$, $2^5 - 1 = 31$, $2^7 - 1 = 127$ — простые, а $2^{11} - 1 = 2047 = 23 \cdot 89$.

Куда дальше

Попробуйте сократить дробь $\frac{391}{527}$. По числам не видно, на что они делятся: ни на $2$, ни на $3$, ни на $5$. Можно разложить оба на простые множители, как мы делали в этой главе, и найти общий. Для трёхзначных чисел это терпимо. Для двадцатизначных перебор делителей растянется на миллиарды делений, а числа в несколько сотен цифр не может разложить за разумное время даже компьютер.

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