Составные числа: определение и свойства¶

Составные числа — это натуральные числа, большие 1, которые не являются простыми, то есть имеют более двух различных натуральных делителей. Иными словами, составное число можно представить в виде произведения двух или более натуральных чисел, каждое из которых больше 1. Например, число 6 является составным, так как делится на 1, 2, 3 и 6, а число 7 — простое, поскольку делится только на 1 и на само себя. Число 1 не относится ни к простым, ни к составным числам.

¶Определение и основные свойства

В теории чисел множество натуральных чисел, больших единицы, разбивается на два непересекающихся класса: простые числа и составные числа. Формально число n > 1 называется составным, если существуют такие натуральные числа a и b, что n = a × b, где 1 < a ≤ b < n.

Ключевое свойство составного числа — наличие хотя бы одного нетривиального делителя. Из этого следует, что любое составное число можно разложить на простые множители. Такое разложение единственно с точностью до порядка множителей (основная теорема арифметики). Например, 12 = 2² × 3, а 100 = 2² × 5².

Минимальным составным числом является 4 (2 × 2). Далее следуют 6, 8, 9, 10, 12 и так далее. Все чётные числа, кроме 2, являются составными, поскольку делятся на 2 и на самих себя.

¶Признаки делимости и проверка на составность

Для определения, является ли число составным, используются признаки делимости. Число является составным, если оно делится хотя бы на одно простое число, не превышающее его квадратный корень. Это правило следует из того, что если число n имеет делитель d, больший √n, то частное n/d будет меньше √n и также будет делителем.

Например, для проверки числа 97 достаточно проверить его делимость на простые числа 2, 3, 5 и 7 (так как √97 ≈ 9,8). Ни на одно из них 97 не делится, следовательно, оно простое. Для числа 91 проверка показывает: 91 = 7 × 13, значит, оно составное.

Основные признаки делимости:

• на 2 — число оканчивается на чётную цифру;
• на 3 — сумма цифр числа делится на 3;
• на 5 — число оканчивается на 0 или 5;
• на 9 — сумма цифр числа делится на 9;
• на 11 — разность сумм цифр на чётных и нечётных позициях делится на 11.

¶Классификация составных чисел

Составные числа классифицируются по различным признакам.

¶По количеству простых множителей

• Полупростое число — произведение двух простых чисел (не обязательно различных). Примеры: 4 = 2×2, 6 = 2×3, 15 = 3×5.
• Числа с более чем двумя простыми множителями, например 30 = 2×3×5.

¶По свойствам делителей

• Совершенные числа — составные числа, равные сумме своих собственных делителей (например, 6 = 1+2+3, 28 = 1+2+4+7+14).
• Недостаточные числа — сумма собственных делителей меньше самого числа (большинство составных чисел, например 8, 10).
• Избыточные числа — сумма собственных делителей больше самого числа (например, 12, 18).

¶По форме записи

• Квадратные числа — составные числа, являющиеся квадратом целого числа (4, 9, 16, 25).
• Треугольные числа — числа вида n(n+1)/2 (6, 10, 15, 21).
• Числа Фибоначчи, среди которых составными являются, например, 8, 21, 34.

¶Распределение составных чисел

Составные числа встречаются в натуральном ряду значительно чаще, чем простые. С ростом величины чисел плотность простых чисел уменьшается, а составных — увеличивается. Согласно теореме о распределении простых чисел, количество простых чисел, не превышающих x, приблизительно равно x / ln(x). Следовательно, доля составных чисел среди чисел до x стремится к 1 по мере роста x.

Известно также, что в натуральном ряду существуют сколь угодно длинные промежутки, не содержащие ни одного простого числа. Например, числа от (n+1)! + 2 до (n+1)! + (n+1) включительно являются составными, так как каждое из них делится на соответствующее число от 2 до n+1.

¶Разложение на простые множители

Разложение составного числа на простые множители — одна из основных задач элементарной теории чисел. Для небольших чисел применяется метод последовательного деления на простые числа. Для больших чисел используются более сложные алгоритмы, такие как метод Полларда (ро-алгоритм), метод квадратичного решета и метод решета числового поля.

Разложение на простые множители используется в криптографии, в частности в алгоритме RSA, безопасность которого основана на сложности факторизации больших составных чисел.

¶Применение составных чисел

Составные числа находят применение в различных областях математики и информатики:

• В криптографии — модуль RSA является произведением двух больших простых чисел, то есть полупростым составным числом.
• В теории кодирования — при построении кодов, исправляющих ошибки.
• В вычислительной технике — при реализации арифметических операций и генерации псевдослучайных чисел.
• В школьном курсе математики — при изучении делимости, дробей и нахождении наибольшего общего делителя и наименьшего общего кратного.

¶Связь с простыми числами

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

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

¶Интересные факты

• Число 1 не является ни простым, ни составным. Это связано с тем, что у него только один делитель.
• Наибольшее известное составное число не существует, так как множество натуральных чисел бесконечно.
• Существуют составные числа, которые при определённых условиях ведут себя как простые. Например, числа Кармайкла — составные числа, удовлетворяющие малой теореме Ферма для любого взаимно простого основания. Наименьшее такое число — 561.
• Все чётные числа, кроме 2, являются составными, но не все нечётные числа — простыми (например, 9, 15, 21).