Статью подготовили специалисты образовательного сервиса Zaochnik
Основная теорема арифметики: формулировка, доказательство
- 27 мая 2023
- 6 минут
- 1 145
Данный материал мы посвятим теоретическим основам разложения чисел на некоторые простые множители. Это называется основной теоремой арифметики. В начале мы приведем ее формулировку, а потом обоснуем и докажем.
Две вспомогательные теоремы для доказательства основной теоремы арифметики
Согласно основной теореме арифметики, любое целое число, большее 11, может быть разложено на простые множители. Перед тем, как переходить к формулировке и доказательствам, запишем две теоремы, которые нам в этом помогут.
Любое положительное число aa, не равное 11, можно разделить на число pp, если оно не является по отношению к aa взаимно обратным числом.
Докажем это утверждение. Наибольшим общим делителем двух чисел aa и pp будет pp. Поскольку pp является простым числом, то у него всего два положительных делителя - единица и оно само. Значит, наибольший общий делитель (НОД) aa и pp будет равен либо единице, либо pp. Если мы возьмем случай с единицей, то получим, что aa и pp будут взаимно простыми числами. Во втором случае, если aa можно разделить на НОД (a, p)(a, p), то a делится на pp.
Вторая теорема выглядит так:
Если у нас есть произведение нескольких целых положительных множителей, не равных единице, которое можно разделить на число pp, то на это же число можно разделить хотя бы один из множителей.
Перейдем к доказательству. Согласно первой теореме, каждый множитель по отношению к pp либо является взаимно простым, либо может быть разделен на pp. Если бы все множители были взаимно простыми с pp, то данное произведение целиком было бы таким же, что следует из свойств взаимно простых чисел. Следовательно, на pp можно разделить хотя бы один из множителей.
Формула и доказательство основной теоремы арифметики
После того, как мы сформулировали две вспомогательные теоремы, мы можем перейти к основной теореме арифметики.
Любое целое число, большее единицы, может быть разделено на простые множители, причем это разложение будет единственным (изменение порядка следования множителей не в счет).
Докажем данную теорему. Возьмем целое число aa, которое будет больше 11, и докажем, что его вообще можно разложить на множители. Возьмем наименьший положительный делитель данного числа, не равный единице, и обозначим его p1p1. Исходя из теоремы, доказательство которой мы приводили в статье о таблице простых чисел, данное число будет простым. Тогда, согласно определению делимости, должно существовать такое целое число, для которого a=p1·a1a=p1⋅a1. Если a1a1 будет больше 11, то должно существовать число, являющееся его наименьшим простым делителем, значит, a1=p2·a2a1=p2⋅a2 и a=p1·p2·a2a=p1⋅p2⋅a2.
Проводим такие подсчеты до тех пор, пока у нас не получится a=1a=1. Такой итог неизбежен, поскольку a, a1, a2, … a, a1, a2, … является последовательностью целых чисел в убывающем порядке. Таким образом, число a всегда может быть разложено на простые множители вида a=p1·p2·…·pn. Если показатель n будет равен единице, то у нас получится, что a=p1. Это разложение подходит для простого числа.
Теперь нам надо доказать, что подобное разложение будет единственным. Допустим, что помимо a=p1·p2·…·pn есть и другое разложение. Обозначим его a=q1·q2·…·qm. Следовательно, в таком случае было бы справедливым равенство p1·p2·…·pn=q1·q2·…·qm. Докажем, что если n не равен m, то данное равенство будет невозможным, а при равенстве показателей эти произведения p1·p2·…·pn и q1·q2·…·qm будут тождественно равными.
Мы можем разделить правую часть равенства на q. Тогда, согласно предыдущей теореме, у нас должен быть хотя бы один множитель из последовательности p1, p2, …, pn, который можно разделить на q1. Например, предположим, что p1делится на q1, но поскольку оба этих числа являются простыми, то p1 делится на q1 только тогда, когда q1=p1. Тогда мы можем сократить правую и левую часть равенства: p1·p2·…·pn=q1·q2·…·qm на q1=p1. Получаем, что p2·…·pn=q2·…·qm.
Повторяем те же действия с p2 и q2 и приходим к равенству p3·…·pn=q3·…·qm. Действуем так до тех пор, пока не сократим все множители. Если n не равен m, то у нас будет равенство 1=qn+1·…·qm, и pm+1·…·pn=1. Для простых чисел они невозможны. Если же показатели равны друг другу, то мы придем к тождеству 1=1, что говорит нам о тождественном равенстве разложений a=p1·p2·…·pn и a=q1·q2·…·qm. На этом единственность разложения на простые множители можно считать доказанной.
Подводя итоги, заметим, что основная теорема арифметики может также называться теоремой о разложении чисел на простые множители.
Сохранить статью удобным способом