Простой множитель

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

360=2×2×2×3×3×5=23×32×5
 в котором множители 2, 3 и 5 имеют кратности 3, 2 и 1, соответственно.
 Для простого множителя р числа n кратность числаp — это наибольший из показателей степени а, для которыхр\emphа делит n нацело.
 Для положительного целого числа n, количество простыхмножителей n и сумма простых множителей n (безучёта кратности) — это примеры арифметических функций из n(аддитивных арифметических функций).

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


 Квадрат числа имеет то свойство, что все его простые множители имеютчётные кратности. Например, число 144 (квадрат 12) имеет простыемножители
144=2×2×2×2×3×3=24×32.
В более понятной форме:
144=2×2×2×2×3×3=(2×2×3)×(2×2×3)=(2×2×3)2=(12)2.
Поскольку каждый простой множитель присутствует здесь чётное число раз,исходное число можно представить в виде квадрата некоторого числа. Такимже образом, куб числа — это число, у которого кратности простыхмножителей делятся на три, и так далее.

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


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

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


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

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


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

  • для = 1, 2, 3, \ldots соответственно 0, 1, 1, 1, 1, 2, 1, 1, 1, \ldots — .
  • для = 1, 2, 3, \ldots соответственно 0, 1, 1, 2, 1, 2, 1, 3, 2, \ldots — .