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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Каждое натуральное число 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 году. Почти во всех школьных учебниках доказательство этой теоремы не приводится, вероятно, из-за отсутствия её в работах Евклида.[3]

Следствия[править | править исходный текст]

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


  • Зная разложение числа на множители, можно сразу указать все делители этого числа.
Делителем натурального числа 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\cdot2\cdot17)\cdot(2\cdot2\cdot3\cdot3\cdot) = 2^4\cdot 3^2\cdot17

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

Пример(упростить выражение): 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 на простые. Существование доказано.[4]

Единственность: Если разложение числа 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 имеет единственное разложение на простые множители. [5]

Другое доказательство (алгоритм Евклида)[править | править исходный текст]

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

Наибольший общий делитель  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. Следовательно, в конце придем к выводу, что оба разложения числа совпадают. Таким образом доказана единственность разложения.

ОТА в кольцах[править | править исходный текст]

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

ОТА в кольце целых Гауссовых чисел[править | править исходный текст]

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

Неединственность разложения в кольце[править | править исходный текст]

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

Для числа 6 в этом кольце существуют два различных разложения:  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} . Кольца, в которых основная теорема арифметики всё же выполняется, называются факториальными.

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Литература[править | править исходный текст]