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

Основная теорема арифметики утверждает: Каждое натуральное число n>1 можно представить в виде n=p1pk, где p1,,pk — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей. Если формально условиться, что произведение пустого множества чисел равно 1, то условие n>1 в формулировке можно опустить, тогда для единицы подразумевается разложение на пустое множество простых: 1=1.
 Как следствие, каждое натуральное число n единственным образом представимо в виде

n=p1d1p2d2pkdk, где p1<p2<<pk — простые числа, и d1,,dk — некоторые натуральные числа.
  Такое представление числа n называется его каноническим разложением на простые сомножители.

История


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

Следствия



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


Н. О. Д.(a,b)=p1min{d1,d1}p2min{d2,d2}p3min{d3,d3}p4min{d4,d4}=pimin{di,di},
Н. О. К.(a,b)=p1max{d1,d1}p2max{d2,d2}p3max{d3,d3}p4max{d4,d4}=pimax{di,di},

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

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

1,2,3,97,22,23,297,397,223,2297,2397,22397
  Для того, чтобы найти количество всех делителей исходного числа, достаточно посмотреть на каноническое разложение, указанное в начале статьи. Натуральные числа d1,,dk — это не что иное, как количество соответствующих простых чисел p1,...,pk, встречающихся в разложении исходного числа. Таким образом, если мы хотим найти количество всех делителей данного числа, достаточно подсчитать количество всевозможных комбинаций значений чисел d1,...,dk. В нашем примере число 2 встречается 2 раза. Следовательно, при нахождении делителей числа N, d3 может принимать целые значения от 0 до 2, то есть всего 3 значения. Значит, чтобы посчитать общее количество делителей, нужно перемножить количество всевозможных значений у разных dk. В нашем случае mdel=223=12

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


ab=p1d1+d1p2d2+d2p3d3+d3p4d4+d4=pidi+di.
  Пример: 6836=(2217)(2233)=243217

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

 Пример (упростить выражение): 85+8361=83(82+61)=83125=8353=

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


Существование: Докажем существование разложения числа n, предполагая, что оно уже доказано для любого другого числа, которое меньше n. Если n — простое, то существование доказано. Если n — составное, то оно может быть представлено в виде произведения двух чисел a и b, каждое из которых больше 1, но меньше n. Числа a и b либо являются простыми, либо могут быть разложены в произведение простых (уже доказано ранее). Подставив их разложение в n=ab, получим разложение исходного числа n на простые. Существование доказано.
Единственность: Сначала докажем следующую лемму: если разложение числа m на простые множители единственно, то каждый простой делитель m должен входить в это разложение. Пусть число m делится на p и при этом p — простое. Тогда можно представить исходное число как m=pm1, где m1 — натуральное число. Тогда разложение m — есть разложение числа m1, с добавленным множителем p. По нашему предположению, существует только одно разложение числа m, следовательно, p должно встретиться в нём. Лемма доказана.
 Теперь докажем единственность методом математической индукции, то есть докажем единственность разложения числа n, если уже доказана единственность разложения всех чисел, которые меньше n. Если n — простое, то единственность очевидна. Если n — составное, то предположим, что существуют два разных разложения числа n в произведение простых:
n=p0p1p2p3=q0q1q2q3, где pi,qi — простые числа.
 Никакое простое число не может встретиться в обоих разложениях сразу, так как, если бы встретилось, то мы могли бы сократить на него и получили бы различные разложения числа, меньшего n, что противоречит предположению индукции.
 Пусть p0 — наименьший из простых множителей, которые встречаются в первом разложении. Так как n — составное, то существует ещё хотя бы один множитель в разложении. И, так как p0 — наименьший из всех множителей, то np02. Во втором разложении аналогично: nq02. Так как p0q0, то одно из этих неравенств — строгое, следовательно, p0q0<n
 Число np0q0 — натуральное число, которое меньше n, следовательно, оно может быть представлено как произведение простых единственным способом. Так как n делится на p0, то и np0q0 делится на p0, следовательно, согласно лемме, p0 должно входить в разложение числа np0q0. Аналогично, q0 тоже должно входить в разложение этого числа.
 Отсюда следует, что число n делится на p0q0, следовательно, p1p2p3 делится на q0. Однако это противоречит доказанной лемме, так как число p1p2p3<n и q0 не является одним из p1,p2,p3,. Полученное противоречие доказывает единственность разложения числа n на простые множители.

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


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

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

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


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

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


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

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


 Однако действие данной теоремы не распространяется на все кольца.
 Рассмотрим, к примеру, комплексные числа вида a=m+in5, где m,n — целые числа. Сумма и произведение таких чисел будут числами того же вида. Тогда получим кольцо с нормой N(a)=m2+5n2=|a|2.
 Для числа 6 в этом кольце существуют два различных разложения: 6=23=(1i5)(1+i5). Остаётся доказать, что числа 2,3,1±i5 являются простыми. Докажем, что число 2 — простое. Пусть 2=(m1+in15)(m2+in25). Тогда 4=(m12+5n12)(m22+5n22). Следовательно, m12+5n12=m22+5n22=2.
 Но в нашем кольце нет чисел с нормой 2, следовательно, такое разложение невозможно, поэтому число 2 — простое. Аналогично рассматриваются числа 3,1±i5.
 Кольца, в которых основная теорема арифметики всё же выполняется, называются факториальными.