Основная теорема арифметики

Важнейшим вопросом, связанным с простыми числами, является вопрос о возможности разложения любого числа на простые множители.

Условились считать два разложения на множители одинаковыми, если они отличаются друг от друга лишь порядком множителей. Например, одинаковы разложения 2 · 2 · 3 · 5 и 3 · 2 · 5 · 2. Тогда справедлива следующая теорема, которую называют основной теоремой арифметики натуральных чисел.

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

Основной эта теорема называется потому, что практически все свойства делимости чисел являются ее следствиями.

Теорема содержит два утверждения:

1) разложение на простые множители существует,

2) разложение на простые множители единственно.

Предварительно сделаем замечание. Возникает вопрос: в каком смысле сформулированная теорема верна для простого числа р?

Условимся считать, что простое число представимо в виде произведения так: р = р, т.е. число простых множителей в правой части равно одному.

1) Докажем сначала возможность представления натурального числа большего единицы в виде произведения простых чисел.

Пусть п > 1– какое-нибудь натуральное число. Оно имеет по крайней мере один простой делитель р ₁, п = р ₁· п ₁, при этом п ₁ = 1 или п ₁ > 1. Если п ₁ = 1, то п = р ₁ и теорема доказана. Если число п ₁ > 1, то оно имеет хотя бы один простой делитель р ₂, т.е. n ₁ = p ₂ × n ₂, n = p ₁ · p ₂ · n ₂. При этом п ₂ = 1 или п ₂ > 1. Если п ₂ = 1, то n ₁ = р ₂ и n=p ₁ × p ₂ и теорема доказана. Если п ₂ > 1, то п ₂ имеет по крайней мере один простой делитель р ₃, п ₂ = p_{3 ×} n₃, п = p ₁ × p ₂ ×  p ₃ × n ₃, если п ₃ = 1, то n = p ₁· p ₂· p ₃ и теорема доказана. Если п ₃ > 1, то рассуждаем аналогичным образом дальше.

Заметим, что числа n ₁, n ₂, n ₃, … уменьшаются: n ₁ > n ₂ > n ₃ > …. Но множество натуральных чисел, меньших определённого числа n, конечно. Поэтому проводимый нами процесс после конечного числа шагов должен прекратиться, что может наступить лишь при условии, что какое-либо число       n_к = 1. Но тогда n = p ₁ · p ₂ · … · p_к, где p ₁, p ₂, …, p_к – простые числа.

Этим и доказывается возможность представления любого натурального числа большего 1 в виде произведения простых чисел.

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

Для осуществления этого разложения испытывают, последовательно, делится ли n на простые числа 2, 3, 5, 7.

2) Доказательство единственности (от противного).

Допустим, что натуральное число n > 1 можно представить в виде произведения простых чисел не единственным образом: n = p ₁· p ₂· … · p_к и n = q ₁ · q ₂ · … · q_m, где простые числа p_i могут отличаться от q_i, и, может быть, к ≠ m.

По симметричности и транзитивности отношения равенства имеем p ₁· p ₂ · … · p_к = q ₁· q ₂ · … · q_m (*). Правая часть имеет множителем q ₁, значит произведение в левой части делится на q ₁, но тогда по теореме 5 (§ 9) один из множителей делится на q ₁. Меняя в случае надобности места множителей, можем считать, что p ₁ q _1, но p ₁и q ₁ – простые числа, значит по теореме 6 (§ 3) p ₁ = q ₁. Разделим обе части равенства (*) на р ₁, получим:

p ₂ · p ₃ ·  … · p_к = q ₂ · q ₃ · … · q_m.

Аналогично устанавливаем, что один из множителей q ₂, q ₃,  …, q_m равен р ₂. Пусть q ₂ = р ₂, тогда p ₃ · p ₄ ·  … · p_к = q ₃ · q ₄ ·  … · q_m. Повторяя рассуждения, придем:

1) при к = т к тому, что при сокращении всех множителей в левой части равенства (*) сократятся все множители в правой части равенства (*) и в этом случае два представления числа n, указанные при допущении, могут отличаться только порядком следования множителей;

2) при к < т к невозможному равенству 1 = q_{k +1} · q_{k +2} · … · q_m, т.к. произведение простых чисел не может быть равно единице;

3)при к > т придем к невозможному равенству p_{m +1} · p_{m +2} · … · p_k = 1.

Следовательно, утверждение о единственности представления натурального числа п > 1 в виде произведения простых чисел доказано.

Если среди множителей p ₁, p ₂, …, p_к встречаются одинаковые, то, пользуясь записью произведения равных множителей как степени, можем написать: , где каждый из показателей – натуральное число, а все множители p ₁, p ₂, …, p_к – различные простые числа.

Такое представление натурального числа п > 1 называют каноническим разложением числа n на простые множители. Например, 360 = 2³ · 3² · 5.