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

Существование: докажем существование разложения числа ${\displaystyle n}$ на простые множители, если предположить, что аналогичное уже доказано для любого другого числа, меньшего ${\displaystyle n}$. Если ${\displaystyle n}$ — простое, то существование доказано. Если ${\displaystyle n}$ — составное, то оно может быть представлено в виде произведения двух чисел ${\displaystyle a}$ и ${\displaystyle b}$, каждое из которых больше 1, но меньше ${\displaystyle n}$. Числа ${\displaystyle a}$ и ${\displaystyle b}$ либо являются простыми, либо могут быть разложены в произведение простых (уже доказано ранее). Подставив их разложение в ${\displaystyle n=a\cdot b}$, получим разложение исходного числа ${\displaystyle n}$ на простые. Существование доказано[5].

Единственность: для простого числа единственность очевидна.

Для составного числа идея для доказательства заключается в использовании метода «от противного», а именно выдвигается предположение о том, что число имеет два различных разложения. Рассматриваются простые числа ${\displaystyle p_{0}}$ и ${\displaystyle q_{0}}$, являющиеся наименьшими в первом и втором из этих разложений соответственно, а также доказывается следующая лемма:

если разложение числа ${\displaystyle m}$ на простые множители единственно, то каждый простой делитель ${\displaystyle m}$ должен входить в это разложение.

Далее рассматривается число ${\displaystyle n-p_{0}\cdot q_{0}}$, которое, в свою очередь, является натуральным и которое меньше ${\displaystyle n}$. Из предположения индукции и вышеуказанной леммы следует, что ${\displaystyle p_{0}\cdot q_{0}}$ является делителем данного числа, после чего аналогично делается вывод, что первое разложение на множители делится на ${\displaystyle q_{0}}$. Никакое простое число не может встретиться в обоих разложениях сразу, так как иначе на него можно было бы сократить и получить различные разложения на простые множители числа, меньшего ${\displaystyle n}$, тем самым достигается противоречие предположению индукции и, следовательно, доказывается единственность разложения числа ${\displaystyle n}$ на простые множители[6].

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

наибольший общий делитель ${\displaystyle n\cdot a}$ и ${\displaystyle n\cdot b}$ есть наибольший общий делитель ${\displaystyle a}$ и ${\displaystyle b}$, умноженный на ${\displaystyle n}$.

Из данного следствия можно доказать лемму Евклида, также необходимую для доказательства теоремы:

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

Существование: идея доказательства существования заключается в том, чтобы доказать лемму:

рассмотрим простое число ${\displaystyle p}$ и произведение ${\displaystyle n\cdot a}$. Пусть ${\displaystyle n\cdot a}$ делится на ${\displaystyle p}$, но ${\displaystyle a}$ не делится на ${\displaystyle p}$, тогда ${\displaystyle n}$ делится на ${\displaystyle p}$.

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

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

${\displaystyle n=p_{1}\cdot p_{2}\cdot p_{3}\cdot \ldots =p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots }$

Так как ${\displaystyle p'_{1}\cdot p'_{2}\cdot p'_{3}\cdot \ldots }$ делится на ${\displaystyle p_{1}}$, то либо ${\displaystyle p'_{1}}$, либо ${\displaystyle p'_{2}\cdot p'_{3}\cdot \ldots }$ делится на ${\displaystyle p_{1}}$. Если ${\displaystyle p'_{1}}$ делится на ${\displaystyle p_{1}}$, то ${\displaystyle p'_{1}=p_{1}}$, так как оба эти числа являются простыми. Если же ${\displaystyle p'_{2}\cdot p'_{3}\cdot \ldots }$ делится на ${\displaystyle p_{1}}$, то продолжим предыдущие рассуждения. В конце концов получится, что какое-либо из чисел ${\displaystyle p'_{1},p'_{2},p'_{3},\ldots }$ равно числу ${\displaystyle p_{1}}$, а следовательно, оба разложения числа на самом деле совпадают. Таким образом доказана единственность разложения.

Евклид изложил в «Началах» важные основы для теории чисел и в том числе основной теоремы арифметики. Три предложения, очень близкие по смыслу к основной теореме арифметики, можно найти в книгах 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].

Известный персидский учёный Камал ад-Дин ал-Фариси сделал значительный шаг вперёд в изучении основной теоремы арифметики. В его труде «Записки для друзей о доказательстве дружественности» (англ. Memorandum for friends on the proof of amicability) доказано существование разложения на простые множители и предоставлена необходимая информация для доказательства единственности данного разложения. Однако Камала ал-Фариси больше всего интересовало построение собственного доказательства для теоремы Сабита ибн Курры по поиску дружественных чисел — и ал-Фариси не стремился доказать основную теорему арифметики, а занимался поиском всех делителей составного числа[15]. Скрупулезно исследуя разложение чисел на множители, он сформулировал и доказал утверждение, которое, по сути, и оказалось доказательством существования разложения натурального числа на простые множители.

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

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

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

Если составное число ${\displaystyle a}$ разложено на простые множители как ${\displaystyle a=b\cdot c\cdot d\cdot h\cdot \ldots \cdot k\cdot l}$, тогда ${\displaystyle a}$ не имеет делителя кроме ${\displaystyle 1}$ и ${\displaystyle b,c,d,...,k,l}$ и произведений каждого из них с каждым, произведений троек и т. д. вплоть до произведения всех элементов без какого-либо одного.

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

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

Следствие IX:

Если числа ${\displaystyle a}$ и ${\displaystyle b}$ простые, то каждый делитель числа ${\displaystyle a\cdot a\cdot b}$ — это либо ${\displaystyle a}$, либо ${\displaystyle a^{2}}$, либо ${\displaystyle 1}$, либо одно из произведений этих трех чисел на ${\displaystyle b}$. То есть один из шести: ${\displaystyle 1,a,a\cdot a,1\cdot b,a\cdot b,a\cdot a\cdot b}$.

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

В переводе его формулировка такова:

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

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

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

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

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

Утверждение Лежандра о существовании разложения гласит[18]:

Любое число ${\displaystyle N}$, не являющееся простым, может быть представлено как произведение нескольких простых чисел ${\displaystyle \alpha ,\beta ,\gamma }$ и т. д., каждое из которых возведено в определенную степень, таким образом, всегда можно полагать ${\displaystyle N=\alpha ^{m}\beta ^{n}\gamma ^{p}}$ и т. д.

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

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

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

Основная теорема арифметики даёт элегантные выражения для НОД и НОК.

Обозначим за ${\displaystyle {p_{i}}}$ все различные простые числа, на которые числа ${\displaystyle a}$ и ${\displaystyle b}$ были разложены, a степени, с которыми они встречаются в этих разложениях, — как ${\displaystyle {d_{i}}}$ и ${\displaystyle {d'_{i}}}$ соответственно. При этом ясно, что ${\displaystyle {d_{i}},{d'_{i}}}$ могут принимать только натуральные или нулевые значения.

Тогда:

${\displaystyle {\text{НОД}}(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}'\,\}}\cdot \ldots =\prod p_{i}^{\min\{\,d_{i},d_{i}'\,\}};}$

${\displaystyle {\text{НОК}}(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}'\,\}}\cdot \ldots =\prod p_{i}^{\max\{\,d_{i},d_{i}'\,\}}.}$

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

Используем каноническое разложение числа ${\displaystyle n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k}},}$ указанное в начале статьи. Натуральные числа ${\displaystyle d_{1},\cdots ,d_{k}}$ — это не что иное, как количество соответствующих простых чисел ${\displaystyle p_{1},...,p_{k}}$, встречающихся в разложении исходного числа. Таким образом, для поиска всех делителей достаточно записать произведения со всевозможными комбинациями простых чисел, варьируя количество каждого ${\displaystyle p_{i}}$ в произведении от ${\displaystyle 0}$ до ${\displaystyle d_{i}}$

Пример: ${\displaystyle N=1164=2\cdot 2\cdot 3\cdot 97=2^{2}\cdot 3^{1}\cdot 97^{1}.}$

Так как число 2 встречается в разложении 2 раза, ${\displaystyle d_{1}}$ может принимать целые значения от 0 до 2. Аналогично ${\displaystyle d_{2}}$ и ${\displaystyle d_{3}}$ принимают значения от 0 до 1. Таким образом, множество всех делителей состоит из чисел

${\displaystyle {\begin{alignedat}{2}1,\\2,\\3,\\97,\\2\cdot 2,\\2\cdot 3,\\2\cdot 97,\\3\cdot 97,\\2\cdot 2\cdot 3,\\2\cdot 2\cdot 97,\\2\cdot 3\cdot 97,\\2\cdot 2\cdot 3\cdot 97.\end{alignedat}}}$.

Для подсчёта общего количества делителей нужно перемножить количество всех возможных значений у разных ${\displaystyle d_{k}}$.

В данном примере общее количество делителей равно ${\displaystyle 2\cdot 2\cdot 3=12.}$

Некоторые арифметические функции можно вычислить с помощью канонического разложения на простые множители.

Например, для функции Эйлера от натурального числа справедлива формула: ${\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),\;\;n>1,}$ где ${\displaystyle p}$ — простое число и пробегает все значения, участвующие в разложении ${\displaystyle n}$ на простые сомножители (доказательство).

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

${\displaystyle 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}'}\ldots =\prod p_{i}^{d_{i}+d_{i}'},}$

где ${\displaystyle {d'_{i}}}$ — это степень, с которой простое число ${\displaystyle {p_{i}}}$ встречается в разложении числа ${\displaystyle b}$. Пример: ${\displaystyle 68\cdot 36=(2\cdot 2\cdot 17)\cdot (2\cdot 2\cdot 3\cdot 3)=2^{4}\cdot 3^{2}\cdot 17}$

Основная теорема арифметики с небольшой поправкой (а именно уточняется, что множители берутся не только с точностью до порядка следования, но и до ассоциированности — свойства гауссовых чисел получаться друг из друга умножением на делитель единицы: 1, i, −1 или −i) имеет место в кольце гауссовых целых чисел. Идея доказательства состоит в нахождении алгоритма деления с остатком в данном кольце чисел[19].

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

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

Для числа 6 в этом кольце существуют два различных разложения: ${\displaystyle 6=2\cdot 3=(1-i{\sqrt {5}})(1+i{\sqrt {5}})}$. Остаётся доказать, что числа ${\displaystyle 2,3,1\pm i{\sqrt {5}}}$ являются простыми. Докажем, что число 2 — простое. Пусть число ${\displaystyle 2}$ разложено на простые множители как ${\displaystyle (m_{1}+in_{1}{\sqrt {5}})(m_{2}+in_{2}{\sqrt {5}})}$. Тогда ${\displaystyle 4=|m_{1}+in_{1}{\sqrt {5}}|^{2}|m_{2}+in_{2}{\sqrt {5}}|^{2}=(m_{1}^{2}+5n_{1}^{2})(m_{2}^{2}+5n_{2}^{2})}$. А для того, чтобы числа ${\displaystyle m_{1}+in_{1}{\sqrt {5}}}$ и ${\displaystyle m_{2}+in_{2}{\sqrt {5}}}$ оставались простыми, у ${\displaystyle m_{1}^{2}+5n_{1}^{2}}$и ${\displaystyle m_{2}^{2}+5n_{2}^{2}}$ есть единственный вариант — они должны равняться именно 2.

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

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