Теорія чисел: від простих до теореми Ферма

Теорія чисел — один із найстаріших розділів математики, присвячений вивченню цілих чисел та їх властивостей. Гаусс називав її «царицею математики». Незважаючи на простоту формулювань задач (наприклад, гіпотеза Гольдбаха), доведення найчастіше виявляються надзвичайно складними.

1. Основна теорема арифметики (ОТА)

Основна теорема арифметики

Кожне натуральне число n > 1 можна єдиним чином розкласти у добуток простих чисел (з точністю до порядку): n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ Приклади: 360 = 2³ · 3² · 5 1001 = 7 · 11 · 13 2⁶³ − 1 = 761 838 257 287 · 529 510 939 (не просте!) Наслідки: НСД(a,b), НСК(a,b), кількість дільників τ(n)

2. Прості числа і решето Ератосфена

Число p > 1, яке ділиться лише на 1 і p, називається простим. Решето Ератосфена (≈240 до н.е.) — елегантний алгоритм знаходження всіх простих до N за час O(N log log N):

2436 5879 10111312 1719232931 37414347

Решето Ератосфена (псевдокод)

Вхід: N 1. Ініціалізуй A[2..N] = True 2. Для p від 2 до √N: якщо A[p] = True: для j = p² до N з кроком p: A[j] = False 3. Виведи всі p, де A[p] = True Складність: O(N log log N) часу, O(N) пам'яті

3. Теорема про розподіл простих (PNT)

Скільки простих чисел до N? Теорема Чебишева–Адамара–де ла Валле Пуссена (1896) дає точну відповідь:

Теорема про розподіл простих (Prime Number Theorem)

π(x) ~ x / ln(x) при x → ∞ де π(x) = |{p ≤ x : p — просте}| Точніша оцінка (логарифмічний інтеграл): π(x) ~ Li(x) = ∫₂ˣ dt / ln(t) Числові значення: π(10³) = 168 ≈ 1000/ln(1000) ≈ 145 π(10⁶) = 78 498 ≈ 10⁶/ln(10⁶) ≈ 72 382 π(10⁹) = 50 847 534 π(10¹²) ≈ 37.6 · 10⁹ Гіпотеза Рімана → точна похибка |π(x) − Li(x)| = O(√x ln x)

4. Китайська теорема про залишки (КТЗ)

Китайська теорема про залишки

Якщо m₁, m₂, …, mₖ — попарно взаємно прості, тоді система конгруенцій: x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂) ⋮ x ≡ aₖ (mod mₖ) має єдиний розв'язок modulo M = m₁·m₂·…·mₖ. Алгоритм: M = m₁·m₂·…·mₖ Mᵢ = M / mᵢ yᵢ = Mᵢ⁻¹ mod mᵢ (обернений елемент) x = Σ aᵢ·Mᵢ·yᵢ (mod M) Приклад: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) M = 105, M₁=35, M₂=21, M₃=15 x ≡ 2·35·2 + 3·21·1 + 2·15·1 = 140+63+30 = 233 ≡ 23 (mod 105)

Застосування: RSA-криптографія, конгруенції у хешуванні, паделеві числа

5. Мала теорема Ферма і тест Міллера–Рабіна

Мала теорема Ферма (Fermat, 1640)

Якщо p — просте і НСД(a, p) = 1, тоді: aᵖ⁻¹ ≡ 1 (mod p) Еквівалентно: aᵖ ≡ a (mod p) для будь-якого a Наслідки: • Числа Кармайкла: складені n, де aⁿ⁻¹ ≡ 1 для всіх НСД(a,n)=1 Найменше: 561 = 3·11·17 Тест Міллера–Рабіна (імовірнісний, O(k·log²n)): 1. Запиши n−1 = 2ˢ·d 2. Обери випадкове a ∈ (1,n) 3. Перевіряй aᵈ, a²ᵈ, …, a²^(ˢ⁻¹)ᵈ mod n 4. Якщо жодне ≡ ±1 → складене; k раундів → похибка ≤ 4⁻ᵏ

6. Числа Мерсенна і досконалі числа

p	Mₚ = 2ᵖ−1	Просте?	Знайдено
2	3	✅	Стародавні
3	7	✅	Стародавні
5	31	✅	Стародавні
7	127	✅	Стародавні
11	2047 = 23·89	❌	—
13	8191	✅	1461
61	2³⁰⁵³−1 (921 цифр)	✅	1883
82589933	2⁸²⁵⁸⁹⁹³³−1 (≈25M цифр)	✅	2018 (найбільше відоме)

Досконалі числа та теорема Ейлера

Число n досконале якщо σ(n) = Σ d = 2n d|n Парне досконале ⟺ n = 2ᵖ⁻¹ · (2ᵖ−1), де 2ᵖ−1 просте (Теорема Евкліда–Ейлера) Перші: 6 = 1+2+3, 28 = 1+2+4+7+14 496, 8128, 33550336… Непарне досконале: невідоме, але якщо існує → > 10¹⁵⁰⁰

7. Велика теорема Ферма — 358 років загадки

Велика теорема Ферма (Fermat, 1637 → Wiles, 1995)

Для цілих n > 2 не існує натуральних a, b, c таких, що: aⁿ + bⁿ = cⁿ Ферма записав: «Я знайшов справді чудовий доказ, але береги цієї книги занадто малі, щоб його вмістити» Доведення Ендрю Вайлса (1995): 1. Теорема про модулярність Таніями–Шимури–Вея (кожна еліптична крива над ℚ є модулярною) 2. = Рибет 1986: гіпотеза Сера → FLT 3. = Вайлс 1995: доводить TSW для напівстабільних кривих Рівняння еліптичної кривої: y² = x³ + ax + b (дискримінант ≠ 0)

8. Гіпотеза Гольдбаха — нерозв'язана до сьогодні

Гіпотеза Гольдбаха (1742): Кожне парне число > 2 є сумою двох простих. Наприклад: 4=2+2, 6=3+3, 100=3+97=11+89=17+83=29+71=41+59=47+53. Перевірено до 4·10¹⁸, але не доведено задовільно.

Гіпотеза Рімана (1859): Всі нетривіальні нулі ζ-функції Рімана мають Re(s)=½. Задача тисячоліття ($1M), нерозв'язана. Еквівалентна найточнішій оцінці похибки в PNT.

Часті запитання

Скільки простих чисел? Безліч (доказ Евкліда: від протилежного — добуток усіх +1 не ділиться на жодне з них).

Чи є простими близнюками безліч? Гіпотеза простих-близнюків (p, p+2): ймовірно так, але не доведено.

Де застосовується теорія чисел? RSA-криптографія, гешування, псевдовипадкові числа, коди коригування помилок.

Про цю статтю

Ця стаття є частиною бази знань calculator.party — освітнього ресурсу, що поєднує теорію з практичними інструментами. Матеріал орієнтований на студентів, учнів і фахівців, що прагнуть глибокого розуміння теми. Тут зібрані ключові концепції, формули та реальні приклади застосування.

Статистика — мова даних. Без неї неможливі медичні дослідження, соціологія, фінанси, Data Science та державне управління. Вміння читати та інтерпретувати статистику є ключовою навичкою XXI ст.

Навіщо читати цю статтю

Після прочитання ви зможете впевнено пояснити тему, вирішувати практичні задачі та застосовувати знання у навчанні й роботі. Стаття охоплює теоретичне підґрунтя і числові приклади, що полегшують запам'ятовування матеріалу.

Часті запитання (FAQ)

Що таке Теорія чисел: від простих до теореми Ферма і чому це важливо знати?

Теорія чисел: від простих до теореми Ферма — ключова тема в різних галузей науки. Розуміння її основ дає змогу вирішувати практичні задачі, успішно складати іспити та застосовувати знання в реальних ситуаціях. Стаття розкриває концепцію доступними словами з конкретними прикладами.

Які ключові формули та методи використовуються в теорія чисел: від простих до теореми ферма?

Основні формули та методи для теорія чисел: від простих до теореми ферма охоплюють як аналітичні підходи, так і числові алгоритми. У статті наведені всі ключові вирази з поясненням кожного позначення та вказівкою одиниць вимірювання.

Де в реальному житті застосовується теорія чисел: від простих до теореми ферма?

Сфери застосування теорія чисел: від простих до теореми ферма надзвичайно широкі: освіті, науці, інженерії та повсякденному житті. Знання цієї теми відкриває кар'єрні можливості в інженерії, науці, фінансах та IT-галузі.

Як розрахувати теорія чисел: від простих до теореми ферма онлайн?

На calculator.party є безкоштовні онлайн-калькулятори з тематики 'Теорія чисел: від простих до теореми Ферма'. Достатньо ввести вхідні дані — і ви миттєво отримаєте точний результат з покроковим поясненням. Це ідеально для перевірки ручних розрахунків.

Яка різниця між теорія чисел: від простих до теореми ферма та суміжними темами?

Стаття чітко описує межі тематики 'Теорія чисел: від простих до теореми Ферма', порівнюючи її з близькими поняттями. Чітке розуміння відмінностей допомагає уникнути типових помилок та плутанини при розв'язанні задач.