8. Разложение натурального числа на простые сомножители

Опираясь на теорему 1, докажем следующую рему.

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

Доказательство. Пусть данное натуральное число Согласно теореме 1, число имеет (по крайней мере один) простой делитель и мы можем предположить, что есть наименьший простой делитель числа . Итак, имеем где — натуральное число.

Если то является произведением, составленным только из одного простого сомножителя. Если же то имеет простой делитель о котором мы можем предположить, что он есть наименьший простой делитель числа . Одновременно он является простым делителем числа причем определения числа следует, что

Таким образом, и либо и тогда есть произведение двух простых чисел (не обязательно разных), либо и тогда с числом мы можем поступить, как ранее с числами и т. д. Так как то имеем Аналогично найдем, что Поэтому натуральные числа образуют убывающую последовательность, которая не может содержать более чем членов. Следовательно, при некотором натуральном число

будет последним членом этой последовательности. Но в таком случае ибо в случае мы могли бы положить

и получили бы дальнейший член нашей последовательности. Итак, имеем , откуда найдем

где простые числа, причем можно предполагать, что (если для каждого из чисел мы будем определять его наименьший простой делитель).

Среди сомножителей произведения (1) могут быть равные. Формулу (1) можно записать в виде:

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

Формула (2) называется каноническим разложением числа на простые сомножители.

Итак, мы не только доказали теорему 4, но и указали способ нахождения для каждого натурального числа его канонического разложения на простые сомножители. Таким образом, нахождение этого разложения для любого данного натурального числа теоретически всегда возможно. Однако на практике оно может потребовать проведения утомительных вычислений, которые для некоторых чисел оказываются столь длинными, что в настоящее время их невозможно осуществить даже при помощи самых лучших вычислительных машин. Например, мы не знаем разложения на простые сомножители числа 2101 — 1 (имеющего 31 цифру); доказано только, что оно является произведением двух различных простых сомножителей, меньший из которых (впрочем, до сих пор неизвестный) имеет не менее 11 цифр. Мы не знаем также разложения на простые сомножители числа о котором неизвестно даже, является ли оно простым или нет. Зато для числа имеющего более

чем цифр , откуда несколько лет назад был найден наименьший простой делитель. Этим делителем является число имеющее 587 цифр. Но мы не знаем разложения числа на простые сомножители и даже не знаем других простых делителей этого числа (см. § 22).

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

Теорема 5. Простое число имеет только два натуральных делителя

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

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

Таким образом, имеет место

Теорема 6. Для того чтобы натуральное число было простым, необходимо и достаточно, чтобы оно имело точно два натуральных делителя (очевидно, единицу и самого себя).

Докажем теперь следующую теорему.

Теорема 7. Если а и натуральные числа и произведение делится на простое число то по крайней мере одно из чисел а и делится на

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

Далее, поскольку делится на имеем где натуральное число, большее 1, так как иначе было бы где (ибо числа а и не делятся на

С другой стороны, на основании неравенства получаем Число I, будучи натуральным числом имеет простой делитель Учитывая теперь определение числа а также то, что произведение делящееся на I, делится также на простое число мы заключим, что хотя бы один сомножителей а и должен делиться на Если, например, а делится на то Но I делится на следовательно, где натуральное число. А так как то откуда причем, учитывая, что имеем откуда что противоречит предположению относительно произведения Итак, предположение о том, что теорема 7 неверна, приводит к противоречию.

Из доказанной теоремы при помощи индукции можно получить следующее

Следствие. Если — натуральные числа, произведение которых делится на простое число то по крайней мере одно из чисел должно делиться на

Доказательство. Это следствие справедливо для Предположим, что оно справедливо для чисел, и пусть числа являются

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

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

обладает разложением

где возрастающая последовательность простых чисел, числа натуральные. Согласно (2), число делится на и поэтому, в силу (3) и следствия теоремы 7, но крайней мере одно из чисел должно делиться на Очевидно, это будет число так как наименьший простой делитель числа (3). Но, согласно теореме 5, простое число имеет только два натуральных делителя: поскольку же простое число также является делителем числа то должно быть Заменив в формуле на мы, ввиду (2), получим для числа и, где следующее равенство:

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

Итак, доказана

Теорема 8. Каждое натуральное число дает только одно разложение на простые сомножители, если не обращать внимания на порядок сомножителей.