Основная теорема арифметики утверждает: каждое натуральное число больше 1 можно представить произведением простых чисел, и набор этих простых множителей единственен с точностью до порядка. Существование следует из того, что составной множитель можно снова разделить; единственность опирается на лемму Евклида: если простое число делит произведение, оно делит хотя бы один множитель.
Почему, например, у 84 не могут оказаться два разных набора простых «деталей»? Разные первые деления возможны: 84 = 6 · 14 и 84 = 4 · 21. Но это ещё не списки простых чисел. Доведём обе ветви до простых листьев и выясним, почему совпадение неизбежно, а не случайно.
Содержание
О чём именно говорит теорема
Простое число имеет ровно два положительных делителя: 1 и само себя. Для любого натурального n > 1 существует запись n = p1 · … · pk, где каждый pi прост. Если получена другая такая запись, в ней те же простые числа с тем же числом повторений; меняться может только порядок. Утверждение состоит из двух разных частей: существования и единственности.
| Первый выбор | Следующее деление | Простые листья |
|---|---|---|
| 84 = 6 · 14 | 6 = 2 · 3; 14 = 2 · 7 | 2 · 3 · 2 · 7 |
| 84 = 4 · 21 | 4 = 2 · 2; 21 = 3 · 7 | 2 · 2 · 3 · 7 |
Почему разложение обязательно существует
Возьмём n > 1. Если оно простое, нужная запись состоит из одного множителя n. Если составное, то n = ab, где 1 < a,b < n. С каждым составным множителем поступаем так же. В каждой новой ветви появляются натуральные числа меньше прежнего; бесконечно убывать среди положительных целых они не могут. Поэтому ветви закончатся простыми числами. Перемножая листья, снова получим n. Это доказывает существование, но само по себе ещё не доказывает единственность.
Ключ к единственности: лемма Евклида
Если простое p делит ab, то p делит a или b. Например, 5 делит 10 · 9 и делит первый множитель 10. Нельзя заменить слово «простое» на «составное»: 6 делит 2 · 3, но не делит ни 2, ни 3.
Лемма не выводится из основной теоремы, которую мы только собираемся доказать. Её можно получить раньше из алгоритма Евклида и равенства Безу. Если p не делит a, то общий делитель простого p и a равен 1. Равенство Безу даёт целые u,v с up + va = 1. Умножим на b: upb + vab = b. При p | ab оба слагаемых слева делятся на p; значит, p | b. Так лемма доказана без обращения к единственности разложения.
Почему равенство Безу не использует эту теорему?
Алгоритм Евклида последовательно делит с остатком. Каждый остаток есть целочисленная комбинация исходных чисел p и a; последний ненулевой остаток равен их НОД. Если НОД равен 1, обратная подстановка даёт up + va = 1. Здесь нужны только деление с остатком и свойства делимости, а не разложение на простые.
Почему второго набора простых быть не может
Предположим, что одно и то же n записано двумя произведениями простых: p1 · … · pk = q1 · … · qm. Простой p1 делит левую часть, значит, и произведение справа. Применяя лемму Евклида к произведению по очереди, получаем: p1 делит один из простых qj. У простого qj нет положительных делителей кроме 1 и него самого, поэтому p1 = qj. Переставим этот множитель на первое место и сократим равные положительные множители.
| Шаг | Что гарантировано |
|---|---|
| Выбрать простой из первого списка | Он делит произведение второго списка. |
| Применить лемму Евклида | Он равен одному простому из второго списка. |
| Сократить одинаковую пару | Осталось равенство более коротких произведений. |
| Повторить | Все пары совпадут; лишний простой дал бы произведение больше 1. |
Повторяем этот шаг, пока один список не опустеет. Другой не может сохранить ни одного простого: тогда справа стояло бы произведение чисел больше 1, а слева уже 1. Значит, длины и все множители совпали. Это и есть единственность с точностью до порядка.
Два примера, где видны обе части
Пример 1: 84. В таблице выше две ветви завершились записью 84 = 2 · 2 · 3 · 7. Существование видно по конечным простым листьям. Если кто-то предложит ещё один список простых для 84, лемма заставит его содержать 2; после сокращения снова 2, затем 3 и 7. Запись 2 · 3 · 14 не опровергает теорему: 14 составное.
Пример 2: 90. Имеем 90 = 9 · 10 = 3 · 3 · 2 · 5. Это простое разложение, включая повтор тройки. В любом другом простом списке для 90 число 5 обязано встретиться: оно делит произведение, а по лемме делит один из простых множителей и потому равно ему. Сократив 5, тем же рассуждением находим 2 и две тройки. Список 2 · 3 · 3 · 5 допустим, потому что поменялся только порядок; список 2 · 3 · 15 не является списком простых.
Границы утверждения
Единицу не называют простым числом и исключают из формулировки: иначе к любой записи можно было бы бесконечно дописывать множители 1 и потерять единственность. Ноль тоже исключён: произведение с нулём допускает сколько угодно дополнительных множителей. Для отрицательных целых отдельно учитывают знак: например, -30 = -1 · 2 · 3 · 5; утверждение выше сформулировано для натуральных чисел больше 1. Повторения важны: 12 = 2 · 2 · 3, а не просто «2 и 3».
Теорема объясняет, почему показатели простых в записи числа определены однозначно. Поэтому в задаче о количестве делителей можно опираться на эти показатели. Если нужна именно техника поиска множителей, а не доказательство её однозначности, она разобрана отдельно в статье о разложении на простые множители.
Проверьте утверждение до раскрытия ответа
Задача 1. Верно ли, что 48 = 2 · 2 · 2 · 2 · 3 — простое разложение и другого набора простых для 48 нет?
Ответ: да. Все множители простые, их произведение равно 48. Лемма Евклида и последовательное сокращение гарантируют тот же набор в любом другом простом разложении; порядок может измениться.
Задача 2. Утверждают: 30 = 2 · 15 и 30 = 3 · 10, поэтому единственность неверна. Найдите ошибку.
Ответ: 15 и 10 составные, поэтому обе записи ещё не простые разложения. После продолжения обе дают 2 · 3 · 5. Разные промежуточные ветви не являются контрпримером.
Задача 3. Можно ли заменить «простое p» на «любое p» в лемме Евклида? Проверьте p = 6 и произведение 2 · 3.
Ответ: нет. 6 делит 2 · 3 = 6, но не делит ни 2, ни 3. Простота p необходима; без неё шаг доказательства единственности не работает.