Простий множник

У теорії чисел, прості множники (прості подільники) додатного цілого числа — це прості числа, які ділять це число без остачі (без залишку)[1]. Виділити прості множники додатного цілого числа означає перелічити ці прості множники разом з їх кратностями. Процес визначення простих множників називається факторизацією цілого числа. Основна теорема арифметики стверджує, що будь-яке натуральне число можна подати у вигляді єдиного (з точністю до порядку слідування) добутку простих множників[2].

Це зображення демонструє знаходження простих множників числа 864. Скорочений спосіб написання — 2 ⁵ × 3 ³

Щоб скоротити вираз, прості множники часто подаються у вигляді степенів простих чисел (кратності). Наприклад,

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 — це найбільший з показників степеня а, для яких $p^{a}$ ділить n без остачі.

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

Повний квадрат

Квадрат числа має властивість, що всі його прості множники мають парні кратності. Наприклад, число 144 (квадрат 12) має прості множники

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

У більш зрозумілій формі:

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\leq 1$ .

Криптографічні застосування

Визначення простих множників числа — це приклад задачі, яка часто використовується для забезпечення криптографічного захисту в системах шифрування[4]. Передбачається, що ця задача вимагає супер-поліноміального часу за кількістю цифр. Це означає, що відносно легко сконструювати задачу, вирішення якої зайняло б більше часу, ніж відомий вік Всесвіту за поточного розвитку комп'ютерів і за допомогою сучасних алгоритмів.

Функції Омега

Функція $ω (n)$ (омега) являє собою число різних простих множників n, у той час як функція $Ω(n)$ (велика Омега) являє собою число простих множників $n$ перелічене з урахуванням кратності[2]. Якщо

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

тоді

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

Наприклад, $24 = 2 3 \times 3 1$ Так що $ω (24) = 2$ і $Ω(24) = 3 + 1 = 4$

$ω (n)$ для $n$ = 1, 2, 3, … відповідно 0, 1, 1, 1, 1, 2, 1, 1, 1, … — послідовність A001221 з Онлайн енциклопедії послідовностей цілих чисел, OEIS .
$Ω(n)$ для $n$ = 1, 2, 3, … відповідно 0, 1, 1, 2, 1, 2, 1, 3, 2, … — послідовність A001222 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.

Див. також

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

Посилання

Jensen, Gary R. (2004). Arithmetic for Teachers: With Applications and Topics from Geometry. American Mathematical Society.
Riesel, Hans (1994). Prime numbers and computer methods for factorization. Basel, Switzerland: Birkhäuser. ISBN 978-0-8176-3743-9.
Melvyn B. Nathanson (1996). Additive Number Theory: the Classical Bases. Graduate Texts in Mathematics 234. Springer-Verlag. ISBN 0-387-94656-X.
Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). Handbook of Applied Cryptography. CRC Press. ISBN 0-8493-8523-7.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Jensen, Gary R. (2004). Arithmetic for Teachers: With Applications and Topics from Geometry. American Mathematical Society.

[Riesel-2] Riesel, Hans (1994). Prime numbers and computer methods for factorization. Basel, Switzerland: Birkhäuser. ISBN 978-0-8176-3743-9.

[3] Melvyn B. Nathanson (1996). Additive Number Theory: the Classical Bases. Graduate Texts in Mathematics 234. Springer-Verlag. ISBN 0-387-94656-X.

[4] Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). Handbook of Applied Cryptography. CRC Press. ISBN 0-8493-8523-7.