§ 2. Единственность разложения на простые множители

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

168 простых чисел между 1 и 1000,

135 простых чисел между 1000 и 2000,

127 простых чисел между 2000 и 3000,

120 простых чисел между 3000 и 4000,

119 простых чисел между 4000 и 5000.

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

Каждое натуральное число, кроме числа 1, либо простое, либо может быть разложено на простые множители.

Рассмотрим, например, натуральное число 94 860. Оно, очевидно, не простое, поскольку

Кроме того, 9486 делится на 2, а также на 3 и, более того, на 9. Следовательно, можно написать

Если бы число 527 было простым, то это выражение было бы разложением 94 860 на простые множители. Но 527 не является простым, поскольку 527=17х31. Разложение числа 94 860 на простые множители имеет, таким образом, вид

Мы рассмотрели определенное число 94 860; но тот же самый процесс применим к любому натуральному числу п. Действительно, либо простое число, либо — не простое. Если оно не простое, то его можно разложить в произведение двух меньших чисел, скажем, а и . Каждое из чисел а, b в свою очередь либо простое, либо может быть разложено в произведение еще меньших чисел. Продолжая этот процесс, мы в конце концов получим разложение на простые множители.

В первой фразе предыдущего абзаца простые числа выделяются из множества всех других натуральных чисел. В математике часто желательно делать определения настолько общими, чтобы становилось ненужным выделение отдельных случаев. Под «разложением на простые множители», например, понимается разложение числа, скажем 12, в произведение нескольких простых чисел, в нашем случае . Обобщим теперь понятие «разложение на простые множители» таким образом, чтобы оно включало случай единственного множителя. При этом, например, простое число 23 будет иметь разложение на простые множители, состоящее из единственного множителя 23. Используя это обобщенное понимание «разложения на простые множители», наше первоначальное утверждение можно заменить на следующее: «Каждое натуральное число, отличное от числа 1, может быть разложено на простые множители».

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

Одним из фундаментальных результатов математики является тот факт, что разложение натурального числа на простые множители единственно. Например, для числа 94 860 не существует иного разложения, кроме приведенного выше. Порядок множителей, конечно, может быть различным, так, например, можно также написать

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

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

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

Приведенная выше формулировка основной теоремы арифметики объясняет одну из причин, почему число 1 не включено в совокупность простых чисел.

Именно если число 1 считать простым, то можно было бы написать, например,

т. е. число 35 (равно как и любое другое натуральное число) разлагалась бы в произведение простых множителей более чем одним способом. Конечно, основная теорема арифметики по-прежнему была бы верна, однако ее формулировка потребовала бы больше оговорок типа «за исключением...» или «если не...». Таким образом, исключение числа 1 из совокупности простых чисел позволяет формулировать результаты короче и изящнее.