Как понимать результат разложения
В таблице ниже приведены разложения нескольких знакомых чисел — они показывают, как работает степенная запись.
| Число | Разложение на простые множители | Количество делителей |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17 (простое число) | 17 (само себя, степень 1) | 2 |
| 1024 | 2¹⁰ | 11 |
- Разложение простого числа — это оно само в первой степени, и у него всегда ровно 2 делителя: 1 и само число. Это и есть определяющее свойство простого числа.
- Число 1 не является ни простым, ни составным и не имеет разложения на простые множители (это пустое произведение); калькулятор принимает значения от 2 и выше.
- Для очень больших чисел пробное деление становится медленным, поскольку приходится проверять простые числа вплоть до квадратного корня из исходного числа, — именно поэтому разложение чрезвычайно больших чисел (в сотни цифр) вычислительно трудно и служит основой стойкости шифрования RSA.
Что такое разложение на простые множители?
Разложение на простые множители — это представление целого числа в виде набора простых чисел, произведение которых даёт исходное число. Простое число — это целое число больше 1, имеющее ровно два положительных делителя: 1 и само себя (2, 3, 5, 7, 11, 13, ... — первые несколько простых чисел). Например, 360 раскладывается как 2³ × 3² × 5, то есть 360 = 2×2×2×3×3×5.
Основная теорема арифметики — одно из краеугольных утверждений теории чисел — гарантирует, что у каждого целого числа больше 1 есть одно и только одно разложение на простые множители, с точностью до порядка записи множителей. Именно эта единственность делает разложение на простые множители чётко определённой и надёжной операцией, а не одним из нескольких равноправных ответов.
Разложение на простые множители лежит в основе ключевых разделов математики и информатики: с его помощью находят наибольший общий делитель и наименьшее общее кратное, определяют все делители числа, сокращают дроби и упрощают корни, а для очень больших чисел вычислительная сложность разложения служит математическим фундаментом криптографии с открытым ключом RSA, которая опирается на то, что разложить большое число на множители несоизмеримо труднее, чем перемножить эти множители.
Как пользоваться калькулятором разложения на простые множители
- Введите целое число от 2 и выше (до 1 триллиона).
- Калькулятор последовательно делит число на наименьший возможный простой множитель, пока не останется 1, — это стандартный метод пробного деления.
- Прочитайте разложение в степенной форме (например, 2³ × 3² × 5), где каждый показатель степени показывает, сколько раз соответствующее простое число входит в произведение.
- Посмотрите общее количество положительных делителей числа и сумму всех этих делителей — оба значения выводятся напрямую из разложения на простые множители.
Как вычисляются разложение, количество делителей и сумма делителей
Пробное деление находит разложение, перебирая простые числа-кандидаты начиная с 2: число делится на каждое простое столько раз, сколько оно делится нацело, после чего берётся следующий кандидат. Пример: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45 (дальше на 2 не делится, значит 2 входит 3 раза); 45 ÷ 3 = 15, ÷3 = 5 (дальше на 3 не делится, значит 3 входит 2 раза); 5 ÷ 5 = 1 (5 входит один раз). Итог: 360 = 2³ × 3² × 5.
Когда каноническое разложение n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ известно, общее количество положительных делителей (включая 1 и само n) находится прибавлением 1 к каждому показателю степени и перемножением результатов: (e₁+1) × (e₂+1) × ... × (eₖ+1). Пример для 360 = 2³ × 3² × 5¹: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24 делителя.
Сумма всех делителей вычисляется по мультипликативной формуле суммы делителей: каждая степень простого p^e из разложения даёт вклад (p^(e+1) − 1) ÷ (p − 1) — сумму геометрической прогрессии 1 + p + p² + ... + p^e — и эти вклады перемножаются по всем простым множителям. Пример для 360: слагаемое 2³ даёт (2⁴−1)/(2−1) = 15, слагаемое 3² даёт (3³−1)/(3−1) = 13, а слагаемое 5¹ даёт (5²−1)/(5−1) = 6; перемножая, получаем 15 × 13 × 6 = 1170 — сумму всех 24 делителей числа 360.
Типичные ошибки
- Остановка разложения до того, как получена 1: каждый найденный множитель нужно выделить полностью (а не один раз), прежде чем переходить к следующему простому кандидату.
- Считать 1 простым числом: по современному математическому соглашению 1 не является ни простым, ни составным, а её включение в разложение нарушило бы единственность, гарантированную основной теоремой арифметики.
- Забывать, что для подсчёта делителей важен показатель степени, а не только само простое число: в формуле используется (показатель + 1) для каждого простого, а не просто количество различных простых.
- Полагать, что у любого большого числа есть маленькие простые множители: у многих больших чисел (особенно у произведений двух больших простых) малых множителей нет вовсе — именно это свойство и делает их пригодными для криптографии.
Часто задаваемые вопросы
Как разложить число на простые множители?
Делите число на наименьшее простое, которое делит его нацело, продолжая делить на то же простое, пока это возможно, затем переходите к следующему простому и повторяйте, пока частное не станет равным 1. Для 360: разделите на 2 три раза (360→180→90→45), затем на 3 дважды (45→15→5), затем на 5 один раз (5→1), что даёт 360 = 2³ × 3² × 5.
Сколько делителей у числа?
Прибавьте 1 к каждому показателю степени в разложении и перемножьте результаты. Для 360 = 2³ × 3² × 5¹ количество делителей равно (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24. Учитываются все положительные делители, включая 1 и само число.
Что такое основная теорема арифметики?
Основная теорема арифметики утверждает, что каждое целое число больше 1 представимо в виде произведения простых чисел ровно одним способом, если не считать порядка перечисления простых. Именно эта единственность делает разложение на простые множители чётко определённой операцией, а не одним из нескольких равноправных ответов, и на ней держится значительная часть теории чисел.
Является ли 1 простым числом?
Нет. По современному математическому соглашению 1 не является ни простым, ни составным. Простое число по определению имеет ровно два различных положительных делителя (1 и само себя); у числа 1 есть лишь один положительный делитель (оно само), поэтому определению оно не удовлетворяет. Исключение 1 из простых необходимо и для того, чтобы выполнялась основная теорема арифметики: иначе число можно было бы «разложить», добавив сколько угодно множителей 1.
Почему разложение на простые множители важно для шифрования?
Современная криптография с открытым ключом RSA опирается на то, что перемножить два больших простых числа вычислительно легко, а разложить их большое произведение обратно на исходные простые крайне трудно с помощью известных сегодня классических алгоритмов. Эта асимметрия — легко умножить, трудно разложить — позволяет открыто передавать публичный ключ (произведение), тогда как закрытый ключ (простые множители) остаётся секретным и практически невосстановимым за разумное время при достаточно больших простых.
Как найти сумму всех делителей числа?
По каноническому разложению n = p₁^e₁ × p₂^e₂ × ... вычислите (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1) для каждого простого множителя и перемножьте результаты. Для 360 = 2³ × 3² × 5: слагаемое 2³ даёт (2⁴−1)/(2−1)=15, слагаемое 3² даёт (3³−1)/(3−1)=13, а слагаемое 5¹ даёт (5²−1)/(5−1)=6; перемножая, 15×13×6 = 1170 — сумма всех делителей числа 360.
Источники
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)