Теорія чисел

🔢 Що таке теорія чисел?

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

🎯 Основні розділи теорії чисел:

Елементарна теорія чисел - основні властивості цілих чисел

Аналітична теорія чисел - застосування аналізу

Алгебраїчна теорія чисел - алгебраїчні методи

Геометрична теорія чисел - геометричні підходи

Обчислювальна теорія чисел - алгоритми та обчислення

🔢 Прості числа

1. Визначення та властивості

Прості числа - це основні будівельні блоки теорії чисел:

🔢 Просте число

Визначення:

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

🔢 Властивості простих чисел

Безліч простих чисел: • 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... • Єдине парне просте число - 2 • Всі інші прості числа непарні • Безліч простих чисел нескінченна

Теорема Евкліда: • Простих чисел нескінченно багато • Доведення від супротивного • Конструкція нового простого • Класичне доведення

🔢 Решето Ератосфена

Алгоритм знаходження простих чисел: • Викреслюємо всі числа, кратні 2 • Викреслюємо всі числа, кратні 3 • Продовжуємо для всіх простих чисел • Залишаються тільки прості числа

Складність: • O(n log log n) операцій • Ефективний для малих n • Пам'ять O(n) • Оптимізації

🔢 Теорема про розподіл простих чисел

Теорема про простих числах: • π(x) ~ x/ln(x) • π(x) - кількість простих ≤ x • Асимптотична формула • Точніші оцінки

Гіпотеза Рімана: • Зв'язана з нулями ζ-функції • Найважливіша невирішена проблема • Вплив на розподіл простих • Спроби доведення

2. Тести простоти

Алгоритми перевірки простоти числа:

🔢 Тест простоти

Детерміністичні тести:

Ймовірнісні тести:

p - просте число, якщо p > 1 та єдині дільники p - це 1 та p

🔢 Ділимість та НСД

1. Найбільший спільний дільник

Фундаментальне поняття теорії чисел:

🔢 НСД та НСК

Визначення:

Властивість:

🔢 Алгоритм Евкліда

Обчислення НСД: • НСД(a,b) = НСД(b, a mod b) • Рекурсивний алгоритм • Складність O(log min(a,b)) • Розширений алгоритм

Розширений алгоритм: • Знаходить x, y: ax + by = НСД(a,b) • Лінійна діофантова комбінація • Застосування в криптографії • Обернені елементи

🔢 Лема Безу

Формулювання: • Для будь-яких a, b ∈ ℤ • Існують x, y ∈ ℤ • ax + by = НСД(a,b) • Не єдині

Застосування: • Розв'язання діофантових рівнянь • Криптографія • Теорія кілець • Алгебраїчна геометрія

🔢 Теорема про унікальну факторизацію

Основна теорема арифметики: • Кожне n > 1 єдиним способом • n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ • pᵢ - різні прості • aᵢ - натуральні

Наслідки: • Єдиність розкладу • Алгоритми факторизації • Криптографія • Теорія кілець

НСД(a,b) = max{d | d|a та d|b}

🔢 Конгруенції

1. Модульна арифметика

Арифметика залишків при діленні:

🔢 Конгруенція

Визначення:

Властивості:

🔢 Арифметика конгруенцій

Операції: • a ≡ b (mod n), c ≡ d (mod n) • ⇒ a + c ≡ b + d (mod n) • ⇒ a - c ≡ b - d (mod n) • ⇒ a·c ≡ b·d (mod n)

Степені: • a ≡ b (mod n) • ⇒ aᵏ ≡ bᵏ (mod n) • Для всіх k ∈ ℕ • Застосування в криптографії

🔢 Класи залишків

Визначення: • [a]ₙ = {b ∈ ℤ | b ≡ a (mod n)} • Клас залишків за модулем n • ℤ/nℤ = {[0], [1], ..., [n-1]} • Кільце залишків

Операції в ℤ/nℤ: • [a] + [b] = [a + b] • [a] · [b] = [a · b] • Нейтральні елементи • Обернені елементи

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

Формулювання: • n₁, n₂, ..., nₖ - попарно взаємно прості • Система x ≡ aᵢ (mod nᵢ) • Має єдине рішення mod n₁n₂...nₖ • Конструктивне рішення

Застосування: • RSA криптосистема • Паралельні обчислення • Теорія кілець • Алгоритми

2. Теорема Ферма та Ейлера

Фундаментальні теореми модульної арифметики:

🔢 Теореми Ферма та Ейлера

Мала теорема Ферма:

Теорема Ейлера:

Функція Ейлера:

a ≡ b (mod n) ⇔ n | (a - b)

🔢 Квадратичні залишки

1. Визначення та властивості

Квадратичні залишки та їх властивості:

🔢 Квадратичний залишок

Визначення:

Символ Лежандра:

🔢 Критерій Ейлера

Формулювання: • p - непарне просте • (a/p) ≡ a^((p-1)/2) (mod p) • Критерій квадратичності • Ефективний алгоритм

Застосування: • Тест простоти • Криптографія • Алгоритми • Теорія чисел

🔢 Квадратичний закон взаємності

Закон Гауса: • p, q - непарні прості • (p/q)(q/p) = (-1)^((p-1)(q-1)/4) • Фундаментальний закон • Доведення Гауса

Наслідки: • Обчислення символів Лежандра • Алгоритми • Теорія чисел • Застосування

🔢 Доповнення до закону взаємності

Перше доповнення: • (-1/p) = (-1)^((p-1)/2) • Квадратичність -1 • Залежність від p mod 4 • Доведення

Друге доповнення: • (2/p) = (-1)^((p²-1)/8) • Квадратичність 2 • Залежність від p mod 8 • Доведення

a - квадратичний залишок mod p, якщо ∃x: x² ≡ a (mod p)

🔢 Діофантові рівняння

1. Лінійні діофантові рівняння

Рівняння виду ax + by = c:

🔢 Лінійне діофантове рівняння

ax + by = c має розв'язок ⇔ НСД(a,b) | c

Загальний розв'язок:

🔢 Рівняння Пелля

Формулювання: • x² - dy² = 1 • d - не квадрат • Має нескінченно багато розв'язків • Фундаментальний розв'язок

Метод розв'язання: • Ланцюгові дроби • Рекурентні співвідношення • Алгоритми • Застосування

🔢 Велика теорема Ферма

Формулювання: • xⁿ + yⁿ = zⁿ • n > 2 • Немає розв'язків в ℕ • Доведена Ендрю Вайлсом

Історія доведення: • 350 років пошуків • Модулярні форми • Еліптичні криві • Теорема Таніями-Шимури

🔢 Рівняння Піфагора

Формулювання: • x² + y² = z² • Піфагорові трійки • Параметричний розв'язок • x = m² - n², y = 2mn, z = m² + n²

Властивості: • Примітивні трійки • НСД(m,n) = 1 • m, n різної парності • Геометричний зміст

x = x₀ + (b/d)t, y = y₀ - (a/d)t, де d = НСД(a,b)

🔢 Алгебраїчна теорія чисел

1. Алгебраїчні числа

Розширення теорії чисел на алгебраїчні числа:

🔢 Алгебраїчне число

Визначення:

Алгебраїчне ціле:

🔢 Кільця алгебраїчних цілих

Властивості: • ℤ[α] - кільце алгебраїчних цілих • Замкненість відносно операцій • Немає унікальної факторизації • Ідеали замість чисел

Приклади: • ℤ[√-1] = ℤ[i] - гаусові цілі • ℤ[√-5] - не має УФ • ℤ[√2] - кільце цілих • Застосування

🔢 Теорія ідеалів

Ідеали в кільцях: • Заміна чисел на ідеали • Унікальна факторизація ідеалів • Прості ідеали • Максимальні ідеали

Класи ідеалів: • Група класів ідеалів • Скінченність групи • Обчислення класів • Застосування

🔢 L-функції

Дзета-функція: • ζ(s) = Σ n^(-s) • Аналітичне продовження • Функціональне рівняння • Нулі функції

L-функції Діріхле: • L(s,χ) = Σ χ(n)n^(-s) • Характери Діріхле • Аналітичні властивості • Гіпотеза Рімана

α - алгебраїчне число, якщо ∃f(x) ∈ ℚ[x]: f(α) = 0

🔢 Застосування

1. Криптографія

Теорія чисел в захисті інформації:

🔢 RSA криптосистема

Математична основа: • Теорема Ейлера • Функція Ейлера φ(n) • Китайська теорема про залишки • Складність факторизації

Алгоритм: • Генерація ключів • Шифрування: c = m^e (mod n) • Розшифрування: m = c^d (mod n) • Безпека

🔢 Еліптичні криві

Математична основа: • Еліптичні криві над полями • Група точок кривої • Дискретний логарифм • Складність обчислень

Криптографічні схеми: • ECDSA - цифровий підпис • ECDH - обмін ключами • ECIES - шифрування • Переваги над RSA

🔢 Квантова криптографія

Математична основа: • Лінійна алгебра над ℂ • Унітарні оператори • Теорія груп • Квантові алгоритми

Протоколи: • BB84 - розподіл ключів • E91 - ентанглемент • SARG04 - детекція • Безпека

2. Обчислювальна теорія чисел

Алгоритми та обчислення в теорії чисел:

🔢 Алгоритми факторизації

Методи: • Решето Ератосфена • Метод пробних ділень • ρ-алгоритм Поларда • Квадратичне решето

Складність: • Експоненціальна • Підекспоненціальна • Поліноміальна • Квантові алгоритми

🔢 Тести простоти

Детерміністичні: • Тест АКС • Поліноміальний • Практично повільний • Теоретичний інтерес

Ймовірнісні: • Тест Міллера-Рабіна • Ефективний • Практичний • Застосування

🔢 Дискретний логарифм

Проблема: • g^x ≡ h (mod p) • Знайти x • Складність • Алгоритми

Методи: • Baby-step giant-step • Index calculus • Pollard's rho • Квантові алгоритми

🎯 Висновки

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

📚 Пов'язані теми

Математика

Алгебра

Криптографія

Алгебраїчна теорія чисел

Аналітична теорія чисел

🔢 Розділи теорії чисел

Прості числа

Ділимість

Конгруенції

Квадратичні залишки

Діофантові рівняння

🔬 Основні поняття

Прості числа

НСД та НСК

Конгруенції

Квадратичні залишки

Алгебраїчні числа

⚡ Застосування

Криптографія

Обчислювальна математика

Теорія кілець

Алгебраїчна геометрія

Фізика

📖 Рекомендована література

"An Introduction to the Theory of Numbers" - Hardy & Wright

"A Course in Number Theory" - Rose

"Number Theory" - Niven, Zuckerman, Montgomery

"Elementary Number Theory" - Burton

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Spirograph і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.