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

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