Я писал недавно о том, почему эта теорема кажется тривиальной и очевидной, и почему этот взгляд ошибочен. Теперь напишу о том, как доказывают эту теорему. Эта запись требует некоторых математических знаний - например, я не буду объяснять, что такое доказательство по индукции.
У ОТА (Основной Теоремы Арифметики) есть две части: существование разложения на простые множители, и его единственность. Существование доказать тривиально по индукции, и тут проблем или вариантов нет. Предположим, что мы уже доказали существование для всех чисел меньше n. Если n простое, то оно само себе разложение, доказывать нечего. Иначе n = a*b, где a и b какие-то числа меньше его. По предположению индукции у каждого из них есть разложение; соединяя эти разложения вместе, получаем разложение для n.
Единственность - это нетривиальная часть ОТА. Нам нужно доказать, что если n = p1*p2*...*pk = q1*q2*...*qs - два разложения числа n, то числа p должны быть на самом деле равны числам q, разве что расположены в другом порядке. Для начала отметим, что достаточно доказать, что не может быть двух разложений, в которых ни одно p не равно ни одному q, т.е. у разложений нет общих простых множителей. Этого случая достаточно, потому что если у двух разных разложений есть общие множители, на них всегда можно поделить, и убрать их с обеих сторон, пока не останутся два разных разложения числа поменьше без общих множителей, а такого (как мы докажем) не может быть.
Итак, предположим, что ни одно p не равно ни одному q. На этом месте доказательства ОТА делятся на две группы: те, которые доказывают с помощью леммы Евклида, и те, которые доказывают напрямую по индукции.
Лемма Евклида гласит следующее: если простое число p делит произведение a*b (p|a*b), то p делит отдельно a или b (или оба): p|a или p|b. Эта лемма была известна Евклиду и появляется именно в таком виде в 7-й книге его Начал.
Предположим, мы доказали лемму Евклида; единственность разложение в ОТА следует из нее немедленно следующим образом. p1 делит все число n = q1*q2*...*qs, значит (применяя лемму Евклида много раз), оно должно делить какое-то qi. Поскольку мы предполагаем, что p1 не равно ни одному qi, и они разные простые числа, это невозможно. Так что главная работа в этом подходе - доказать лемму Евклида.
Почти во всех учебниках теории чисел, алгебры итд. ОТА доказывают именно так, через лемму Евклида. Но есть и другой подход, напрямую по индукции, который приводится в некоторых учебниках теории чисел. Полагаю, что он не очень популярен, потому что подход через лемму Евклида обобщается до гораздо более широкого класса структур: колец главных идеалов, в которых док-во по индукции в общем случае невозможно. Таким образом, док-во по индукции слишком сильно завязано на свойства натуральных чисел и не раскрывает "настоящей" причины, по которой единственность ОТА верна - так, мне кажется, думают многие математики.
Тем не менее в доказательствах по индукции есть своя прелесть - главное их преимущество в том, что они намного короче и проще обычного доказательства через лемму Евклида. В этой записи я опишу доказательства по индукции, а подход через лемму Евклида разберу отдельно позже.
Доказательств по индукции я знаю два разных, хоть они довольно похожи друг на друга.
1. Сначала опишу более элегантное, на мой взгляд. Это доказательство принадлежит Цермело, он опубликовал его в 1934 году, но упомянул тогда же, что нашел его еще примерно в 1912-м.
Предположим, мы доказали единственность для всех чисел, меньших n, и теперь доказываем для n. Мы можем предположить, что n непростое, иначе все тривиально. Пусть p - наименьший делитель n из всех делителей n, больших 1; очевидно, что p обязан быть простым делителем, иначе были бы делители еще меньше.
Мы хотим доказать следующее: в любом разложении n на простые множители встречается p. Если мы это докажем, то работа закончена - выше мы увидели, что достаточно показать, что нет разных разложений без общих множителей, а если p всегда присутствует, то он всегда общий множитель, так что таких разных не может быть. Этот же аргумент в развернутом виде: возьмем любые два разложения, они оба включают p, удалим его и получим два разложения числа n/p, согласно индуктивному предположению они должны быть одинаковыми, значит, и исходные два одинаковы.
Пусть n = q*q1*...*qs - произвольное разложение n, в котором множитель q отличается от p. Мы хотим доказать, что несмотря на это, p все равно найдется где-то среди других множителей q1...qs. Поскольку p минимальный делитель, q > p, так что посмотрим на число n - p*n/q. Оно меньше n и потому имеет единственное разложение; поскольку p делит это число, p должно участвовать в этом разложении. Однако это число равно также (q-p)*q1*...*qs. p не делит q-p, так что он обязан участвовать в разложении среди
q1*...*qs, что и требовалось доказать.
2. Теперь второе доказательство по индукции.
Предположим, n = p1*p2*...*pk = q1*q2*...*qs, и у разложений нет общих элементов. Мы можем предположить, что в каждом разложении есть хотя бы два множителя - иначе все тривиально - и пусть p1, q1 будут минимальными множителями в каждом разложении. Тогда p12 ≤ n, и то же верно насчет q1; поскольку они разные, одно из неравенств должно быть строгим, и следовательно p1*q1 < n. Рассмотрим число X = n - p1*q1; согласно индуктивному предположению у него есть единственное разложение. Поскольку и p1 и q1 делят n и делят p1*q1, каждое из них делит X и поэтому встречается в его единственном разложении. Единственность разложения X поэтому дает нам право записать X = p1*q1*Y, и соответственно n = p1*q1(1+Y). Но теперь, если мы посмотрим на n/p1, у которого тоже обязано быть единственное разложение, оно с одной стороны должно быть p2*...*pk, а с другой включать в себя q1, потому что n/p1 = q1(1+Y). Это противоречие, потому что q1 не встречается среди p2*...*pk.