Прості множники: основа розкладання чисел
Кожне натуральне число, окрім одиниці, ховає в собі набір простих множників — тих самих “цеглинок”, з яких воно складається. Взяти 84: поділіть на 2 тричі, отримаєте 3 і 7. Отже, 84 = 2³ × 3 × 7. Ці прості числа ділять 84 без остачі, і саме вони визначають його суть. Розуміння простих множників відкриває двері до теорії чисел, де числа перестають бути просто цифрами на папері, а перетворюються на захоплюючу мозаїку.
Для початківців це базовий інструмент: перевірте подільність на 2, 3, 5 — і число розпадеться. Просунуті читачі знають, що за цим стоїть унікальність розкладу, гарантована Основною теоремою арифметики. А тепер зануримося глибше, розбираючи приклади крок за кроком, щоб ви могли самі розкладати будь-яке число, від шкільних задач до гігантських криптографічних викликів.
Прості числа: фундаментом усього
Без простих чисел немає простих множників. Просте число — натуральне більше за 1, яке ділиться лише на 1 і себе. 2, найменше і єдине парне просте, 3, 5, 7 — вони немов самотні вовки в лісі чисел, неподільні ні на що інше. Складені ж, як 4 чи 9, легко розпадаються.
Чому це важливо? Бо кожне число будується з простих, ніби вежа з кубиків Lego. Перші прості: 2, 3, 5, 7, 11, 13, 17, 19, 23… Їх безліч, і шукати нові — окреме мистецтво, від решета Ератосфена до сучасних суперкомп’ютерів.
- Переваги простих чисел: Унікальність у множенні, неможливість розкладу далі.
- Приклади перевірки: 17 не ділиться на 2,3,5 (√17≈4.1), отже просте.
- Факт для просунутих: Щільність простих падає, але нескінченна, як довів Евклід.
Цей фундамент дозволяє переходити до множників. Без нього розкладання — сліпа лотерея.
Що таке прості множники насправді
Прості множники додатного цілого числа — прості числа, що ділять його без залишку. З кратністю: для 360 це 2³ × 3² × 5. Кратність — скільки разів той самий простий повторюється. Виділення множників — факторизація, серце теорії чисел.
Число 1 не має множників — порожній добуток. Взаємно прості числа, як 8 і 15, не ділять спільних простих. Квадрат числа має парні кратності: 144=12²=2⁴×3².
Функції: ω(n) — кількість різних множників (для 24=2³×3 — 2), Ω(n) — з кратністю (4). Ці інструменти рахують “складність” числа.
Як розкладати число на прості множники: базові методи
Почніть з найменших простих. Метод стовпчиком: пишіть дільник праворуч від риски, частку знизу. Для 756:
- 756 ÷ 2 = 378
- 378 ÷ 2 = 189
- 189 ÷ 3 = 63
- 63 ÷ 3 = 21
- 21 ÷ 3 = 7
- 7 — просте.
Результат: 756 = 2² × 3³ × 7. Дерево факторів: від 756 розділіть на 2×378, 378 на 2×189 і 3×252 — розгалужується до простих.
Ознаки подільності прискорюють: на 2 — парне, на 3 — сума цифр. Для великих — перевірте до √n. Цей підхід ідеальний для шкільних задач, але для мільйонів цифр потрібні хитрощі.
Основна теорема арифметики: унікальність розкладу
Кожне n>1 — просте або добуток простих, і розклад унікальний (окрім порядку). Доведення існування: найменше неподільне — просте. Єдиність: перший простий зліва ділить правий бік, скорочуємо рекурсивно.
Приклад: 420=2²×3×5×7. Ніяк інакше. Чому 1 не просте? Бо руйнує унікальність: 2=2×1×1…. Ця теорема — скеля арифметики, від Евкліда до Гаусса. (uk.wikipedia.org)
Наслідки: НСД і НСКД через множники — беріть min/max кратностей.
Історія: від Евкліда до сучасності
Евклід у “Началах” (300 до н.е.) довів нескінченність простих і леми про розклад. XIV ст. — аль-Фарісі уточнив. XVII — Престет, XVIII — Ейлер. Гаусс у 1801 “Арифметичних дослідженнях” дав повне доведення: “кожне складене — унікальний добуток простих”.
Сьогодні — квантові загрози, але класика жива. Ця еволюція показує, як базова ідея росте в монстра обчислень.
Просунуті алгоритми факторизації
Для гігантів trial division (O(√n)) замалий. Ось порівняння:
| Алгоритм | Складність | Приклад | Застосування |
|---|---|---|---|
| Trial division | O(√n) | 100=2²×5² | Малі числа |
| Метод Ферма | O(√n) | 391=17×23 (20²-1²) | Близькі множники |
| Pollard ρ | O(n^{1/4}) | 187→11 | Середні дільники |
| ECM | Субекспоненційна | 20-30 цифр | Практика GMP-ECM |
| GNFS | O(exp((ln n)^{1/3})) | RSA-232 цифри | Рекорди |
Джерела: uk.wikipedia.org. Ці методи еволюціонували для криптоатаки, де час — ключ.
Ймовірнісні, як Pollard, шукають колізії в послідовностях. GNFS — король для надвеликих.
Застосування: криптографія та RSA
У RSA ключ — добуток двох величезних простих p,q (n=p×q, ~300 цифр). Шифрування легке, факторизація — ні. Зламайте n — отримайте приватний ключ. Безпека на складності розкладу.
Щодня мільярди транзакцій захищені. Квантовий алгоритм Шора загрожує, але класичні GNFS тримають форт. У програмуванні: Python sympy.factorint() — миттєво для середніх.
Типові помилки початківців
Включати 1 як множник: 30≠1×2×3×5 — 1 нейтральне. Забувати кратність: 12=2×6, а не 2×2×3. Не перевіряти до √n: 91=7×13, пропустите 7 — помилка. Плутати з усіма дільниками: множники тільки прості.
- Помилка: вважати 9 простим — ні, 3².
- Радість: дерево факторів візуалізує, уникайте повторів.
- Порада: завжди множте назад для перевірки.
Ці пастки коштують балів на тестах, але з практикою зникають. Спробуйте 1001=7×11×13 — класика обману.
Прості множники пронизують математику, від шкільних зошитів до квантових комп’ютерів. З ними числа оживають, відкриваючи таємниці коду світу. Експериментуйте з великими — і теорія чисел захопить назавжди.
