www.wikidata.uk-ua.nina.az

Простий множник У теорії чисел прості множники прості дільники додатного цілого числа це прості числа які ділять це числ

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

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

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

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

в якому множники 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

Див. також

Посилання

  1. Jensen, Gary R. (2004). Arithmetic for Teachers: With Applications and Topics from Geometry. American Mathematical Society. 
  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). . CRC Press. ISBN 0-8493-8523-7. Архів оригіналу за 7 березня 2005. Процитовано 27 грудня 2019. 
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
U teoriyi chisel prosti mnozhniki prosti dilniki dodatnogo cilogo chisla ce prosti chisla yaki dilyat ce chislo bez ostachi bez zalishku 1 Vidiliti prosti mnozhniki dodatnogo cilogo chisla oznachaye perelichiti ci prosti mnozhniki razom z yih kratnostyami Proces viznachennya prostih mnozhnikiv nazivayetsya faktorizaciyeyu cilogo chisla Osnovna teorema arifmetiki stverdzhuye sho bud yake naturalne chislo mozhna podati u viglyadi yedinogo z tochnistyu do poryadku sliduvannya dobutku prostih mnozhnikiv 2 Ce zobrazhennya demonstruye znahodzhennya prostih mnozhnikiv chisla 864 Skorochenij sposib napisannya 2 5 3 3Shob skorotiti viraz prosti mnozhniki chasto podayutsya u viglyadi stepeniv prostih chisel kratnosti Napriklad 360 2 2 2 3 3 5 2 3 3 2 5 displaystyle 360 2 times 2 times 2 times 3 times 3 times 5 2 3 times 3 2 times 5 v yakomu mnozhniki 2 3 i 5 mayut kratnosti 3 2 i 1 vidpovidno Dlya prostogo mnozhnika r chisla n kratnist chisla p ce najbilshij z pokaznikiv stepenya a dlya yakih p a displaystyle p a dilit n bez ostachi Dlya dodatnogo cilogo chisla n kilkist prostih mnozhnikiv n i suma prostih mnozhnikiv n bez urahuvannya kratnosti ce prikladi arifmetichnih funkcij vid n aditivnih arifmetichnih funkcij 3 Zmist 1 Povnij kvadrat 2 Vzayemno prosti chisla 3 Kriptografichni zastosuvannya 4 Funkciyi Omega 5 Div takozh 6 PosilannyaPovnij kvadrat RedaguvatiKvadrat chisla maye vlastivist sho vsi jogo prosti mnozhniki mayut parni kratnosti Napriklad chislo 144 kvadrat 12 maye prosti mnozhniki 144 2 2 2 2 3 3 2 4 3 2 displaystyle 144 2 times 2 times 2 times 2 times 3 times 3 2 4 times 3 2 U bilsh zrozumilij formi 144 2 2 2 2 3 3 2 2 3 2 2 3 2 2 3 2 12 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 Oskilki kozhen prostij mnozhnik prisutnij tut parne chislo raziv vihidne chislo mozhna podati u viglyadi kvadrata deyakogo chisla Takim zhe chinom kub chisla ce chislo u yakogo kratnosti prostih mnozhnikiv dilyatsya na tri i tak dali Vzayemno prosti chisla RedaguvatiDodatni cili chisla sho ne mayut spilnih prostih mnozhnikiv nazivayutsya vzayemno prostimi Dva cilih chisla a i b mozhna nazvati vzayemno prostimi yaksho yih najbilshij spilnij dilnik NSD a b 1 displaystyle a b 1 Yaksho dlya dvoh cilih chisel nevidomi yih prosti mnozhniki to dlya viznachennya togo chi ye voni vzayemno prostimi vikoristovuyetsya algoritm Evklida algoritm vikonuyetsya za polinomialnij chas za kilkistyu cifr Cile chislo 1 ye vzayemno prostim dlya bud yakogo dodatnogo cilogo chisla vklyuchno z samim soboyu Inshimi slovami chislo 1 ne maye prostih mnozhnikiv vono porozhnij dobutok en Ce oznachaye sho NSD 1 b 1 displaystyle 1 b 1 dlya bud yakogo b 1 displaystyle b leq 1 Kriptografichni zastosuvannya RedaguvatiViznachennya prostih mnozhnikiv chisla ce priklad zadachi yaka chasto vikoristovuyetsya dlya zabezpechennya kriptografichnogo zahistu v sistemah shifruvannya 4 Peredbachayetsya sho cya zadacha vimagaye super polinomialnogo chasu za kilkistyu cifr Ce oznachaye sho vidnosno legko skonstruyuvati zadachu virishennya yakoyi zajnyalo b bilshe chasu nizh vidomij vik Vsesvitu za potochnogo rozvitku komp yuteriv i za dopomogoyu suchasnih algoritmiv Funkciyi Omega RedaguvatiFunkciya w n omega yavlyaye soboyu chislo riznih prostih mnozhnikiv n u toj chas yak funkciya W n velika Omega yavlyaye soboyu chislo prostih mnozhnikiv n perelichene z urahuvannyam kratnosti 2 Yaksho n i 1 w n p i a i displaystyle n prod i 1 omega n p i alpha i todi W n i 1 w n a i displaystyle Omega n sum i 1 omega n alpha i Napriklad 24 23 31 Tak sho w 24 2 i W 24 3 1 4 w n dlya n 1 2 3 vidpovidno 0 1 1 1 1 2 1 1 1 poslidovnist A001221 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS W n dlya n 1 2 3 vidpovidno 0 1 1 2 1 2 1 3 2 poslidovnist A001222 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Div takozh RedaguvatiSkladene chislo Faktorizaciya cilih chisel algoritmichna problema znahodzhennya prostih mnozhnikiv zadanogo chisla Podilnist Tablicya prostih mnozhnikiv Resheto Eratosfena Teorema Erdesha Kaca ru Kriptografichna stijkistPosilannya Redaguvati Jensen Gary R 2004 Arithmetic for Teachers With Applications and Topics from Geometry American Mathematical Society a b Riesel Hans 1994 Prime numbers and computer methods for factorization Basel Switzerland Birkhauser 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 Arhiv originalu za 7 bereznya 2005 Procitovano 27 grudnya 2019 Otrimano z https uk wikipedia org w index php title Prostij mnozhnik amp oldid 37260634