Основная теорема арифметики: формулировка, доказательство

Любое положительное число $a$, не равное $1$, можно разделить на число $p$, если оно не является по отношению к $a$ взаимно обратным числом.

Докажем это утверждение. Наибольшим общим делителем двух чисел $a$ и $p$ будет $p$. Поскольку $p$ является простым числом, то у него всего два положительных делителя - единица и оно само. Значит, наибольший общий делитель (НОД) $a$ и $p$ будет равен либо единице, либо $p$. Если мы возьмем случай с единицей, то получим, что $a$ и $p$ будут взаимно простыми числами. Во втором случае, если $a$ можно разделить на НОД $(a, p)$, то a делится на $p$.

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

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

Любое целое число, большее единицы, может быть разделено на простые множители, причем это разложение будет единственным (изменение порядка следования множителей не в счет).

Докажем данную теорему. Возьмем целое число $a$, которое будет больше $1$, и докажем, что его вообще можно разложить на множители. Возьмем наименьший положительный делитель данного числа, не равный единице, и обозначим его $p_1$_.  Исходя из теоремы, доказательство которой мы приводили в статье о таблице простых чисел, данное число будет простым. Тогда, согласно определению делимости, должно существовать такое целое число, для которого $a=p_1·a_1$. Если $a_1$ будет больше $1$, то должно существовать число, являющееся его наименьшим простым делителем, значит, $a_1=p_2·a_2$ и $a=p_1·p_2·a_2$.

Проводим такие подсчеты до тех пор, пока у нас не получится $a=1$. Такой итог неизбежен, поскольку $a, a1, a2, \dots$является последовательностью целых чисел в убывающем порядке. Таким образом, число a всегда может быть разложено на простые множители вида $a=p_1·p_2·\dots ·p_n$. Если показатель $n$ будет равен единице, то у нас получится, что $a=p_1$_. Это разложение подходит для простого числа.

Теперь нам надо доказать, что подобное разложение будет единственным. Допустим, что помимо $a=p_1·p_2·\dots ·p_n$ есть и другое разложение. Обозначим его $a=q_1·q_2·\dots ·q_m$. Следовательно, в таком случае было бы справедливым равенство $p_1·p_2·\dots ·p_n=q_1·q_2·\dots ·q_m$. Докажем, что если $n$ не равен $m$, то данное равенство будет невозможным, а при равенстве показателей эти произведения $p_1·p_2·\dots ·p_n$ и $q_1·q_2·\dots ·q_m$ будут тождественно равными.

Мы можем разделить правую часть равенства на $q$. Тогда, согласно предыдущей теореме, у нас должен быть хотя бы один множитель из последовательности $p_1, p_2, \dots , p_n$, который можно разделить на $q_1$. Например, предположим, что $p_1$ делится на $q_1$, но поскольку оба этих числа являются простыми, то $p_1$ делится на $q_1$ только тогда, когда $q_1=p_1$. Тогда мы можем сократить правую и левую часть равенства: $p_1·p_2·\dots ·p_n=q_1·q_2·\dots ·q_m$ на $q_1=p_1$. Получаем, что $p_2·\dots ·p_n=q_2·\dots ·q_m$.

Повторяем те же действия с $p_2$ и $q_2$ и приходим к равенству $p_3·\dots ·p_n=q_3·\dots ·q_m$. Действуем так до тех пор, пока не сократим все множители. Если $n$ не равен $m$, то у нас будет равенство $1=q_n+1·\dots ·q_m$, и $p_{m+1}·\dots ·p_n=1$. Для простых чисел они невозможны. Если же показатели равны друг другу, то мы придем к тождеству $1=1$, что говорит нам о тождественном равенстве разложений $a=p_1·p_2·\dots ·p_n$ и $a=q_1·q_2·\dots ·q_m$. На этом единственность разложения на простые множители можно считать доказанной.