Аксиоматика натуральных чисел содержание

Основная теорема арифметики

В предыдущем пунк­те было доказано, что любое составное число представимо в ви­де произведения простых. В качестве примера мы разложили на множители число 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 >= р². Аналогично n>= р'². Так как р и р' не одинаковы, то по крайней мере одно из этих нера­венств строгое и, следовательно, рр' < n. Рассмотрим теперь число n-рр'. Это натуральное число меньше n, следовательно, оно может быть представлено как произведение простых одним и только одним способом. Так как р делит n, оно делит так­же n-рр', поэтому, согласно сделанному ранее замечанию, р должно входить в разложение n-рр'. Аналогично убеждаем­ся, что в это разложение должно входить и р'. Следовательно, разложение n-рр' на простые имеет вид
n - рр' = pp'QR...,
где Q, R, ... простые. Отсюда следует, что число рр' делит n. Но n=рqr..., поэтому (после сокращения на р) получает­ся, что р' делит qr ... . Ввиду предварительного замечания это невозможно, ибо qr ... — число, меньшее n, и р' не является одним из простых q, г, ..., входящих в его разложение. Это противоречие доказывает, что n обладает только одним разло­жением на простые множители.
Основная теорема арифметики вскрывает структуру нату­ральных чисел по отношению к операции умножения. Эта те­орема показывает, что все натуральные числа получаются из простых с помощью всевозможных умножений, причем в ре­зультате различных умножений получаются различные числа. Теперь понятно, что число 1 неудобно считать простым, ибо это нарушило бы единственность разложения на простые множите­ли: к любому произведению можно присоединить множителем 1, не изменив значения этого произведения.