2.3. Разложение целых чисел на множители

Среди всех задач теории чисел, при решении которых применялся компьютер, ни одна другая, по-видимому, не имела такого

значения, как задача разложения на множители (факторизации). Из-за того, что эта задача является одной из основных в теории чисел и при этом просто формулируется, она привлекала людей еще в античности (Dickson, 1952). В самой простой формулировке: пусть нам дано целое число и требуется, если это возможно, найти два целых числа a и b, таких, что На самом деле здесь имеются две различные задачи: первая, называемая тестом на простоту, — это проверка того, существуют ли такие a и b, вторая, называемая разложением, — это задача их нахождения. В этой части мы рассмотрим обе эти задачи и попутно введем дополнительные математические понятия, которые нам понадобятся в дальнейшем.

2.3.1. Простые числа и решето Эратосфена

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

Теорема 2.3.1 (существование неприводимого разложения). Всякое ненулевое целое число может быть записано как ± произведение конечного числа положительных неразложимых целых чисел, , где для и неразложимы.

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

Например, Является ли это разложение единственным, т. е. можно ли записать 1008 как произведение других неразложимых чисел? Перед тем как мы сможем ответить на этот вопрос, нам понадобится следующее определение. Целое число называется простым, если для любых а, b из того, что следует, что или Следующее предложение характеризует простые числа как положительные неразложимые элементы. Доказательство этого предложения иллюстрирует способ рассуждений, который потребуется для выполнения некоторых упражнений этой части книги.

Предложение 2.3.2. Целое число является простым тогда и только тогда, когда оно неразложимо.

Доказательство. Предположим, что просто и что а ; нужно показать, что а — тривиальный делитель. Запишем для некоторого b. Поскольку просто, а или . Если , то (см. упр. 2 разд. 2.2.1). Если , то для некоторого с и что влечет за собой поэтому . Итак, мы показали, что всякий делитель числа тривиален, следовательно, неразложимо. Обратно, предположим, что неразложимо и что Если не делит а, то поскольку не имеет положительных делителей, отличных от . По теореме 2.2.3 существуют х и у, такие, что Умножив это равенство на , получим и, так как делит левую часть, . Мы показали, что, если не делит а, то , следовательно, просто.

Теорема 2.3.3 (единственность неприводимого разложения). Всякое ненулевое целое число может быть записано как ± произведение простых чисел только одним способом, с точностью до порядка сомножителей.

Доказательство. Предположим, что положительное целое число а записано в виде где положительны и неразложимы и, следовательно, просты. Имеем и, так как «1 просто, для некоторого Поскольку не имеет нетривиальных делителей, Продолжая, получаем, что «2 делит произведение оставшихся и, следовательно, для некоторого и так далее. В конце концов мы получим, что и после некоторого переупорядочивания - для всех

Теорему 2.3.3 называют основной теоремой арифметики. Исторически математики рассматривали теорему 2.3.3 как «данную

свыше», однако существуют математические системы, в которых утверждение о единственности разложения не выполняется. В качестве примера такой системы рассмотрим множество Е, элементами которого являются положительные четные числа Отметим, что Е замкнуто относительно умножения. Предположив, что все числа, которые мы знаем, являются элементами Е, мы видим, что 8 = 2•4 - «составное» число, тогда как 14 — «простое», поскольку оно не является произведением двух или более «чисел»; более того, число 840 имеет два разложения на «простые» числа, а именно поэтому теорема о единственности разложения не выполняется.

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

Объединенные вместе, теоремы 2.3.1 и 2.3.3 утверждают, что всякое ненулевое целое число может быть однозначно представлено как произведение конечного числа простых сомножителей (единственность с точностью до порядка сомножителей). Это представление числа известно под названием разложение числа а в произведение степеней простых чисел, которое записывается так:

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

В качестве первого применения приведенных выше результатов выразим d, наибольший общий делитель чисел а и b, в терминах простых сомножителей чисел a и b.

Пусть

где . Тогда, поскольку если и только если , наибольший общий делитель чисел a и b выражается в виде

где, как обычно, обозначает наименьшее из чисел, стоящих в скобках. Аналогично, наименьшее общее кратное чисел a и b выражается в виде

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

а также равенство , мы можем легко получить результат теоремы .

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

Теорема — иррациональное число.

Доказательство. Допустим, что существуют два натуральных числа a и b, такие, что . Тогда, используя разложение в произведение степеней простых чисел, мы видим, что в левую часть равенства простой множитель 2 входит с нечетной степенью, а в правую — с четной, что невозможно.

Теорема 2.3.5 (Евклид). Существует бесконечно много простых чисел.

Доказательство. Предположим противное. Пусть существует лишь конечное число простых чисел . Рассмотрим число которое либо является простым, и тогда оно будет новым простым числом, либо имеет простой сомножитель . (Отметим, что первые несколько чисел такого вида просты; например, Однако Если бы было одним из перечисленных простых чисел , то делило бы произведение и, поскольку делит оно делило бы и разность этих чисел, т.е. единицу, что невозможно. Поэтому должно быть новым простым числом.

Теорема 2.3.6. Для произвольного положительного целого числа существуют последовательных (т.е. отличающихся на единицу) составных чисел. Другими словами, в последовательности простых чисел существуют сколь угодно большие промежутки.

Доказательство. Рассмотрим числа где . Очевидно, каждое из этих чисел составное, потому что делится на , когда

Как мы уже говорили, два целых числа тип называются взаимно простыми, если заметим, что не обязаны быть простыми, как, например, в случае 9 и 14. Для заданного через обозначается количество положительных целых чисел таких, что называется функцией Эйлера. Заметим, что для всякого простого числа мы имеем Например, потому что все целые числа 1, 2, 3 и 4 взаимно просты с числом 5.

Выведем формулу, которая выражает в терминах разложения в произведение степеней простых чисел;

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

Читатель может проверить, что эту формулу можно записать в виде

Пример. Для того чтобы вычислить разложим сначала 60 в произведение степеней простых чисел: Затем, применив нашу формулу, получим

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

Для того чтобы найти все простые числа , запишем по порядку все целые числа от 2 до . Затем вычеркнем все четные числа, кроме 2, поскольку они делятся на 2 и потому не являются простыми. Потом вычеркнем все числа, кратные 3, и так далее. После прохода будут вычеркнуты все числа, которые делятся на первые простых чисел Первое число которое останется невычеркнутым, будет простым числом. (Почему?) Затем будут вычеркнуты все числа, кратные и процесс остановится, когда в списке не останется невычеркнутых чисел, которые больше последнего найденного простого числа. Целые числа, которые остались в списке, прошли сквозь решето и являются простыми п.

В следующем примере мы найдем все простые числа 60, в исходный список включены только нечетные числа 2:

Числа, кратные зачеркнуты символом кратные — символом и кратные — символом Следующее после 7 простое число — это 11, но поэтому по причине, которая будет объяснена ниже, процесс останавливается, и невычеркнутые числа являются простыми 60. (См. также (Dudley, 1983) и (Mills, )

Мы можем использовать этот метод для проверки простоты заданного числа , которая зависит от того, будет ли оно вычеркнуто. Приведенная выше процедура может быть сделана более эффективной, если учитывать, что у составного числа обязательно есть простой делитель (Причина в том, что

делители всегда составляют пары; если число имеет делитель, больший, чем квадратный корень из него, оно также должно иметь делитель, меньший чем этот корень.) Поэтому при вычеркивании чисел, кратных мы можем рассматривать только простые числа и процесс остановится, когда для некоторого t. Однако, несмотря на это ускорение, приведенный метод не подходит для проверки наибольших из известных простых чисел. Например, для проверки -значного числа , простота которого была доказана в 1979 г., компьютеру, выполняющему миллион операций в секунду, потребовалось бы лет для завершения работы, если бы он остановился только при достижении квадратного корня числа.

Для некоторых последующих приложений нам нужно уметь находить наибольших простых чисел М, где М — максимальное целое число, представимое аппаратно на имеющемся в нашем распоряжении компьютере. Например, обычные размеры компьютерного слова — это 16 или 32 бита, и, отбрасывая знаковый бит, получаем, что наибольшие целые числа, представимые в таких машинах, равны соответственно. Для нахождения таких простых чисел построим сначала таблицу простых чисел используя метод решета. Кратные каждого из этих простых чисел затем вычеркиваются из списка , где интервал достаточно велик для того, чтобы содержать как минимум простых чисел. Целые числа, оставшиеся невычеркнутыми, будут простыми.

Для того чтобы этот метод можно было реализовать практически, список простых чисел М должен быть не слишком велик и нужно выбрать интервал который содержал бы по крайней мере простых чисел и был бы не слишком большим для небольшого . Замечательная теорема о количестве простых чисел может быть использована для решения обеих этих задач ((Erdoes, 1949; Goldstein, 1973; Levinson, 1969), см. также историческое замечание 3.) Пусть обозначает количество простых чисел из примера с решетом, рассмотренного выше, мы видим, что . В теореме утверждается, что . Для больших величина аппроксимирует на самом деле это оценка снизу. Грубо говоря, теорема утверждает, что из каждых чисел одно является простым. Таким образом, интервал, достаточно превышающий по длине , должен содержать простых чисел. Далее, размер таблицы простых чисел примерно равен Если то для -битной машины

поэтому, скорее всего, хватит интервала длины 200. Таблица простых чисел должна содержать около простых чисел. В действительности Для -битной машины поэтому возьмем интервал длины 500. Размер таблицы простых чисел — примерно Настоящий размер равен Следующий алгоритм объединяет сформулированные выше соображения.

GENPR. Генерация простых чисел (Generate Primes)

Вход: Два целых числа одинарной точности и одномерный массив А длины — нечетное целое число 3.

Выход: Простые числа одинарной точности, лежащие в замкнутом отрезке

1. [Инициализация] для к выполнять

2. [Если то получить простые числа и закончить работу] Если то перейти к шагу 6.

3. [Вычислить наименьшее положительное число j, такое, что если четно, то если нечетно, то если m d, то

4. [Вычеркивание составных] Для пока выполнять

5. [Изменение d] Если то иначе перейти к шагу 2.

6. [Получить простые числа] Для выполнять то выдать простое число закончить работу.

Анализ времени работы алгоритма GENPR. Все арифметические операции в алгоритме выполняются с короткими числами, следовательно, каждая операция выполняется за время порядка

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

Шаги от 2 до 5 образуют цикл, для которого, как можно видеть из описания шага 2, число где является верхней оценкой количества повторений. Кроме того, при каждом выполнении тела цикла шаг 4 включает не более к операций, а

шаги 2, 3 и 5 — одну или две операции. Поэтому весь цикл выполняется за время

Объединяя эти результаты и учитывал, что получаем

где

Пример. С помощью предыдущего алгоритма найдем все простые числа между 3 и 21 (т.е. в случае

После первого шага На шаге 2 условие окончания не выполняется, поэтому мы производим шаг 3, где мы получаем (поскольку ). На шаге 4 мы изменяем массив А, присваивая и на шаге 5 мы изменяем d, присваивал Этим завершается первое выполнение цикла, который включает шаги от 2 до 5.

В начале второго выполнения цикла проверка условия окончания оказывается успешной, и мы переходим к шагу 6. На шаге 6 для мы ничего не выдаем, поскольку однако для поэтому мы выдаем простое число 19, и так далее. Таким путем будут выданы простые числа 19, 17, 13, 11, 7, 5 и 3.