Основна́я теоре́ма арифме́тики утверждает:^[1][2]

Единицу можно также считать произведением нулевого количества простых чисел, «пустым произведением».

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

где  — простые числа, и  — некоторые натуральные числа.

Такое представление числа называется его каноническим разложением на простые сомножители.

История

В «Началах» Евклида теорема не встречается, однако уже в книге VII появляются предложения, которые ей эквивалентны. Нет точной формулировки и в книге «Введение в теорию чисел» Лежандра, написанной в 1798 году. Первая её точная формулировка и доказательство приводятся в книге К. Ф. Гаусса «Арифметические исследования», изданной в 1801 году. Почти во всех школьных учебниках доказательство этой теоремы не приводится, вероятно, из-за отсутствия её в работах Евклида.^[3]

Следствия

• Основная теорема арифметики даёт элегантные выражения для наибольшего общего делителя и наименьшего общего кратного:

Н. О.Д.

Н. О.К.

• Зная разложение числа на множители, можно сразу указать все делители этого числа.

Делителем натурального числа является такое натуральное число , для которого , где  — другое натуральное число.

Пример: .

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

Для того, чтобы найти количество всех делителей исходного числа, достаточно посмотреть на каноническое разложение, указанное в начале статьи. Натуральные числа  — это не что иное, как количество соответствующих простых чисел , встречающихся в разложении исходного числа. Таким образом, если мы хотим найти количество всех делителей данного числа, достаточно подсчитать количество всевозможных комбинаций значений чисел . В нашем примере, число 2 встречается 2 раза. Следовательно, при нахождении делителей числа , может принимать значения 0 до 2, то есть всего 3 значения. Значит, чтобы посчитать общее количество делителей, нужно перемножить количество всевозможных значений у разных . В нашем случае

• Вычисление произведения двух чисел можно провести таким образом:

Пример:

• Иногда, находя общие делители, можно заметно упростить вычисление суммы(разности) двух чисел.

Пример(упростить выражение):

Доказательство (метод индукции)

Существование: Докажем существование разложения числа , предполагая, что оно уже доказано для любого другого числа, которое меньше . Если  — простое, то существование доказано. Если  — составное, то оно может быть представлено в виде произведения двух чисел и , каждое из которых больше 1, но меньше . Числа и либо являются простыми, либо могут быть разложены в произведение простых(уже доказано ранее). Подставив их разложение в , получим разложение исходного числа на простые. Существование доказано.^[4]

Единственность: Сначала докажем следующую лемму: если разложение числа на простые множители единственно, то каждый простой делитель должен входить в это разложение. Пусть число делится на и при этом  — простое. Тогда можно представить исходное число как , где  — натуральное число. Тогда разложение  — есть разложение числа , с добавленным множителем . По нашему предположению существует только одно разложение числа , следовательно, должно встретиться в нем. Лемма доказана.

Теперь докажем единственность методом математической индукции, то есть докажем единственность разложения числа , если уже доказана единственность разложения всех чисел, которые меньше . Если  — простое, то единственность очевидна. Если  — составное, то предположим, что существуют два разных разложения числа в произведение простых:

, где  — простые числа.

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

Пусть  — наименьший из простых множителей, которые встречаются в первом разложении. Так как  — составное, то существует еще хотя бы один множитель в разложении. И так как  — наименьший из всех множителей, то . Во втором разложении аналогично: . Так как , то одно из этих неравенств — строгое, следовательно

Число  — натуральное число, которое меньше , следовательно, оно может быть представлено как произведение простых единственным способом. Так как делится на , то и делится на , следовательно, согласно лемме, должно входить в разложение числа . Аналогично,  тоже должно входить в разложение этого числа.

Отсюда следует, что число делится на , следовательно, делится на . Однако это невозможно, так как число и не является одним из . Полученное противоречие доказывает единственность разложения числа на простые множители. ^[5]

Другое доказательство (алгоритм Евклида)

Можно доказать основную теорему арифметики с помощью алгоритма Евклида.^[6] Здесь алгоритм Евклида будет присутствовать не в явном виде, а будет использоваться следствие из него:

Наибольший общий делитель и есть раз взятый наибольший общий делитель a и b.

Из данного следствия можно доказать теорему Евклида:

Если p — простое число и произведение двух чисел делится на p, то хотя бы один из двух множителей делится на p.

Теперь используем данную теорему, чтобы доказать основную теорему арифметики.

Существование: является следствием теоремы Евклида. Для доказательства этой теоремы рассмотрим простое число p и произведение . Пусть делится на p, но a не делится на p. Так как p — простое, то его единственными делителями являются 1 и p. Тогда 1 — единственный общий множитель p и a. Следовательно, Н. О.Д. и равен n. Очевидно, что делится на p. Следовательно, так как каждый общий делитель двух чисел также является и делителем их Н. О.Д, а p является общим делителем и , то n делится на p.

Единственность: пусть число n имеет два разных разложения на простые числа:

Так как делится на , то либо , либо делится на . Если делится на , то , так как оба эти числа являются простыми. Если же делится на , то продолжим предыдущие рассуждения. В конце концов придем к результату, что какое-либо из чисел равно числу . Следовательно, в конце придем к выводу, что оба разложения числа совпадают. Таким образом доказана единственность разложения.

ОТА в кольцах

Рассмотрим основную теорему арифметики в более общем случае: в кольцах с нормой и в евклидовых кольцах.

ОТА в кольце целых Гауссовых чисел

Основная теорема арифметики имеет место в кольце Гауссовых целых чисел. Идея доказательства состоит в нахождении алгоритма деления с остатком в данном кольце чисел.^[7] Кольцо, в котором имеется алгоритм деления с остатком, называется евклидовым. Для любого евклидова кольца доказательство основной теоремы арифметики можно провести точно так же, как для натуральных чисел.

Неединственность разложения в кольце

Однако действие данной теоремы не распространяется на все кольца.^[7] Рассмотрим, к примеру, комплексные числа вида , где , — целые числа. Сумма и произведение таких чисел будут числами того же вида. Тогда получим кольцо с нормой .

Для числа 6 в этом кольце существуют два различных разложения: . Остаётся доказать, что числа являются простыми. Докажем, что число 2 — простое. Пусть . Тогда . Следовательно, Но в нашем кольце нет чисел с нормой 2, следовательно, такое разложение невозможно, поэтому число 2 — простое. Аналогично рассматриваются числа . Кольца, в которых основная теорема арифметики всё же выполняется, называются факториальными.

См. также

• Основная теорема алгебры
• Основная теорема анализа
• Простое число
• Алгоритм Евклида
• Видео доказательство основной теоремы арифметики

Примечания

Литература

• Жиков В.В. Основная теорема арифметики // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 3. — С. 112–117.
• Г. Дэвенпорт. Высшая арифметика. — Наука, 1965. — С. 15-38. — 176 с.
• Л. А. Калужин. Основная теорема арифметики. — Популярные лекции по математике. — М.: Наука, 1969. — 32 с.
• И. М. Виноградов. Основы теории чисел. — Государственное издательство технико-теоретической литературы, 1952. — 180 с. — 10 000 экз.
• Р. Курант, Г. Роббинс. Дополнение к главе I, § 4.2 // Что такое математика? — МЦНМО, 2000. — 568 с.