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

Данный материал мы посвятим теоретическим основам разложения чисел на некоторые простые множители. Это называется основной теоремой арифметики. В начале мы приведем ее формулировку, а потом обоснуем и докажем.

Две вспомогательные теоремы для доказательства основной теоремы арифметики

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

Теорема 1

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

Доказательство 1

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

Вторая теорема выглядит так:

Теорема 2

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

Доказательство 2

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

Формула и доказательство основной теоремы арифметики

После того, как мы сформулировали две вспомогательные теоремы, мы можем перейти к основной теореме арифметики.

Теорема 3

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

Доказательство 3

Докажем данную теорему. Возьмем целое число $a$ $a$ , которое будет больше $1$ $1$ , и докажем, что его вообще можно разложить на множители. Возьмем наименьший положительный делитель данного числа, не равный единице, и обозначим его $p_{1}$ $p_{1}$ _. Исходя из теоремы, доказательство которой мы приводили в статье о таблице простых чисел, данное число будет простым. Тогда, согласно определению делимости, должно существовать такое целое число, для которого $a = p_{1} \cdot a_{1}$ $a = p_{1} \cdot a_{1}$ . Если $a_{1}$ $a_{1}$ будет больше $1$ $1$ , то должно существовать число, являющееся его наименьшим простым делителем, значит, $a_{1} = p_{2} \cdot a_{2}$ $a_{1} = p_{2} \cdot a_{2}$ и $a = p_{1} \cdot p_{2} \cdot a_{2}$ $a = p_{1} \cdot p_{2} \cdot a_{2}$ .

Проводим такие подсчеты до тех пор, пока у нас не получится $a = 1$ $a = 1$ . Такой итог неизбежен, поскольку $a, a 1, a 2, \dots$ $a, a 1, a 2, \dots$ является последовательностью целых чисел в убывающем порядке. Таким образом, число a всегда может быть разложено на простые множители вида $a = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ $a = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ . Если показатель $n$ $n$ будет равен единице, то у нас получится, что $a = p_{1}$ $a = p_{1}$ _. Это разложение подходит для простого числа.

Теперь нам надо доказать, что подобное разложение будет единственным. Допустим, что помимо $a = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ $a = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ есть и другое разложение. Обозначим его $a = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ $a = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ . Следовательно, в таком случае было бы справедливым равенство $p_{1} \cdot p_{2} \cdot \dots \cdot p_{n} = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ $p_{1} \cdot p_{2} \cdot \dots \cdot p_{n} = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ . Докажем, что если $n$ $n$ не равен $m$ $m$ , то данное равенство будет невозможным, а при равенстве показателей эти произведения $p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ $p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ и $q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ $q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ будут тождественно равными.

Мы можем разделить правую часть равенства на $q$ $q$ . Тогда, согласно предыдущей теореме, у нас должен быть хотя бы один множитель из последовательности $p_{1}, p_{2}, \dots, p_{n}$ $p_{1}, p_{2}, \dots, p_{n}$ , который можно разделить на $q_{1}$ $q_{1}$ . Например, предположим, что $p_{1}$ $p_{1}$ делится на $q_{1}$ $q_{1}$ , но поскольку оба этих числа являются простыми, то $p_{1}$ $p_{1}$ делится на $q_{1}$ $q_{1}$ только тогда, когда $q_{1} = p_{1}$ $q_{1} = p_{1}$ . Тогда мы можем сократить правую и левую часть равенства: $p_{1} \cdot p_{2} \cdot \dots \cdot p_{n} = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ $p_{1} \cdot p_{2} \cdot \dots \cdot p_{n} = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ на $q_{1} = p_{1}$ $q_{1} = p_{1}$ . Получаем, что $p_{2} \cdot \dots \cdot p_{n} = q_{2} \cdot \dots \cdot q_{m}$ $p_{2} \cdot \dots \cdot p_{n} = q_{2} \cdot \dots \cdot q_{m}$ .

Повторяем те же действия с $p_{2}$ $p_{2}$ и $q_{2}$ $q_{2}$ и приходим к равенству $p_{3} \cdot \dots \cdot p_{n} = q_{3} \cdot \dots \cdot q_{m}$ $p_{3} \cdot \dots \cdot p_{n} = q_{3} \cdot \dots \cdot q_{m}$ . Действуем так до тех пор, пока не сократим все множители. Если $n$ $n$ не равен $m$ $m$ , то у нас будет равенство $1 = q_{n} + 1 \cdot \dots \cdot q_{m}$ $1 = q_{n} + 1 \cdot \dots \cdot q_{m}$ , и $p_{m + 1} \cdot \dots \cdot p_{n} = 1$ $p_{m + 1} \cdot \dots \cdot p_{n} = 1$ . Для простых чисел они невозможны. Если же показатели равны друг другу, то мы придем к тождеству $1 = 1$ $1 = 1$ , что говорит нам о тождественном равенстве разложений $a = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ $a = p_{1} \cdot p_{2} \cdot \dots \cdot p_{n}$ и $a = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ $a = q_{1} \cdot q_{2} \cdot \dots \cdot q_{m}$ . На этом единственность разложения на простые множители можно считать доказанной.