этого школьников учат некоторым простым методикам работы с простыми числами, акцентируя внимание на вычислениях, где цифры относительно невелики. В результате наши первые впечатления от встречи с простыми числами, как правило, обманчивы.
Древние греки были знакомы с некоторыми базовыми свойствами простых чисел и знали, как их доказать. Простые числа и сомножители – основная тема Книги VII евклидовых «Начал», классического труда, посвященного геометрии. В этой книге имеется, в частности, геометрическое представление арифметических действий – деления и умножения. Греки предпочитали работать не с числами как таковыми, а с длинами линий (отрезков), но их результаты несложно переформулировать на языке чисел. Так, Предложение 16 Книги VII доказывает, что при перемножении двух чисел результат не зависит от того, в каком порядке берутся эти числа. Иными словами, ab = ba, фундаментальный закон алгебры.
В школьной арифметике простые делители используют для поиска наибольшего общего делителя двух чисел. К примеру, чтобы найти наибольший общий делитель чисел 135 и 630, мы раскладываем их на простые множители:
Затем берем все простые числа, которые присутствуют в обоих разложениях, в наибольшей общей степени; получаем 32 × 5. Перемножаем, получаем 45. Это и есть наибольший общий делитель. Из этой процедуры создается впечатление, что без разложения на простые множители невозможно найти наибольший общий делитель. На самом деле с точки зрения логики все наоборот. Предложение 2 Книги VII «Начал» представляет метод поиска наибольшего общего делителя двух натуральных чисел без разложения их на простые множители. Метод состоит в последовательном вычитании меньшего числа из большего, а затем остатка из меньшего числа и т. д. до тех пор, пока есть остаток. Для тех же чисел 135 и 630 – это достаточно типичный случай для небольших чисел – процесс выглядит так. Вычитаем 135 из 630 столько раз, сколько сможем:
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.
Эта процедура работает потому, что на каждой стадии происходит замена первоначальной пары чисел более простой парой (одно из чисел уменьшается), которая тем не менее имеет тот же наибольший общий делитель. В конце концов, одно из чисел делится на второе нацело, без остатка, и процесс поиска на этом завершается. В наше время подробное описание вычислительного метода, при помощи которого можно гарантированно найти ответ той или иной задачи, называют алгоритмом. Поэтому и процедура из «Начал» Евклида известна сегодня как евклидов
