В этой статье дана теоретическая основа разложения чисел на простые множители - основная теорема арифметики. Здесь мы дадим ее формулировку и приведем доказательство основной теоремы арифметики.

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

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

Наибольший общий делитель чисел a и p делит p . Так как p – простое число по условию, то его положительными делителями являются лишь 1 и p , следовательно, НОД(a, p) равен либо 1 , либо p . В первом случае НОД(a, p)=1 , откуда следует, что числа a и p – взаимно простые. Во втором случае НОД(a, p)=p , а так как a делится на НОД(a, p) , то a делится на p .

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

Каждый из множителей согласно предыдущей теореме либо взаимно прост с числом p , либо делится на p . Если бы все множители были взаимно просты с p , то произведение этих множителей было бы взаимно просто с p в силу свойств взаимно простых чисел. Поэтому, хотя бы один из множителей делится на p .

Теперь мы обладаем необходимым арсеналом знаний, позволяющим провести доказательство основной теоремы арифметики.

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

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

Пусть p₁ – наименьший положительный и отличный от 1 делитель числа a . В силу теоремы, доказанной в разделе таблица простых чисел, число p₁ – простое. Тогда по определению делимости существует такое целое число a₁ , что a=p₁·a₁ . Если a₁ больше единицы, то существует его наименьший простой делитель p₂ , откуда a₁=p₂·a₂ и a=p₁·p₂·a₂ . Если a₂ больше единицы, то существует его наименьший простой делитель p₃ , поэтому a₂=p₃·a₃ , откуда a=p₁·p₂·p₃·a₃ . И так продолжаем этот процесс, пока не получим a_n=1 , что неизбежно, так как a , a₁ , a₂ , … - последовательность убывающих целых положительных чисел. Итак, мы всегда можем получить разложение числа a на простые множители вида a=p₁·p₂·…·p_n (при n=1 имеем a=p₁ , это разложение соответствует случаю, когда число a простое).

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

Правая часть последнего равенства делится на q₁ , тогда в силу предыдущей теоремы хотя бы один из множителей p₁, p₂, …, p_n должен делиться на q₁ . Допустим, на q₁ делится p₁ , но так как числа p₁ и q₁ простые, то p₁ делится на q₁ только тогда, когда q₁=p₁ . Это позволяет нам сократить обе части равенства p₁·p₂·…·p_n=q₁·q₂·…·q_m на q₁=p₁ , получаем p₂·…·p_n=q₂·…·q_m . Рассуждая аналогично про p₂ и q₂ , придем к равенству p₃·…·p_n=q₃·…·q_m . И так действуем дальше, пока в какой либо части равенства не сократятся все множители. При n≠m мы получим или равенство 1=q_n+1·…·q_m , или равенство p_m+1·…·p_n=1 , которые невозможны для простых чисел q_n+1, …, q_m и p_m+1, …, p_n . Если же n=m , то мы получим тождество 1=1 , которое указывает на тождественное равенство разложений a=p₁·p₂·…·p_n и a=q₁·q₂·…·q_m . Этим доказана единственность разложения числа на простые множители.

В заключение отметим, что основную теорему арифметики часто называют теоремой о разложении чисел на простые множители.