Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Що вивчає теорія чисел?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Теорія чисел** - розділ математики про властивості цілих чисел і близьких до них структур: подільність, прості числа та їхній розподіл, арифметику за модулем (конгруенції), розв'язки діофантових рівнянь, а також алгоритми, побудовані на цих ідеях (наприклад, для криптографії). **Ключове:** будь-яке натуральне число > 1 єдиним чином розкладається на прості множники - це основна теорема арифметики, на якій тримається вся теорія чисел.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Що вивчає теорія чисел? ### Коротка відповідь Теорія чисел - розділ математики про властивості цілих чисел і близьких до них структур: подільність, прості числа та їхній розподіл, арифметику за модулем (конгруенції), розв'язки діофантових рівнянь, а також алгоритми, побудовані на цих ідеях (наприклад, для криптографії). ### Розгорнута відповідь #### Визначення і предмет галузі Теорія чисел вивчає натуральні й цілі числа, їх розклад на прості множники, подільність, порівняння за модулем, а також рівняння, у яких розв'язки шукаються в цілих або раціональних числах (діофантові рівняння). Сучасна теорія чисел спирається на інструменти аналізу, алгебри та обчислювальної математики. #### Ключові розділи та ідеї - Подільність і алгоритми. - НСД, алгоритм Евкліда, лема Безу: для цілих a, b існують x, y такі, що ax + by = gcd(a, b). - Основна теорема арифметики: будь-яке n > 1 єдиним чином подається у вигляді добутку простих степенів. - Прості числа та факторизація. - Тести простоти (Міллера-Рабіна), методи факторизації (ρ-метод Полларда, квадратичне решето). - Розподіл простих: скільки простих не перевищує x. - Конгруенції та арифметика за модулем. - a ≡ b (mod m) означає, що m ділить a − b; можна додавати, множити й підносити до степеня «за модулем». - Мала теорема Ферма: a^(p−1) ≡ 1 (mod p) при простому p і gcd(a, p)=1. Теорема Ейлера: a^φ(m) ≡ 1 (mod m), якщо gcd(a, m)=1. - Китайська теорема про остачі: система порівнянь за взаємно простими модулями зводиться до одного порівняння за добутком модулів. - Діофантові рівняння. - Лінійні: ax + by = c мають розв'язки в цілих тоді й лише тоді, коли gcd(a, b) ділить c. - Класичні нелінійні: рівняння Пелля x^2 − Dy^2 = 1, піфагорові трійки, рівняння Морделла й еліптичні криві. - Аналітична теорія чисел. - Теорема про розподіл простих: π(x) ~ x / ln x. - Дзета-функція Рімана та L-функції як інструменти дослідження розподілу простих. - Алгебраїчна теорія чисел. - Кільця алгебраїчних цілих, розклад простих у розширеннях числових полів, ідеали та групи класів. - Обчислювальна теорія чисел і криптографія. - Практичні алгоритми: швидкі тести простоти, піднесення до степеня за модулем, розширений алгоритм Евкліда, китайська теорема в алгоритмічному вигляді. - Застосування: RSA, Diffie-Hellman, еліптичні криві, підписи та протоколи. - Адитивна та комбінаторна теорія чисел. - Суми множин, теореми типу Шнірельмана-Рота, гіпотези Гольдбаха та Варінга. #### Типові приклади задач і тверджень - Перевірити, чи є число простим; знайти розклад на прості множники для помірно великих чисел. - Розв'язати порівняння a·x ≡ b (mod m) або систему порівнянь із взаємно простими модулями (КТО). - Знайти НСД(a, b) і коефіцієнти Безу x, y такі, що ax + by = gcd(a, b). - Оцінити кількість простих до N і зрозуміти, чому алгоритми криптографії на великих числах працюють. #### Практичні приклади в коді (Python) ```python # Базові інструменти теорії чисел для практики def gcd(a: int, b: int) -> int: """Найбільший спільний дільник (алгоритм Евкліда).""" while b: a, b = b, a % b return abs(a) def extended_gcd(a: int, b: int): """Розширений алгоритм Евкліда: повертає (g, x, y), де ax + by = g = gcd(a, b).""" if b == 0: return (abs(a), 1 if a > 0 else -1, 0) g, x1, y1 = extended_gcd(b, a % b) return (g, y1, x1 - (a // b) * y1) def mod_inverse(a: int, m: int) -> int: """Обернений за модулем: знаходить x таке, що a*x ≡ 1 (mod m), якщо gcd(a, m) = 1.""" g, x, _ = extended_gcd(a, m) if g != 1: raise ValueError("Оберненого за модулем не існує") return x % m def is_probable_prime(n: int) -> bool: """Імовірнісний тест Міллера-Рабіна для n > 3 (достатній для практики). Для малих n обробляємо тривіально. """ if n < 2: return False small_primes = [2, 3, 5, 7, 11] if n in small_primes: return True for p in small_primes: if n % p == 0: return False # подаємо n-1 = 2^r * d, де d непарне d = n - 1 r = 0 while d % 2 == 0: d //= 2 r += 1 # фіксований набір основ, достатній для помірних n bases = [2, 3, 5, 7, 11] for a in bases: if a % n == 0: continue x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(r - 1): x = pow(x, 2, n) if x == n - 1: break else: return False return True def crt(remainders, moduli): """Китайська теорема про остачі: розв'язує систему x ≡ r_i (mod m_i) при попарно взаємно простих m_i. Повертає (x, M), де M = prod(m_i) і x - найменший невід'ємний розв'язок. """ M = 1 for m in moduli: M *= m x = 0 for r, m in zip(remainders, moduli): Mi = M // m inv = mod_inverse(Mi % m, m) x = (x + r * Mi * inv) % M return x, M if __name__ == "__main__": # НСД і коефіцієнти Безу a, b = 252, 198 g, x, y = extended_gcd(a, b) print("gcd:", g, "Перевірка Безу:", a * x + b * y) # Обернений за модулем і розв'язання лінійного порівняння a*x ≡ b (mod m) a, b, m = 7, 5, 26 g = gcd(a, m) if b % g == 0: a_, b_, m_ = a // g, b // g, m // g inv = mod_inverse(a_, m_) x0 = (inv * b_) % m_ print(f"Розв'язок a*x ≡ b (mod m): x ≡ {x0} (mod {m_})") # Китайська теорема про остачі: x ≡ 2 (mod 5), x ≡ 3 (mod 7) x, M = crt([2, 3], [5, 7]) print("CRT:", x, "mod", M) # 17 mod 35 # Імовірнісна перевірка простоти for n in [97, 221, 10**9 + 7]: print(n, "просте?", is_probable_prime(n)) # Міні-демо RSA (лише для навчальних цілей!) p, q = 61, 53 n = p * q phi = (p - 1) * (q - 1) e = 17 d = mod_inverse(e, phi) m = 42 c = pow(m, e, n) m2 = pow(c, d, n) print("RSA:", "n=", n, "e=", e, "d=", d, "cipher=", c, "decrypted=", m2) ``` #### Практичні застосування (в ІТ і на співбесідах) - Криптографія та безпека: RSA, ECDSA, протоколи обміну ключами - усе спирається на прості числа, модулярну арифметику та складність факторизації/логарифмування. - Хешування, шардування та розподілені системи: робота за модулем, вибір хороших модулів (зазвичай простих), оцінка колізій і рівномірності. - Оптимізація алгоритмів: швидке піднесення до степеня, обчислення НСД, обернених за модулем - часто трапляється в задачах на алгоритми та структури даних. - Контрольні суми, кодування, імовірнісні структури (Bloom-фільтри): вибір параметрів з урахуванням властивостей чисел. #### Ключові факти, які варто пам'ятати - Будь-яке натуральне число > 1 єдиним чином розкладається на прості множники. - gcd(a, b) можна швидко знаходити алгоритмом Евкліда; розширений варіант дає коефіцієнти для розв'язання лінійних порівнянь. - Якщо gcd(a, m) = 1, то існує обернений елемент a^{-1} за модулем m, і він єдиний за модулем m. - Малі теореми (Ферма, Ейлера) дають основу для швидких алгоритмів піднесення до степеня і тестів простоти.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.