630 − 135 = 495;
495 − 135 = 360;
360 − 135 = 225;
225 − 135 = 90.
Поскольку 90 < 135, переходим к той же процедуре с участием чисел 90 и 135:
135 − 90 = 45.
Поскольку 45 < 90, продолжаем то же с числами 45 и 90:
90 − 45 = 45;
45 − 45 = 0.
Таким образом, наибольший общий делитель чисел 135 и 630 равен 45.
Эта процедура работает потому, что на каждой стадии происходит замена первоначальной пары чисел более простой парой (одно из чисел уменьшается), которая тем не менее имеет тот же наибольший общий делитель. В конце концов, одно из чисел делится на второе нацело, без остатка, и процесс поиска на этом завершается. В наше время подробное описание вычислительного метода, при помощи которого можно гарантированно найти ответ той или иной задачи, называют алгоритмом. Поэтому и процедура из «Начал» Евклида известна сегодня как евклидов алгоритм. Логически эта процедура первична по отношению к процедуре разложения на простые множители. В самом деле, Евклид использует ее для доказательства основных свойств простых делителей. В современных университетских курсах математики алгоритм Евклида используется с той же целью.
Описанная процедура целиком опирается на евклидово Предложение 30 и была бы невозможна без него. В современных терминах речь в нем идет о том, что если произведение двух чисел — то, что мы получаем при их перемножении — делится на некое простое число, то на это же число должен делиться один из сомножителей. Предложение 32 заключается в том, что любое число либо само является простым, либо имеет простой делитель. Объединив оба утверждения, несложно сделать вывод, что любое число есть результат перемножения простых множителей и что их набор единственный, если не брать во внимание порядок записи. К примеру,
и т. д., но единственный реальный способ получить 60 состоит в том, чтобы взять множители из первого разложения и переставить их местами. Не существует, к примеру, разложения, в котором 60 = 7 × что-нибудь. Существование какого-нибудь разложения следует из Предложения 32. Если число простое — стоп. Если нет, находим простой делитель, делим на него, получая меньшее число, и повторяем процедуру. Уникальность набора делителей следует из Предложения 30. Так, если бы разложение 60 = 7 × что-нибудь существовало, то одно из чисел 2, 3 и 5 должно было бы тоже делиться на 7, но этого не происходит.
Здесь я должен прояснить один небольшой, но важный момент: исключительный статус числа 1. Согласно приведенному выше определению, оно простое: если мы попытаемся разбить его на множители, максимум, что мы получим, будет 1 = 1 × 1, где нет меньших чисел. Однако позже, с развитием теории, такая интерпретация вызывает проблемы, поэтому в последние век-два математики добавили в определение простого числа дополнительное ограничение. Число 1 настолько отличается от всех остальных чисел, что его следует рассматривать как исключение, — это не простое число, но и не составное. Это третья разновидность числа — единица. Одна из причин, по которым мы называем 1 особым случаем, а не относим ее к настоящим простым числам, заключается в том, что если мы согласимся с простотой единицы, то единственность набора множителей нарушится. Вообще-то 1 × 1 = 1 — уже нарушение, а уж 1 × 1 × 1 × 1 × 1 × 1 × 1 × 1 = 1 ни в какие ворота не лезет. Можно было бы изменить определение единственности и сказать «единственный, без учета дополнительных единичных множителей», но это был бы всего лишь другой способ признать, что 1 — число особое.
Много позже, в Предложении 20 Книги IX, Евклид доказывает еще один ключевой факт: «Простых чисел существует больше, чем их насчитывается в любом множестве простых чисел». Иными словами, множество простых чисел бесконечно. Это чудесная теорема и изящное доказательство, но ее появление вызвало множество проблем. Если простые числа уходят в бесконечность, но, судя по всему, расположены без всякой системы, то как можно сказать, на что они похожи?
Мы вынуждены обратиться к этому вопросу потому, что не можем оставить в стороне простые числа — очень существенную деталь математического ландшафта. Особенно часто они встречаются (и особенно полезны) в теории чисел — разделе математики, изучающем свойства целых чисел. Звучит, может быть, достаточно элементарно, но на самом деле теория чисел — один из самых глубоких и сложных разделов математики. Позже мы увидим тому множество свидетельств. В 1801 г. Гаусс, ведущий специалист того времени по теории чисел (а также, по мнению некоторых ученых, один из ведущих математиков всех времен, а может быть, и величайший из них), написал продвинутый учебник по этой теории — «Арифметические исследования» (Disquisitiones Arithmeticae). В нем среди множества сложных тем Гаусс указал, что не следует терять из виду два весьма фундаментальных вопроса: «Известно, что задача отличения простых чисел от составных и разложения последних на простые множители является одной из важнейших и полезнейших в арифметике».