ПРИЛОЖЕНИЕ Б. Доказательство основной теоремы арифметики

В настоящем приложении доказывается, что каждое натуральное число, отличное от 1, может быть разложено в произведение простых множителей лишь единственным способом, если отвлечься от порядка следования множителей. При этом понимается, что натуральное число, являющееся простым, как, например, 23, само является своим «разложением на простые множители». Рассматриваемое утверждение легко проверить для маленьких натуральных чисел. Например, 10 можно разложить в произведение 25, и по опыту мы знаем, что других разложений у 10 нет. То же самое верно и для всех чисел, меньших 10:

Этот список можно было бы продолжить, однако такое перечисление, как бы длинным оно ни было, не может рассматриваться как доказательство. В самом деле, натуральных чисел бесконечно много, и поэтому нельзя проверить разложение их всех.

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

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

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

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

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

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

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

Введенное обозначение требует еще дальнейших пояснений. Вовсе не имеется в виду, что, как это было в приложении есть лишь иное обозначение для простого числа — иное обозначение для простого числа 3 и т. д. Нам вообще неизвестно принадлежит или нет простое число 2 совокупности . Таким образом, может быть равным простому числу 2, или простому числу 23, или простому числу 47, или ни одному из них. Это есть попросту некоторое простое число. Точно так же есть некоторое простое число. Оно может как совпадать, так и не совпадать с . Единственное, что мы предполагаем — это возможность разложить натуральное число на простые множители двумя различными способами.

Доказательство. Часть I. Покажем, что все простые числа из первой совокупности отличны от всех простых чисел из второй совокупности. Таким образом, если, например, простое число 7 принадлежит первой совокупности, то оно не может принадлежать второй совокупности. Поскольку это вовсе не очевидно, мы должны дать соответствующее доказательство. Предположим, что имеется простое число, принадлежащее обеим совокупностям. Изменив, если нужно, обозначения, мы можем считать, что совпадают первые числа обеих совокупностей, т. е. что (Это можно сделать, поскольку в каждом разложении простые числа могут находиться в любом порядке.) Заменяя во втором разложении на мы получаем, что имеются следующие два разложения:

Деля эти равенства на находим

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

Часть II. Итак, нами установлено, что все простые числа из первого разложения отличны от всех простых чисел из второго разложения т. В Частности, не равно что можно записать как . Предположим, что есть наименьшее из чисел т. е. что . Мы вправе это сделать в силу полной симметрии обозначений в обеих совокупностях простых чисел. Таким образом, если мы проведем доказательство в случае то по симметрии аналогичное доказательство применимо к случаю с , замененными на q, и наоборот.

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

Обратим внимание на то, как строится число : оно равно произведению и простых чисел Его можно записать в виде разности:

или

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

Установим, наконец, что натуральное число имеет два различных разложения. Для этого рассмотрим в той его форме, в которой оно было введено, а именно:

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

где b есть частное от деления на Но из этого равенства следуют равенства

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

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

Заменяя в нем по формуле

получаем

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

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