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

Основна́я теоре́ма арифме́тики утверждает:

Каждое натуральное число $n>1$ можно представить в виде $n=p_1\cdot\dots\cdot p_k$, где $p_1,\dots,p_k$ — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

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

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

$n = p_1^{d_1} \cdot p_2^{d_2} \cdot \dots \cdot p_k^{d_k},$ где $p_1 < p_2 < \dots < p_k$ — простые числа, и $d_1,\dots,d_k$ — некоторые натуральные числа.

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

История

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

Следствия

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

Н.О.Д.$(a,b) = p_1^{min(d_1,d_1')}\cdot p_2^{min(d_2,d_2')}\cdot p_3^{min(d_3,d_3')}\cdot p_4^{min(d_4,d_4')}\cdots = \prod p_i^{min(d_i,p_i')},$

Н.О.К.$(a,b) = p_1^{max(d_1,d_1')}\cdot p_2^{max(d_2,d_2')}\cdot p_3^{max(d_3,d_3')}\cdot p_4^{max(d_4,d_4')}\cdots = \prod p_i^{max(d_i,p_i')},$

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

Делителем натурального числа $N$ является такое натуральное число $k$, для которого $N = k\cdot l$, где $l$ - другое натуральное число.

Пример: $N = 1164 = 97\cdot3\cdot2\cdot2 = 97^1 \cdot 3^1 \cdot 2^2$.

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

$1, 2, 3, 97, 2\cdot2, 2\cdot3, 2\cdot97, 3\cdot97, 2\cdot2\cdot3, 2\cdot2\cdot97, 2\cdot3\cdot97, 2\cdot2\cdot3\cdot97$

Для того, чтобы найти количество всех делителей исходного числа, достаточно посмотреть на каноническое разложение, указанное в начале статьи. Натуральные числа $d_1,...,d_k$ - это не что иное, как количество соответствующих простых чисел $p_1,...,p_k$, встречающихся в разложении исходного числа. Таким образом, если мы хотим найти количество всех делителей данного числа, достаточно подсчитать количество всевозможных комбинаций значений чисел $d_1,...,d_k$. В нашем примере, число 2 встречается 2 раза. Следовательно, при нахождении делителей числа $N$, $d_3$ может принимать значения 0 до 2, т.е. всего 3 значения. Значит, чтобы посчитать общее количество делителей, нужно перемножить количество всевозможных значений у разных $d_k$. В нашем случае $m_{del} = 2\cdot2\cdot3 = 12$

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

$a\cdot b = p_1^{d_1+d_1'}\,p_2^{d_2+d_2'}\,p_3^{d_3+d_3'}\,p_4^{d_4+d_4'}\cdots = \prod p_i^{d_i+d_i'}.$

Пример: $68\cdot 36 = (2\cdot 2\cdot 17)\cdot(2\cdot 2\cdot 3\cdot 3\cdot) = 2^4 \cdot 3^2 \cdot 17$

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

Пример(упростить выражение): $8^5 + 8^3 \cdot 61 = 8^3 \cdot (8^2 + 61) = 8^3 \cdot 125 = 8^3 \cdot 5^3 = ...$

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

Существование: Докажем существование разложения числа $n$, учитывая, что оно уже доказано для любого другого числа, которое меньше $n$. Если $n$ - простое, то существование доказано. Если $n$ - составное, то оно может быть представлено в виде произведения двух чисел $a$ и $b$, которые больше 1, но меньше $n$. Числа $a$ и $b$ либо являются простыми, либо могут быть разложены в произведение простых(уже доказано ранее). Подставив их разложение в $n = a\cdot b$, получим разложение исходного числа $n$ на простые. Существование доказано.

Единственность: Если разложение числа $m$ на простые числа единственно, то каждый множитель $m$ должен входить в это разложение. Пусть число $m$ делится на $p$ и при этом $p$ - простое. Тогда можно представить исходное число как $m = p\cdot m^{(1)}$, где $m^{(1)}$ - целое число. Тогда разложение $m$ - есть разложение числа $m^{(1)}$, с добавленным множителем $p$. По нашему предположению существует только одно разложение числа $m$, следовательно, $p$ должно встретиться в нем.

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

$n = p^0\cdot p^1 \cdot p^2\cdot p^3 \cdot ... = q^0\cdot q^1\cdot q^2\cdot q^3\cdot ...$, где $p^i, q^i, i = 0, 1, 2, ...$ - простые числа.

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

Пусть, например, $p^0$ - наименьший из простых множителей, которые встречаются в первом разложении. Так как $n$ - составное, то существует еще хотя бы один множитель в разложении. И так как $p^0$ - был выбран как наименьший из всех множителей, то $n \geqslant (p^0)^2$. Во втором разложении аналогично: $n \geqslant (q^0)^2$. Так как $p^0 \neq q^0$, то одно из этих неравенств - строгое, следовательно $p^0\cdot q^0 < n$

Число $n - p^0 \cdot q^0$ - натуральное число, которое меньше $n$, следовательно, оно может быть представлено как произведение простых единственным способом. Так как $n$ делится на $p^0$, то $n - p^0\cdot q^0$ делится на $p^0$, следовательно, $p^0$ должно входить в разложение числа $n - p^0\cdot q^0$. Аналогично $q^0$ - должно входить в разложение этого числа.

Таким образом получим, что $n - p^0\cdot q^0\cdot r^0\cdot r^1 \cdot r^2 \cdot ...$, где $r^i, i = 0, 1, 2, ...$ - простые. Следовательно, число $n$ делится на $p^0\cdot q^0$, следовательно, $p^1 \cdot p^2 \cdot p^3 \cdot ...$ делится на $q^0$. Получим, что это невозможно, так как число $p^1 \cdot p^2 \cdot p^3 \cdot ... < n$ и $q^0$ не является одним из $p^1, p^2, p^3, ...$. Следовательно, число $n$ имеет единственное разложение на простые множители.

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

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

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

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

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

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

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

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

$n = p_1\cdot p_2\cdot p_3\cdot ... = p'_1\cdot p'_2\cdot p'_3\cdot ...$

Так как $p'_1\cdot p'_2\cdot p'_3\cdot ...$ делится на $p_1$, то либо $p'_1$, либо $p'_2\cdot p'_3\cdot ...$ делится на $p_1$. Если $p'_1$ делится на $p_1$, то $p'_1 = p_1$, так как оба эти числа являются простыми. Если же $p'_2\cdot p'_3\cdot ...$ делится на $p_1$, то продолжим предыдущие рассуждения. В конце концов придем к результату, что какое-либо из чисел $p'_1, p'_2, p'_3, ...$ равно числу $p_1$. Следовательно, в конце придем к выводу, что оба разложения числа совпадают. Таким образом доказана единственность разложения.

ОТА в кольцах

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

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

Основная теорема арифметики имеет место в кольце Гауссовых целых чисел. Идея доказательства состоит в нахождении алгоритма деления с остатком в данном кольце чисел. Доказав то, что он существует, и, получив Евклидово кольцо(кольцо с нормой называется евклидовым, если в нем имеется алгоритм деления с остатком), можно повторить все доказательства, сделанные для натуральных чисел, теперь для целых чисел и многочленов.

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

Однако действие данной теоремы не распространяется на все кольца. Рассмотрим, к примеру, комплексные числа вида $a = m + i\cdot n\cdot \sqrt{5}$, где $m$,$n$ - целые числа. Сумма и произведение таких чисел будут числами того же вида. Тогда получим кольцо с нормой $N(a) = m^2 + 5 \cdot n^2 = a^2$.

Рассмотрим разложение: $6 = 2\cdot3 = (1 - i\cdot \sqrt{5})\cdot(1 + i\cdot \sqrt{5})$. Получается единственность основной теоремы арифметики в данном кольце не выполняется, если числа $2, 3, 1\pm i\cdot \sqrt{5}$ являются простыми. Докажем, что число 2 - простое. Пусть $2 = (m_1 + i\cdot n_1 \cdot \sqrt{5}) \cdot (m_2 + i\cdot n_2 \cdot \sqrt{5})$. Тогда $4 = (m_1^2 + 5\cdot n_1^2)\cdot(m_2^2 + 5\cdot n_2^2)$. Следовательно, $m_1^2 + 5\cdot n_1^2 = m_2^2 + 5\cdot n_2^2 = 2$ Но в нашем кольце нет чисел с нормой 2, следовательно, такое разложение невозможно, а тогда получим, что число 2 - простое. Аналогично рассматриваются числа $3, 1\pm i\cdot \sqrt{5}$

См. также

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

Литература

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