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

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

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

Если формально условиться, что произведение пустого множества чисел равно 1, то условие <math>n>1</math> в формулировке можно опустить, тогда для единицы подразумевается разложение на пустое множество простых: <math>1=1</math>.

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

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

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

История

В древнегреческой математике основная теорема арифметики в современной формулировке не встречается. Однако в «Началах» Евклида есть предложения, которые ей эквивалентны. В частности, теорема легко следует из так называемой леммы Евклида (предложение 30 в VII книге). Нет точной формулировки и в книге «Введение в теорию чисел» (фр. Essai sur la Théorie des Nombres) Лежандра, написанной в 1798 году. Первая её точная формулировка и доказательство приводятся в книге Гаусса «Арифметические исследования» (лат. Disquisitiones Arithmeticae), изданной в 1801 году.

Следствия

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

Н. О. Д.<math>(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,d_i')},</math>

Н. О. К.<math>(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,d_i')},</math>

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

Пример: <math> N = 1164 = 2\cdot 2\cdot 3\cdot 97 = 2^2 \cdot 3^1 \cdot 97^1</math>.

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

<math> 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</math>

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

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

<math>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'}.</math>

Пример: <math>68\cdot 36 = (2\cdot2\cdot17)\cdot(2\cdot2\cdot3\cdot3\cdot) = 2^4\cdot 3^2\cdot17</math>

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

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

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

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

Единственность: Сначала докажем следующую лемму: если разложение числа <math>m</math> на простые множители единственно, то каждый простой делитель <math>m</math> должен входить в это разложение. Пусть число <math>m</math> делится на <math>p</math> и при этом <math>p</math> — простое. Тогда можно представить исходное число как <math>m = p\cdot m_1</math>, где <math>m_1</math> — натуральное число. Тогда разложение <math>m</math> — есть разложение числа <math>m_1</math>, с добавленным множителем <math>p</math>. По нашему предположению, существует только одно разложение числа <math>m</math>, следовательно, <math>p</math> должно встретиться в нём. Лемма доказана.

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

<math>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 ...</math>, где <math>p_i, q_i</math> — простые числа.

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

Пусть <math>p_0</math> — наименьший из простых множителей, которые встречаются в первом разложении. Так как <math>n</math> — составное, то существует ещё хотя бы один множитель в разложении. И, так как <math>p_0</math> — наименьший из всех множителей, то <math>n \geqslant p_0^2</math>. Во втором разложении аналогично: <math> n \geqslant q_0^2</math>. Так как <math> p_0 \neq q_0 </math>, то одно из этих неравенств — строгое, следовательно, <math>p_0\cdot q_0 < n</math>

Число <math> n - p_0 \cdot q_0 </math> — натуральное число, которое меньше <math>n</math>, следовательно, оно может быть представлено как произведение простых единственным способом. Так как <math>n</math> делится на <math>p_0</math>, то и <math>n - p_0\cdot q_0</math> делится на <math>p_0</math>, следовательно, согласно лемме, <math>p_0</math> должно входить в разложение числа <math> n - p_0\cdot q_0</math>. Аналогично, <math> q_0</math> тоже должно входить в разложение этого числа.

Отсюда следует, что число <math> n</math> делится на <math>p_0\cdot q_0</math>, следовательно, <math> p_1 \cdot p_2 \cdot p_3 \cdot ...</math> делится на <math>q_0</math>. Однако это противоречит доказанной лемме, так как число <math> p_1 \cdot p_2 \cdot p_3 \cdot ... < n </math> и <math>q_0</math> не является одним из <math> p_1, p_2, p_3, ...</math>. Полученное противоречие доказывает единственность разложения числа <math>n</math> на простые множители.

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

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

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

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

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

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

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

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

<math> n = p_1\cdot p_2\cdot p_3\cdot ... = p'_1\cdot p'_2\cdot p'_3\cdot ... </math>

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

Основная теорема арифметики в кольцах

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

Основная теорема арифметики в кольце целых гауссовых чисел

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

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

Однако действие данной теоремы не распространяется на все кольца.

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

Для числа 6 в этом кольце существуют два различных разложения: <math> 6 = 2\cdot3 = (1 - i\cdot \sqrt{5})\cdot(1 + i\cdot \sqrt{5}) </math>. Остаётся доказать, что числа <math>2, 3, 1\pm i\cdot \sqrt{5} </math> являются простыми. Докажем, что число 2 — простое. Пусть <math> 2 = (m_1 + i\cdot n_1 \cdot \sqrt{5}) \cdot (m_2 + i\cdot n_2 \cdot \sqrt{5}) </math>. Тогда <math> 4 = (m_1^2 + 5\cdot n_1^2)\cdot(m_2^2 + 5\cdot n_2^2) </math>. Следовательно, <math> m_1^2 + 5\cdot n_1^2 = m_2^2 + 5\cdot n_2^2 = 2 </math>.

Но в нашем кольце нет чисел с нормой 2, следовательно, такое разложение невозможно, поэтому число 2 — простое. Аналогично рассматриваются числа <math> 3, 1\pm i\cdot \sqrt{5} </math>.

Кольца, в которых основная теорема арифметики всё же выполняется, называются факториальными.

См. также

• Основная теорема алгебры
• Основная теорема анализа

Литература

• Виноградов И. М. [www.mccme.ru/free-books/djvu/vinogradov.djvu Основы теории чисел]. — Государственное издательство технико-теоретической литературы, 1952. — 180 с. — 10 000 экз.
• Жиков В.В. [www.pereplet.ru/nauka/Soros/pdf/0003_112.pdf Основная теорема арифметики] // Соросовский Образовательный Журнал. — 2000. — Т. 6, № 3. — С. 112–117.
• Калужнин Л. А. [plm.mccme.ru/ann/a47.htm Основная теорема арифметики]. — Популярные лекции по математике. — М.: Наука, 1969. — 32 с.
• Курант Р., Роббинс Г. Дополнение к главе I, § 4.2 // [www.mccme.ru/free-books/pdf/kurant.htm Что такое математика?] — МЦНМО, 2000. — 568 с.