Важнейшим вопросом, связанным с простыми числами, является вопрос о возможности разложения любого числа на простые множители.
Условились считать два разложения на множители одинаковыми, если они отличаются друг от друга лишь порядком множителей. Например, одинаковы разложения 2 · 2 · 3 · 5 и 3 · 2 · 5 · 2. Тогда справедлива следующая теорема, которую называют основной теоремой арифметики натуральных чисел.
Теорема. Всякое натуральное число, большее единицы, можно единственным образом представить в виде произведения простых множителей.
Основной эта теорема называется потому, что практически все свойства делимости чисел являются ее следствиями.
Теорема содержит два утверждения:
1) разложение на простые множители существует,
2) разложение на простые множители единственно.
Предварительно сделаем замечание. Возникает вопрос: в каком смысле сформулированная теорема верна для простого числа р?
Условимся считать, что простое число представимо в виде произведения так: р = р, т.е. число простых множителей в правой части равно одному.
1) Докажем сначала возможность представления натурального числа большего единицы в виде произведения простых чисел.
Пусть п > 1– какое-нибудь натуральное число. Оно имеет по крайней мере один простой делитель р 1, п = р 1· п 1, при этом п 1 = 1 или п 1 > 1. Если п 1 = 1, то п = р 1 и теорема доказана. Если число п 1 > 1, то оно имеет хотя бы один простой делитель р 2, т.е. n 1 = p 2 × n 2, n = p 1 · p 2 · n 2. При этом п 2 = 1 или п 2 > 1. Если п 2 = 1, то n 1 = р 2 и n=p 1 × p 2 и теорема доказана. Если п 2 > 1, то п 2 имеет по крайней мере один простой делитель р 3, п 2 = p3 × n3, п = p 1 × p 2 × p 3 × n 3, если п 3 = 1, то n = p 1· p 2· p 3 и теорема доказана. Если п 3 > 1, то рассуждаем аналогичным образом дальше.
Заметим, что числа n 1, n 2, n 3, … уменьшаются: n 1 > n 2 > n 3 > …. Но множество натуральных чисел, меньших определённого числа n, конечно. Поэтому проводимый нами процесс после конечного числа шагов должен прекратиться, что может наступить лишь при условии, что какое-либо число nк = 1. Но тогда n = p 1 · p 2 · … · pк, где p 1, p 2, …, pк – простые числа.
Этим и доказывается возможность представления любого натурального числа большего 1 в виде произведения простых чисел.
Процесс разложения натурального числа на простые множители, применённый при доказательстве, хорошо известен со школы и схематически изображается так
| 168 | 2 | |
| 84 | 2 | |
| 42 | 2 | |
| 21 | 3 | |
| 7 | 7 | |
| 1 |
Для осуществления этого разложения испытывают, последовательно, делится ли n на простые числа 2, 3, 5, 7.
2) Доказательство единственности (от противного).
Допустим, что натуральное число n > 1 можно представить в виде произведения простых чисел не единственным образом: n = p 1· p 2· … · pк и n = q 1 · q 2 · … · qm, где простые числа pi могут отличаться от qi, и, может быть, к ≠ m.
По симметричности и транзитивности отношения равенства имеем p 1· p 2 · … · pк = q 1· q 2 · … · qm (*). Правая часть имеет множителем q 1, значит произведение в левой части делится на q 1, но тогда по теореме 5 (§ 9) один из множителей делится на q 1. Меняя в случае надобности места множителей, можем считать, что p 1 
q 1, но p 1и q 1 – простые числа, значит по теореме 6 (§ 3) p 1 = q 1. Разделим обе части равенства (*) на р 1, получим:
p 2 · p 3 · … · pк = q 2 · q 3 · … · qm.
Аналогично устанавливаем, что один из множителей q 2, q 3, …, qm равен р 2. Пусть q 2 = р 2, тогда p 3 · p 4 · … · pк = q 3 · q 4 · … · qm. Повторяя рассуждения, придем:
1) при к = т к тому, что при сокращении всех множителей в левой части равенства (*) сократятся все множители в правой части равенства (*) и в этом случае два представления числа n, указанные при допущении, могут отличаться только порядком следования множителей;
2) при к < т к невозможному равенству 1 = qk +1 · qk +2 · … · qm, т.к. произведение простых чисел не может быть равно единице;
3)при к > т придем к невозможному равенству pm +1 · pm +2 · … · pk = 1.
Следовательно, утверждение о единственности представления натурального числа п > 1 в виде произведения простых чисел доказано.
Если среди множителей p 1, p 2, …, pк встречаются одинаковые, то, пользуясь записью произведения равных множителей как степени, можем написать: 
, где каждый из показателей – натуральное число, а все множители p 1, p 2, …, pк – различные простые числа.
Такое представление натурального числа п > 1 называют каноническим разложением числа n на простые множители. Например, 360 = 23 · 32 · 5.
