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

Чтобы сократить выражение, простые множители часто представляются в виде степеней простых чисел (кратностей). Например,

${\displaystyle 360=2\times 2\times 2\times 3\times 3\times 5=2^{3}\times 3^{2}\times 5}$

в котором множители 2, 3 и 5 имеют кратности 3, 2 и 1, соответственно.

Для простого множителя р числа n кратность числа p — это наибольший из показателей степени а , для которых р а делит n нацело.

Для положительного целого числа n , количество простых множителей n и сумма простых множителей n (без учёта кратности) — это примеры арифметических функций из n ( ).

Полный квадрат

Квадрат числа имеет то свойство, что все его простые множители имеют чётные кратности. Например, число 144 (квадрат 12) имеет простые множители

${\displaystyle 144=2\times 2\times 2\times 2\times 3\times 3=2^{4}\times 3^{2}.}$

В более понятной форме:

${\displaystyle 144=2\times 2\times 2\times 2\times 3\times 3=(2\times 2\times 3)\times (2\times 2\times 3)=(2\times 2\times 3)^{2}=(12)^{2}.}$

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

Взаимно простые числа

Положительные целые числа, не имеющие общих простых множителей, называются взаимно простыми . Два целых числа a и b можно назвать взаимно простыми, если их наибольший общий делитель НОД( a , b ) = 1. Если для двух целых чисел неизвестны их простые множители, то для определения того, являются ли они взаимно простыми, используется алгоритм Евклида ; алгоритм выполняется за полиномиальное время по количеству цифр.

Целое число 1 является взаимно простым для любого положительного целого числа, включая само себя. Иными словами, число 1 не имеет простых множителей, оно — . Это означает, что НОД(1, b ) = 1 для любого b ≥ 1.

Криптографические приложения

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

Функции Омега

Функция ω ( n ) (омега) представляет собой число различных простых множителей n , в то время как функция Ω( n ) (большая Омега) представляет собой число простых множителей n , пересчитанное с учётом кратности . Если

${\displaystyle n=\prod _{i=1}^{\omega (n)}p_{i}^{\alpha _{i}},}$

тогда

${\displaystyle \Omega (n)=\sum _{i=1}^{\omega (n)}\alpha _{i}.}$

Например, 24 = 2 ³ × 3 ¹ , Так что ω (24) = 2 и Ω(24) = 3 + 1 = 4 .

• ω ( n ) для n = 1, 2, 3, … соответственно 0, 1, 1, 1, 1, 2, 1, 1, 1, … — последовательность в OEIS .
• Ω( n ) для n = 1, 2, 3, … соответственно 0, 1, 1, 2, 1, 2, 1, 3, 2, … — последовательность в OEIS .

См. также

• Составное число
• Факторизация целых чисел — алгоритмическая проблема нахождения простых множителей заданного числа
• Делимость
• Таблица простых множителей
• Решето Эратосфена
• Теорема Эрдёша-Каца
• Криптографическая стойкость

Ссылки