В теории чисел, простые множители (простые делители) положительного целого числа — это простые числа, которые делят это число нацело (без остатка)[1]. Выделить простые множители положительного целого числа означает перечислить эти простые множители вместе с их кратностями. Процесс определения простых множителей называется факторизацией целых чисел. Основная теорема арифметики утверждает, что любое натуральное число можно представить в виде единственного (с точностью до порядка следования) произведения простых множителей[2].
Чтобы сократить выражение, простые множители часто представляются в виде степеней простых чисел (кратностей). Например
в котором множители 2, 3 и 5 имеют кратности 3, 2 и 1, соответственно.
Для простого множителя р числа n кратность числа p — это наибольший из показателей степени а, для которых ра делит n нацело.
Для положительного целого числа n, количество простых множителей n и сумма простых множителей n (без учёта кратности) — это примеры арифметических функций из n (аддитивных арифметических функций[фр.][3]).
Полный квадрат
правитьКвадрат числа имеет то свойство, что все его простые множители имеют чётные кратности. Например, число 144 (квадрат 12) имеет простые множители
В более понятной форме:
Поскольку каждый простой множитель присутствует здесь чётное число раз, исходное число можно представить в виде квадрата некоторого числа. Таким же образом, куб числа — это число, у которого кратности простых множителей делятся на три, и так далее.
Взаимно простые числа
правитьПоложительные целые числа, не имеющие общих простых множителей, называются взаимно простыми. Два целых числа a и b можно назвать взаимно простыми, если их наибольший общий делитель НОД(a, b) = 1. Если для двух целых чисел неизвестны их простые множители, то для определения того, являются ли они взаимно простыми, используется алгоритм Евклида; алгоритм выполняется за полиномиальное время по количеству цифр.
Целое число 1 является взаимно простым для любого положительного целого числа, включая само себя. Иными словами, число 1 не имеет простых множителей, оно — empty product. Это означает, что НОД(1, b) = 1 для любого b ≥ 1.
Криптографические приложения
правитьОпределение простых множителей числа — это пример задачи, которая часто используется для обеспечения криптографической защиты в системах шифрования[4]. Предполагается, что эта задача требует супер-полиномиального времени по количеству цифр. Это значит, что относительно легко сконструировать задачу, решение которой заняло бы больше времени, чем известный возраст Вселенной при текущем развитии компьютеров и с помощью современных алгоритмов.
Функции Омега
правитьФункция ω(n) (омега) представляет собой число различных простых множителей n, в то время как функция Ω(n) (большая Омега) представляет собой число простых множителей n, пересчитанное с учётом кратности[2]. Если
тогда
Например, 24 = 23 × 31, Так что ω(24) = 2 и Ω(24) = 3 + 1 = 4.
См. также
править- Составное число
- Факторизация целых чисел — алгоритмическая проблема нахождения простых множителей заданного числа
- Делимость
- Таблица простых множителей
- Решето Эратосфена
- Теорема Эрдёша-Каца
- Криптографическая стойкость
Ссылки
править- ↑ Jensen, Gary R. Arithmetic for Teachers: With Applications and Topics from Geometry (англ.). — American Mathematical Society, 2004.
- ↑ 1 2 Riesel, Hans (1994), Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, ISBN 978-0-8176-3743-9
- ↑ Melvyn B. Nathanson. Additive Number Theory: the Classical Bases (англ.). — Springer-Verlag, 1996. — Vol. 234. — (Graduate Texts in Mathematics). — ISBN 0-387-94656-X.
- ↑ Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. Handbook of Applied Cryptography (неопр.). — CRC Press, 1996. — ISBN 0-8493-8523-7. Архивировано 7 марта 2005 года.