Евклид: простых чисел бесконечно много

Три книги из тринадцати

Книги VII, VIII и IX «Начал» посвящены числам, и это первое в истории систематическое изложение теории чисел. Числа у Евклида изображаются отрезками, а «измеряет» значит «делит нацело»; но содержание вполне узнаваемо.

VII.1–2: алгоритм Евклида. Чтобы найти наибольшую общую меру двух чисел, вычитаем меньшее из большего, пока не получим равные:

$$\gcd(a,b)=\gcd(b,\;a\bmod b),\qquad \gcd(a,0)=a.$$

Считается древнейшим нетривиальным алгоритмом, которым пользуются до сих пор без изменений. Пример: $\gcd(1071,462)$: $1071=2\cdot462+147$; $462=3\cdot147+21$; $147=7\cdot21+0$. Ответ 21.

Скорость его оценили только в 1844 году: Габриэль Ламе доказал, что число шагов не превосходит впятеро числа десятичных знаков меньшего аргумента, а худший случай достигается на соседних числах Фибоначчи — они дают самые длинные цепочки. Это, между прочим, первый в истории результат о вычислительной сложности.

VII.30 (лемма Евклида). Если простое $p$ делит произведение $ab$, то оно делит $a$ или $b$.

Здесь важна оговорка, которую учебники часто проглатывают. Основной теоремы арифметики — о существовании и единственности разложения на простые множители — у Евклида нет. Есть лемма VII.30 и предложение VII.31 (у всякого составного числа есть простой делитель), из которых она выводится; но саму формулировку и полное доказательство впервые даёт Гаусс в 1801 году. Две тысячи лет единственность разложения считали настолько очевидной, что не замечали, что она требует доказательства, — и заметили лишь тогда, когда Куммер обнаружил кольца, где она неверна.

IX.20: бесконечность простых

Знаменитое предложение звучит у Евклида так:

Простых чисел больше всякого предложенного количества простых чисел.

Четыре шага доказательства — и честная оговорка: само N простым быть не обязаноMathLocus · построено для этого сайта

Обратите внимание на формулировку. Слова «бесконечно много» здесь нет — греки актуальной бесконечности избегали. Сказано: сколько простых ни возьми, найдётся ещё.

Доказательство (по Евклиду). Пусть даны какие-то простые $p_1,\dots,p_k$. Рассмотрим

$$N=p_1p_2\cdots p_k+1 .$$

У числа $N$ есть простой делитель $q$ (по VII.31). Если бы $q$ совпало с каким-то $p_i$, то $q$ делило бы и произведение, и $N$, значит делило бы их разность, равную 1 — невозможно. Значит, $q$ — простое, отличное от всех взятых. $\blacksquare$

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

Сопутствующее заблуждение: будто $p_1\cdots p_k+1$ обязано быть простым. Это неверно уже на шестом шаге:

$$2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509 .$$

Утверждается лишь, что простой делитель этого числа — новый.

Через две с лишним тысячи лет Эйлер даст совершенно другое доказательство — аналитическое, из расходимости ряда $\sum 1/p$, — а Чебышёв и Риман превратят вопрос «сколько их?» в вопрос «как часто они встречаются?».

IX.36: совершенные числа

Число называется совершенным, если равно сумме своих собственных делителей: $6=1+2+3$, $28=1+2+4+7+14$.

Предложение IX.36. Если $2^{n}-1$ — простое, то $2^{n-1}(2^{n}-1)$ совершенно.

Доказательство. Пусть $q=2^{n}-1$ просто и $N=2^{n-1}q$. Делители $N$ — это $1,2,\dots,2^{n-1}$ и они же, умноженные на $q$. Сумма всех делителей:

$$\sigma(N)=(1+2+\cdots+2^{n-1})(1+q)=(2^{n}-1)\cdot 2^{n}=2N .$$

А $\sigma(N)=2N$ и означает совершенность. $\blacksquare$

Для $n=2,3,5,7$ получаем $6$, $28$, $496$, $8128$ — четыре совершенных числа, известных грекам.

Обратное утверждение — что всякое чётное совершенное число имеет такой вид — доказал Эйлер, и работа была издана посмертно, в 1849 году. Разрыв между половинками одной теоремы — больше двух тысяч лет; она так и называется: теорема Евклида — Эйлера.

А про нечётные совершенные числа не известно ничего до сих пор: ни одного не найдено, и не доказано, что их нет. Известно лишь, что если такое число существует, то оно больше $10^{1500}$ и имеет не менее десяти различных простых делителей. Это, вероятно, старейшая нерешённая задача математики — ей около 2300 лет.

Эратосфен: решето

В той же Александрии, полувеком позже, Эратосфен Киренский (ок. 276–194 до н. э.), заведующий Библиотекой, придумал способ выписывать простые числа подряд.

Выписываем $2,3,\dots,n$; берём первое невычеркнутое число, объявляем простым и вычёркиваем все его кратные; повторяем. Достаточно дойти до $\sqrt n$: у составного числа $m\leqslant n$ обязательно есть делитель, не превосходящий $\sqrt m\leqslant\sqrt n$.

Алгоритм не улучшен за 2200 лет: он и сегодня остаётся практически лучшим способом получить все простые до заданной границы, а число операций оценивается как $O(n\log\log n)$ — почти линейно, потому что $\sum_{p\leqslant n}1/p\approx\ln\ln n$.

Тот же Эратосфен, к слову, измерил окружность Земли по разнице длины теней в Сиене и Александрии, получив величину, отличающуюся от истинной на несколько процентов.

Задача. Покажите, что среди чисел вида $4k+3$ бесконечно много простых, повторив приём Евклида. (Указание: пусть $p_1,\dots,p_k$ — какие-то простые вида $4k+3$; рассмотрите $N=4p_1\cdots p_k-1$. Оно само имеет вид $4k+3$, значит, у него есть простой делитель вида $4k+3$ — произведение чисел вида $4k+1$ снова имеет вид $4k+1$. И этот делитель не входит в список.) Почему тот же приём не проходит для прогрессии $4k+1$?

Следующая точка: снова Александрия — где заведующий Библиотекой придумает, как выписывать простые подряд, и заодно измерит Землю.