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

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

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

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

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

    Теорема 1

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

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

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

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

    Теорема 2

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

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

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

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

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

    Теорема 3

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

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

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

    Проводим такие подсчеты до тех пор, пока у нас не получится a=1. Такой итог неизбежен, поскольку 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. На этом единственность разложения на простые множители можно считать доказанной.

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

    Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
    Средняя оценка статьи
    4,5 из 5 (6 голосов)