Составное число

---

Составно́е число́ — натуральное число, имеющее делители, отличные от единицы и самого себя. Каждое составное число является произведением двух или более натуральных чисел, бо́льших единицы^[1]. Все натуральные числа делятся на три непересекающиеся категории: простые, составные и единица^[2].

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

Основная теорема арифметики утверждает, что любое составное число может быть разложено в произведение простых множителей, причём единственным способом (с точностью до порядка множителей).

Покажем, что в натуральном ряду можно найти последовательности подряд идущих составных чисел любой длины. Пусть n — произвольное натуральное число. Обозначим:

Тогда n последовательных чисел ${\displaystyle N+2,N+3,N+4\dots N+(n+1)}$ содержит только составные числа: ${\displaystyle N+2}$ делится на 2, ${\displaystyle N+3}$ делится на 3 и т. д.

Чтобы определить, является ли заданное натуральное число ${\displaystyle N}$ простым или составным, надо найти его нетривиальные делители или доказать, что таких не существует. В случае небольшого ${\displaystyle N}$ поиск его делителей — несложная задача, для этого можно использовать признаки делимости^[3] или специальные алгоритмы, указанные в статьях Тест простоты и Факторизация целых чисел. Нахождение делителей больших чисел (актуальная задача криптографии) может оказаться проблемой, превышающей возможности современных компьютеров.

---