У теорії чисел, прості множники (прості дільники) додатного цілого числа — це (прості числа), які ділять це число (без остачі) ((без залишку)). (Виділити прості множники) додатного цілого числа означає перелічити ці прості множники разом з їх кратностями. Процес визначення простих множників називається (факторизацією цілого числа). (Основна теорема арифметики) стверджує, що будь-яке натуральне число можна подати у вигляді єдиного (з точністю до порядку слідування) добутку простих множників.
Щоб скоротити вираз, прості множники часто подаються у вигляді (степенів простих чисел) (кратності). Наприклад,
в якому множники 2, 3 і 5 мають кратності 3, 2 і 1, відповідно.
Для простого множника р числа n кратність числа p — це найбільший з (показників степеня) а, для яких ділить n без остачі.
Для додатного цілого числа n, кількість простих множників n і сума простих множників n (без урахування кратності) — це приклади арифметичних функцій від n ((адитивних арифметичних функцій)).
Повний квадрат
(Квадрат числа) має властивість, що всі його прості множники мають парні кратності. Наприклад, число 144 (квадрат 12) має прості множники
У більш зрозумілій формі:
Оскільки кожен простий множник присутній тут парне число разів, вихідне число можна подати у вигляді квадрата деякого числа. Таким же чином, (куб числа) — це число, у якого кратності простих множників діляться на три, і так далі.
Взаємно прості числа
Додатні цілі числа, що не мають спільних простих множників, називаються (взаємно простими). Два цілих числа a і b можна назвати взаємно простими, якщо їх (найбільший спільний дільник) НСД . Якщо для двох цілих чисел невідомі їх прості множники, то для визначення того, чи є вони взаємно простими, використовується (алгоритм Евкліда); алгоритм виконується за (поліноміальний час) за кількістю цифр.
Ціле число 1 є взаємно простим для будь-якого додатного цілого числа, включно з самим собою. Іншими словами, число 1 не має простих множників, воно — [en]. Це означає, що НСД для будь-якого .
Криптографічні застосування
Визначення простих множників числа — це приклад задачі, яка часто використовується для забезпечення криптографічного захисту в системах (шифрування). Передбачається, що ця задача вимагає (супер-поліноміального часу) за кількістю цифр. Це означає, що відносно легко сконструювати задачу, вирішення якої зайняло б більше часу, ніж відомий (вік Всесвіту) за поточного розвитку комп'ютерів і за допомогою сучасних алгоритмів.
Функції Омега
Функція ω(n) (омега) являє собою число різних простих множників n, у той час як функція Ω(n) (велика Омега) являє собою число простих множників n перелічене з урахуванням кратності. Якщо
тоді
Наприклад, 24 = 23 × 31 Так що ω(24) = 2 і Ω(24) = 3 + 1 = 4
Див. також
- (Складене число)
- (Факторизація цілих чисел) — алгоритмічна проблема знаходження простих множників заданого числа
- (Подільність)
- (Таблиця простих множників)
- (Решето Ератосфена)
- [ru]
- Криптографічна стійкість
Посилання
- 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
- Melvyn B. Nathanson (1996). Additive Number Theory: the Classical Bases. Graduate Texts in Mathematics. Т. 234. Springer-Verlag. ISBN .
- Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. (October 1996). . CRC Press. ISBN . Архів оригіналу за 7 березня 2005. Процитовано 27 грудня 2019.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет