У теорії чисел, прості множники (прості дільники) додатного цілого числа — це прості числа, які ділять це число без остачі (без залишку). Виділити прості множники додатного цілого числа означає перелічити ці прості множники разом з їх кратностями. Процес визначення простих множників називається факторизацією цілого числа. Основна теорема арифметики стверджує, що будь-яке натуральне число можна подати у вигляді єдиного (з точністю до порядку слідування) добутку простих множників.
Щоб скоротити вираз, прості множники часто подаються у вигляді степенів простих чисел (кратності). Наприклад,
в якому множники 2, 3 і 5 мають кратності 3, 2 і 1, відповідно.
Для простого множника р числа n кратність числа p — це найбільший з показників степеня а, для яких ділить n без остачі.
Для додатного цілого числа n, кількість простих множників n і сума простих множників n (без урахування кратності) — це приклади арифметичних функцій від n (адитивних арифметичних функцій).
Повний квадрат Квадрат числа має властивість, що всі його прості множники мають парні кратності. Наприклад, число 144 (квадрат 12) має прості множники
У більш зрозумілій формі:
Оскільки кожен простий множник присутній тут парне число разів, вихідне число можна подати у вигляді квадрата деякого числа. Таким же чином, куб числа — це число, у якого кратності простих множників діляться на три, і так далі.
Взаємно прості числа Додатні цілі числа, що не мають спільних простих множників, називаються взаємно простими. Два цілих числа a і b можна назвати взаємно простими, якщо їх найбільший спільний дільник НСД . Якщо для двох цілих чисел невідомі їх прості множники, то для визначення того, чи є вони взаємно простими, використовується алгоритм Евкліда; алгоритм виконується за поліноміальний час за кількістю цифр.
Ціле число 1 є взаємно простим для будь-якого додатного цілого числа, включно з самим собою. Іншими словами, число 1 не має простих множників, воно — порожній добуток. Це означає, що НСД для будь-якого .
Криптографічні застосування Визначення простих множників числа — це приклад задачі, яка часто використовується для забезпечення криптографічного захисту в системах шифрування. Передбачається, що ця задача вимагає супер-поліноміального часу за кількістю цифр. Це означає, що відносно легко сконструювати задачу, вирішення якої зайняло б більше часу, ніж відомий вік Всесвіту за поточного розвитку комп'ютерів і за допомогою сучасних алгоритмів.
Функції Омега Функція (омега) являє собою число різних простих множників n, у той час як функція (велика Омега) являє собою число простих множників перелічене з урахуванням кратності. Якщо
тоді
Наприклад, Так що і
для = 1, 2, 3, … відповідно 0, 1, 1, 1, 1, 2, 1, 1, 1, … — . для = 1, 2, 3, … відповідно 0, 1, 1, 2, 1, 2, 1, 3, 2, … — .
Див. також
Складене число Факторизація цілих чисел — алгоритмічна проблема знаходження простих множників заданого числа Подільність Таблиця простих множників Решето Ератосфена
Криптографічна стійкість
Посилання