Що вивчає теорія чисел?

АлгоритмиJunior~3 хв читання

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

Розгорнута відповідь

Визначення і предмет галузі

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

Ключові розділи та ідеї

Подільність і алгоритми.
- НСД, алгоритм Евкліда, лема Безу: для цілих 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.
Малі теореми (Ферма, Ейлера) дають основу для швидких алгоритмів піднесення до степеня і тестів простоти.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.