В предыдущем пункте было доказано, что любое составное число представимо в виде произведения простых. В качестве примера мы разложили на множители число 666: 666 = 2 • 3 • 3 • 37. Обратимся теперь к другому вопросу, также имеющему первостепенное значение. Можно ли осуществить разложение на простые более чем одним способом? (Понятно, конечно, что два представления, отличающиеся только порядком множителей, должны рассматриваться как одно, например разложение 3 • 2 • 37 • 3 отождествляется с разложением 2 • 3 • 3 • 37.) Может ли, например, число 666 иметь какое-нибудь другое представление в виде произведения простых? Читатель, не знающий теории чисел, вероятно, будет все же уверен, что другого такого представления нет, однако найти слишком простое общее доказательство ему не удастся.
Было бы удобно высказать это предложение в форме, применимой ко всем натуральным, а не только к составным числам. Будем рассматривать простые числа как «произведения» простых, состоящие только из одного сомножителя. Можно сделать еще один шаг и рассматривать число 1 как пустое произведение простых, считая по определению, что величина пустого произведения равна 1. Это соглашение полезно не только здесь, но и в других частях математики, так как оно дает возможность включать в общие теоремы частные случаи, которые иначе пришлось бы исключить или рассматривать особо.
При этих соглашениях общее предложение таково: каждое натуральное число может быть представлено в виде произведения простых одним и только одним способом. Эту теорему называют основной теоремой арифметики; она имеет довольно странную историю. В «Элементах» Евклида она еще не встречается, но некоторые арифметические предложения в книге VII уже эквивалентны ей. Точно она не формулируется даже во «Введении в теорию чисел», написанном в 1798 году Лежандром. Первую точную формулировку теоремы и ее доказательство дал Гаусс в 1801 году в своих знаменитых «Арифметических исследованиях». Приведем здесь прямое доказательство единственности разложения на множители.
Заметим, прежде всего, что если разложение числа m на простые множители единственно, то каждый простой множитель m должен входить в это разложение. Действительно, пусть р — какое-нибудь простое, делящее m, тогда m= рm', где m' — некоторое целое число; разложение m можно получить из разложения m', добавив простой множитель р. Так как по предположению имеется только одно разложение числа m на простые, то р должно встретиться в нем.
Будем доказывать единственность разложения по индукции, именно: докажем единственность разложения числа n в предположении, что единственность разложения для всех чисел, меньших n, уже установлена. Если n простое, то доказывать нечего. Предположим, что n составное и имеются два различных представления n в виде произведения простых, скажем,
n = pqr • • • = p'q'r'...,
где р, q, r,... и р', q', r',... - простые. Одно и то же простое не может встретиться в двух разложениях, так как в этом случае мы сократили бы на это простое и получили бы два различных разложения меньшего числа, а это противоречит индуктивному предположению.
Не нарушая общности, можно предполагать, что р - наименьшее из простых, встречающихся в первом разложении. Так как n составное, имеется по меньшей мере один множитель в разложении, помимо р; поэтому n >= р2. Аналогично n>= р'2. Так как р и р' не одинаковы, то по крайней мере одно из этих неравенств строгое и, следовательно, рр' < n. Рассмотрим теперь число n-рр'. Это натуральное число меньше n, следовательно, оно может быть представлено как произведение простых одним и только одним способом. Так как р делит n, оно делит также n-рр', поэтому, согласно сделанному ранее замечанию, р должно входить в разложение n-рр'. Аналогично убеждаемся, что в это разложение должно входить и р'. Следовательно, разложение n-рр' на простые имеет вид
n - рр' = pp'QR...,
где Q, R,... простые. Отсюда следует, что число рр' делит n. Но n=рqr..., поэтому (после сокращения на р) получается, что р' делит qr.... Ввиду предварительного замечания это невозможно, ибо qr... — число, меньшее n, и р' не является одним из простых q, г,..., входящих в его разложение. Это противоречие доказывает, что n обладает только одним разложением на простые множители.
Основная теорема арифметики вскрывает структуру натуральных чисел по отношению к операции умножения. Эта теорема показывает, что все натуральные числа получаются из простых с помощью всевозможных умножений, причем в результате различных умножений получаются различные числа. Теперь понятно, что число 1 неудобно считать простым, ибо это нарушило бы единственность разложения на простые множители: к любому произведению можно присоединить множителем 1, не изменив значения этого произведения.