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

При этих соглашениях общее предложение таково: каждое натуральное число может быть представлено в виде произведения простых одним и только одним способом. Эту теорему называют основной теоремой арифметики; она имеет довольно странную историю. В «Элементах» Евклида она еще не встречается, но некоторые арифметические предложения в книге vn уже эквивалентны ей. Точно она не формулируется даже во «Введении в теорию чисел» написанном в 1798 году Лежандром. Первую точную формулировку теоремы и ее доказательство дал Гаусс в 1801 году в своих знаменитых «Арифметических исследованиях». Вероятно, из-за отсутствия этой теоремы у Евклида она принимается без доказательства во многих школьных учебниках. В одном из учебников ее даже объявляют «законом мышления», каковым она, конечно, не является. Приведем здесь прямое доказательство единственности разложения на множители. Позднее (в п. 7) будет дано другое доказательство, полностью независимое от рассматриваемого в этом пункте.

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

Будем доказывать единственность разложения по индукции, именно: докажем единственность разложения числа п в предпо-

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

п = pgr ... = pqr...,

где р ,,, и р, q г, . • • ~ простые. Одно и то же простое не может встретиться в двух разложениях, так как в этом случае мы сократили бы на это простое и получили бы два различных разложения меньшего числа, а это противоречит индуктивному предположению.

Не нарушая обш;ности, можно предполагать, что р - наименьшее из простых, встречаюш;ихся в первом разложении. Так как п составное, имеется по меньшей мере один множитель в разложении, помимо р; поэтому р. Аналогично р. Так как р и р ие одинаковы, то по крайней мере одно из этих неравенств строгое и, следовательно, рр < п. Рассмотрим теперь число п - рр. Это натуральное число меньше п, следовательно, оно может быть представлено как произведение простых одним и только одним способом. Так как р делит п, оно делит также п - рр поэтому, согласно сделанному ранее замечанию, р должно входить в разложение п - рр. Аналогично убеждаемся, что в это разложение должно входить и р. Следовательно, разложение п - рр на простые имеет вид

п- рр = ppQR...,

где ,,, - простые. Отсюда следует, что число рр делит

п. Но п = pqr..., поэтому (после сокраш;ения на р) получается, что р делит qr ,,. . Ввиду предварительного замечания это невозможно, ибо qr,.. - число, меньшее п, и р не является одним из простых q г, ..., входягцих в его разложение. Это противоречие доказывает, что п обладает только одним разложением на простые множители.

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

следует из определения простого, доказательство единственности разложения получается не сразу. Следуюгций пример, указанный Гильбертом, объясняет, почему эти два предложения так отличаются друг от друга. Определения множителей и простых используют лишь операцию умножения и не зависят от операции сложения. Посмотрим, что произойдет, если применить эти определения к системе чисел, замкнутой относительно умножения, но не замкнутой относительно сложения и вычитания. Рассмотрим систему всевозможных чисел вида Ах + 1:

1, 5, 9, 13, 17, 21, 25, 29, ... Произведение двух таких чисел снова является числом того же вида. Определим «псевдопростое» как число этой системы (отличное от 1), которое не разлагается собственно в этой системе. Числа 5, 9, 13, 17, 21 являются псевдопростыми; а 25 есть первое не псевдопростое число. Каждое число этой системы либо само псевдопростое, либо может быть разложено на псевдопростые множители, - это доказывается так же, как и раньше. Но в этой системе разложение числа на псевдопростые не является однозначным; например, число 693 имеет два разложения:

693 = 9 • 77 = 21 . 33,

где все числа 9, 77, 21, 33 - псевдопростые. Конечно, ясно, что эти числа можно разложить на множители вне рассматриваемой системы; точка зрения примера проливает свет на логическую структуру любого доказательства единственности разложения на множители. Такое доказательство не может опираться лишь на определение простого и свойства мультипликативных операций. Оно должно где-то использовать сложение или вычитание, ибо иначе его можно было бы применить к только что рассмотренной системе чисел. В приведенном доказательстве фундаментальной теоремы вычитание использовалось при образовании числа п - рр.

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