§ 3.2. Существование разложения

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

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

Посмотрим, почему справедливо последнее утверждение. Пусть целое число, такое что Предположим, что наименьший делитель числа и пусть делитель числа По определению делимости, существуют такие

натуральные числа a и b, что

Значит, также является делителем числа Поскольку наименьший делитель должно выполняться неравенство но делит поэтому Эти неравенства означают, что Тем самым мы доказали, что если число делит то оно совпадает с Значит, простое.

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

Это утверждение легко проверить. Пусть Поскольку наименьший делитель числа имеем Теперь следовательно, откуда вытекает, что Другими словами, что мы и хотели доказать.

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

Еще одно замечание практического характера. Обозначим через целую часть вещественного числа а. Другими словами, наибольшее целое число, меньшее или равное а.

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

Ниже мы приводим запись алгоритма разложения в соответствии с канонической формой, предложенной в главе 2. Чтобы избежать излишней суеты, будем предполагать, что компьютер умеет вычислять значение

Алгоритм разложения путем деления методом проб

Ввод: натуральное число

Вывод: натуральное число наименьший простой делитель числа или сообщение о том, что простое.

Шаг 1. Положить

Шаг 2. Если целое, то сообщить: является делителем числа и завершить работу; в противном случае перейти к шагу 3.

Шаг 3. Увеличить F на единицу и перейти к шагу 4.

Шаг 4. Если то сообщить: простое», и завершить работу; в противном случае перейти к шагу 2.

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

Предположим, что в результате применения предыдущего алгоритма к мы нашли делитель этого числа. Тогда

его наименьший простой множитель. Применим тот же алгоритм к числу Предположим, что число составное и — его наименьший простой делитель. Ясно, что Заметим, однако, что эти делители могут оказаться равными. Такая возможность реализуется, если делится на Продолжая в том же духе, мы применяем алгоритм к и результате мы получаем последовательность простых чисел

каждое из которых является делителем числа Этой последовательности отвечает последовательность частных

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

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

Посмотрим на примере, как работает такой алгоритм. Допустим, мы хотим разложить число Алгоритм деления методом проб дает первый наименьший простой множитель 2. Повторное применение алгоритма, на этот раз к частному дает множитель 3. Значит, делитель 3 числа

225 является и делителем числа 450. Применим алгоритм к числу Вновь наименьшим делителем оказывается 3. Значит, 450 делится на Еще два выполнения алгоритма деления методом проб показывают, что 25 делится на 52, причем частное равно 1. Поэтому мы нашли полное разложение: