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

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

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

Каждое натуральное число можно представить в виде , где  — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

Если формально условиться, что произведение пустого множества чисел равно 1, то условие в формулировке можно опустить, тогда для единицы подразумевается разложение на пустое множество простых: [3][4].

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

где  — простые числа, и  — некоторые натуральные числа.

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

Доказательство[править | править вики-текст]

По методу индукции[править | править вики-текст]

Существование: Докажем существование разложения числа на простые множители, предполагая, что оно уже доказано для любого другого числа, меньшего . Если  — простое, то существование доказано. Если  — составное, то оно может быть представлено в виде произведения двух чисел и , каждое из которых больше 1, но меньше . Числа и либо являются простыми, либо могут быть разложены в произведение простых (уже доказано ранее). Подставив их разложение в , получим разложение исходного числа на простые. Существование доказано.[5]

Единственность: Сначала докажем следующую лемму:

Если разложение числа на простые множители единственно, то каждый простой делитель должен входить в это разложение.

Пусть число делится на и при этом  — простое. Тогда можно представить исходное число как , где  — натуральное число. Тогда разложение  — есть разложение числа , с добавленным множителем . По нашему предположению, существует только одно разложение числа , следовательно, должно встретиться в нём. Лемма доказана.

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

, где  — простые числа.

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

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

Число  — натуральное число, которое меньше , следовательно, оно может быть представлено как произведение простых единственным способом. Так как делится на , то и делится на , следовательно, согласно лемме, должно входить в разложение числа . Аналогично, тоже должно входить в разложение этого числа.

Отсюда следует, что число делится на , следовательно, делится на . Однако это противоречит доказанной лемме, так как число и не является одним из . Полученное противоречие доказывает единственность разложения числа на простые множители. [6]

С использованием алгоритма Евклида[править | править вики-текст]

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

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

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

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

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

Существование: Для доказательства этой теоремы рассмотрим простое число и произведение . Пусть делится на , но не делится на . Так как  — простое, то его единственными делителями являются и . Тогда  — единственный общий делитель и . Следовательно, Н. О. Д. и равен . Очевидно, что делится на . Следовательно, так как каждый общий делитель двух чисел также является и делителем их Н. О.Д, а является общим делителем и , то делится на .

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

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

История[править | править вики-текст]

Предпосылки основной теоремы арифметики берут свои истоки в Древней Греции. Несмотря на то, что в древнегреческой математике основная теорема арифметики в современной формулировке не встречается, в «Началах»(др.-греч. Στοιχεῖα) Евклида есть эквивалентные ей предложения. Следуя за Евклидом, многие математики на протяжении веков вносили свой вклад к доказательству основной теоремы арифметики, приводя в своих трудах близкие по смыслу утверждения, среди этих ученых Камаль аль-Дин аль-Фариси, Ж. Престет, Л. Эйлер, А. Лежандр.[8] Первая точная формулировка основной теоремы арифметики и ее доказательство приводятся К. Гауссом в книге «Арифметические исследования» (лат. Disquisitiones Arithmeticae), изданной в 1801 году[9]. С этих пор появилось множество различных новых доказательств теоремы, конкурирующих между собой по красоте и пикантности.[8]

Евклид (III век до н. э.)[править | править вики-текст]

Евклид заложил в «Началах» важные основы для теории чисел и, в частности, основной теоремы арифметики. Три предложения, очень близкие по смыслу к основной теореме арифметики, можно найти в книгах VII и IX, а именно: предложение 30 из книги VII, наиболее известное как лемма Евклида, предложение 31 из книги VII и предложение 14 из книги IX. Ниже они приведены в переводе Мордухай-Болтовского.

VII.30:

Если два числа, умножая друг друга, производят что-то, возникающее же из них измеряется каким-то первым числом, то (последнее) измерит и одно из первоначальных[10]

VII.31:

Всякое составное число измеряется каким-то первым числом[11]

IX.14:

Если число будет наименьшим измеряемым (данными) первыми числами, то оно не измерится никаким иным простым числом, кроме первоначально измерявших (его)[12]

В настоящее время из предложений VII.30 и VII.31 выводят доказательство основной теоремы арифметики, однако Евклид его в своих трудах не изложил. Предложение IX.14 в свою очередь имеет много схожего с единственностью разложения на простые множители, однако было замечено, что это утверждение охватывает не все возможные случаи, например, наличие хотя бы одного квадрата простого числа в разложении на простые множители.[13][14]

Аль-Фариси (XIV век)[править | править вики-текст]

Известный персидский математик и физик Камаль аль-Дин аль-Фариси[en] сделал значительный шаг вперед в изучении основной теоремы арифметики. В его труде «Меморандум для друзей о доказательстве дружественности» (араб. Tadhkira al-ahbab fi bayan al-tahabb‎) доказано существование разложения на простые множители и предоставлена необходимая информация для доказательства единственности данного разложения. В связи с тем, что наибольший интерес для аль-Фариси представляло построение собственного доказательства для теоремы Сабита ибн Курры по поиску дружественных чисел, аль-Фариси не стремился доказать основную теорему арифметики, а занимался поиском всех делителей составного числа.[15] Скрупулезно исследуя разложение чисел на множители, он сформулировал и доказал утверждение, являющееся ни чем иным как доказательством существования разложения натурального числа на простые множители.

В переводе его утверждение звучит приблизительно так:

Каждое составное число может быть разложено на конечное число простых множителей, произведением которых оно является.

В утверждении 9 аль-Фариси сформулировал принцип для определения всех делителей составного числа, именно он и был необходим математику для доказательства теоремы Ибн Курры, в переводе предложение звучит так:

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

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

Жан Престет (XVII век)[править | править вики-текст]

Результаты, опубликованные Жаном Престетом[en] в книге «Новые элементы математики» (фр. Elements de Mathématiques, 1869) подтверждают, что разложение на простые множители рассматривалось в те времена не как нечто само по себе интересное, а как полезное приложение — средство для нахождения делителей заданного числа. Престет не сформулировал ни существования, ни единственности основной теоремы арифметики и уделял наибольшее внимание поиску делителей числа.[16] Несмотря на это, подобно аль-Фариси, Престет предоставил всю необходимую информацию для доказательства единственности разложения на простые множители при помощи своего Следствия IX, которое само по себе можно считать эквивалентным единственности разложения на простые множители.

Следствие IX:

Если числа и простые, каждый делитель это либо , либо , либо , либо один из произведения этих трех числе на .То есть один из шести: .

Леонард Эйлер и Лежандр (XVIII век)[править | править вики-текст]

В книге «Полное руководство по алгебре» (нем. Vollstandige Einleitung zur Algebra) Эйлер опубликовал результаты, схожие с трудами своих предшественников. Он сформулировал существование разложения числа на простые множители и предоставил частичное доказательство этого, опуская некоторые подробности в пункте 41 главы IV из первой части первого раздела книги.

В переводе его предложение звучит следующим образом:

Все составные числа которые могут быть разложены на множители, представлены произведением простых чисел; то есть все их множители — простые числа. Ибо, если найти множитель, который не является простым числом, он всегда может быть разложен и представлен двумя или более простыми числами.

Эйлер не формулировал теоремы об единственности разложения, но предложил схожее утверждение без доказательства в пункте 65 главы IV из первого раздела первой части. Там Эйлер неявно объясняет, что разложение числа на простые множители единственно, говоря, что все делители числа можно найти, зная простые множители из разложения данного числа.[17] Таким образом, этот пункт может считаться эквивалентным единственности разложения на простые множители.

В переводе данное утверждение звучит так:

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

«Введение в теорию чисел» (фр. Essai sur la Théorie des Nombres) Лежандра содержит доказательство существования разложения на простые множители и своеобразное предположение об единственности данного разложения при помощи перечисления всех простых делителей заданного числа.

Утверждение Лежандра о существовании разложения звучит так:

Любое составное число N может быть представлено как произведение некоторых простых чисел , каждое из которых возведено в определенную степень, таким образом, всегда существует разложение .

Утверждение, связанное с уникальностью разложения на простые множители, приведено в параграфе 10 «Введения в теорию чисел», где Лежандр намеревался найти число всех делителей числа и в то же время сумму этих же делителей. Из этого утверждения легко доказывается единственность.

Карл Гаусс (XIX век)[править | править вики-текст]

Первая точная формулировка теоремы и её доказательство приводятся в книге Гаусса «Арифметические исследования» (1801). Формулировку теоремы можно найти в параграфе 16, в переводе она звучит так:

Составное число может быть разложено на простые множители единственным образом.

Применение[править | править вики-текст]

Обозначим за все различные простые числа из разложений чисел и на простые множители, a степени, с которыми они встречаются в этих разложенииях, как и соответственно. Стоит заметить, что могут принимать только натуральные или нулевые значения.

Тогда:

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

Пример: .

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

Для того, чтобы найти количество всех делителей исходного числа, достаточно посмотреть на каноническое разложение, указанное в начале статьи. Натуральные числа  — это не что иное, как количество соответствующих простых чисел , встречающихся в разложении исходного числа. Таким образом, если мы хотим найти количество всех делителей данного числа, достаточно подсчитать количество всевозможных комбинаций значений чисел . В нашем примере число 2 встречается 2 раза. Следовательно, при нахождении делителей числа , может принимать целые значения от 0 до 2, то есть всего 3 значения. Значит, чтобы посчитать общее количество делителей, нужно перемножить количество всевозможных значений у разных . В нашем случае

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

Пример:

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

Пример (упростить выражение):

Основная теорема арифметики в кольцах[править | править вики-текст]

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

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

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

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

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

Рассмотрим, к примеру, комплексные числа вида , где , — целые числа. Сумма и произведение таких чисел будут числами того же вида. Тогда получим кольцо с нормой .

Для числа 6 в этом кольце существуют два различных разложения: . Остаётся доказать, что числа являются простыми. Докажем, что число 2 — простое. Пусть . Тогда . Следовательно, .

Но в нашем кольце нет чисел с нормой 2, следовательно, такое разложение невозможно, поэтому число 2 — простое. Аналогично рассматриваются числа .

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Литература[править | править вики-текст]