Нетривиальные делители¶
Нетривиальные делители — это все натуральные делители числа, за исключением единицы и самого числа. Понятие используется в элементарной теории чисел и алгебре при анализе свойств натуральных чисел, простых чисел и структуры множества делителей.
¶Определение
Пусть $n$ — натуральное число, $n > 1$. Делителем числа $n$ называется натуральное число $d$, на которое $n$ делится без остатка, то есть существует натуральное $k$ такое, что $n = d \cdot k$.
Среди всех делителей выделяют:
- тривиальные делители — единица $1$ и само число $n$;
- нетривиальные делители — все остальные делители числа $n$.
Число $n$ имеет нетривиальные делители тогда и только тогда, когда оно составное. Если таких делителей нет, число является простым.
¶Связь с простыми и составными числами
Классификация натуральных чисел по наличию нетривиальных делителей лежит в основе определения простого числа:
- Простое число — натуральное число $n > 1$, не имеющее нетривиальных делителей. К ним относятся числа 2, 3, 5, 7, 11, 13, 17, 19, 23 и далее.
- Составное число — натуральное число $n > 1$, имеющее хотя бы один нетривиальный делитель. Первые составные числа: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20.
Единица $1$ не относится ни к простым, ни к составным числам, поскольку по определению простое число должно превышать единицу.
¶Количество нетривиальных делителей
Общее число делителей числа $n$ обозначается $\tau(n)$ (также используется обозначение $d(n)$). Если каноническое разложение числа имеет вид
$$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k},$$
то
$$\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1).$$
Число нетривиальных делителей равно $\tau(n) - 2$ (при $n > 1$).
Примеры:
| Число $n$ | Разложение | Все делители | Нетривиальные делители | Их количество |
|---|---|---|---|---|
| 12 | $2^2 \cdot 3$ | 1, 2, 3, 4, 6, 12 | 2, 3, 4, 6 | 4 |
| 16 | $2^4$ | 1, 2, 4, 8, 16 | 2, 4, 8 | 3 |
| 30 | $2 \cdot 3 \cdot 5$ | 1, 2, 3, 5, 6, 10, 15, 30 | 2, 3, 5, 6, 10, 15 | 6 |
| 36 | $2^2 \cdot 3^2$ | 1, 2, 3, 4, 6, 9, 12, 18, 36 | 2, 3, 4, 6, 9, 12, 18 | 7 |
¶Минимальный нетривиальный делитель
Для любого составного числа $n$ его наименьший нетривиальный делитель не превосходит $\sqrt{n}$. Действительно, если $n = a \cdot b$ и оба множителя превышают $\sqrt{n}$, то их произведение превысило бы $n$. Следовательно, по крайней мере один из множителей не больше $\sqrt{n}$.
Это свойство лежит в основе простейшего алгоритма проверки числа на простоту — перебора делителей до $\sqrt{n}$. Для числа $n$ достаточно проверить делимость на все простые числа, не превосходящие $\sqrt{n}$.
¶Наименьший нетривиальный делитель и простота
Наименьший нетривиальный делитель составного числа всегда является простым числом. Если бы наименьший нетривиальный делитель $d$ был составным, он имел бы собственный нетривиальный делитель $d'$, который также делил бы $n$, что противоречило бы минимальности $d$.
Это свойство позволяет быстро отсеивать составные числа: если число делится на малое простое, оно заведомо не является простым. Именно на этом принципе построен тест Миллера — Рабина — одного из основных вероятностных алгоритмов проверки на простоту, применяемого в современной криптографии.
¶Применение
¶Теория чисел
Понятие нетривиальных делителей фигурирует при формулировке фундаментальных теорем: основной теоремы арифметики (о единственности канонического разложения), теоремы Евклида о бесконечности простых чисел, а также в задачах о совершенных числах, дружественных числах и простых числах Мерсенна.
¶Криптография
В криптосистемах с открытым ключом, таких как RSA, безопасность основана на трудности разложения больших составных чисел на нетривиальные множители. Если бы существовал эффективный алгоритм нахождения нетривиальных делителей произведения двух больших простых чисел, криптосистема была бы взломана. Нетривиальные делители чисел с сотнями цифр остаются недоступны для точного вычисления современными методами.
¶Алгоритмы факторизации
Методы разложения чисел на нетривиальные множители включают:
- метод пробного деления;
- алгоритм Ферма;
- метод непрерывных дробей;
- квадратичное решето;
- сферическое решето;
- алгоритм Pollard rho;
- алгоритм Pollard p − 1.
Асимптотически лучший из известных алгоритмов — сферическое решето Нумберфилда — имеет подполиниальную сложность $L_n\!\left[\tfrac{1}{3}, \sqrt[3]{\frac{64}{9}}\right]$.
¶Числа без нетривиальных делителей
Простые числа — единственные натуральные числа, не имеющие нетривиальных делителей. Среди них выделяют особые классы: числа Ферма $2^{2^n} + 1$, числа Мерсенна $2^p - 1$, простые числа-близнецы, простые числа вида $4k+1$ и $4k+3$. Вопрос о распределении простых чисел, то есть о том, как часто числа без нетривиальных делителей встречаются среди натуральных, раскрывается в простейшей гипотезе о распределении простых чисел, доказанной в 1896 году Жаком Адамаром и Шарлем де ла Валле-Пуссеном независимо друг от друга.
Источники:
- Виноградов И. М. Основы теории чисел.
- Новосёлов А. А. Элементарная теория чисел.
- Кнут Д. Искусство программирования, том 2: получисловые алгоритмы.
- Рибенбойм П. Книга о простых числах.
- Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers.