Делимость, простые числа, НОД и алгоритм Евклида

Начинаем теорию чисел с фундамента: делимость, простые числа и древнейший нетривиальный алгоритм — Евклидов.

Число a делится на b (b делит a), если существует целое k, такое что a = b·k. Записывают b | a.

Зачем программисту теория чисел

Теория чисел — внезапно одна из самых прикладных областей. На ней стоит вся современная криптография: RSA, обмен ключами, цифровые подписи — это арифметика остатков и простых чисел. Хеш-функции используют простые числа и модули. Алгоритм Евклида — один из старейших и до сих пор используется ежедневно (например, при сокращении дробей). Понимание делимости и модулярной арифметики — это ключ к безопасности данных и множеству алгоритмов. И начинается всё с простых, на первый взгляд, понятий.

Делимость и её свойства

Делимость — отношение на целых числах (вспомни: мы уже видели, что «делит» — частичный порядок). Несколько свойств, которые работают как инструменты:

• Если b | a и b | c, то b | (a + c) и b | (a − c) (делитель суммы и разности).
• Если b | a, то b | (a·m) для любого целого m.
• Делимость транзитивна: a | b и b | c ⇒ a | c.

Эти свойства — основа доказательств в теории чисел. Например, из них сразу следует, что сумма двух чётных чисел чётна (оба делятся на 2 ⇒ сумма делится на 2).

Простые числа — атомы умножения

Простое число — натуральное число больше 1, делящееся только на 1 и на само себя (2, 3, 5, 7, 11, ...). Остальные числа больше 1 называют составными. Простые — это «строительные блоки»: основная теорема арифметики гласит, что любое натуральное число больше 1 единственным образом раскладывается в произведение простых. Простые для чисел — как атомы для вещества.

Чтобы найти все простые до N, есть классический алгоритм — решето Эратосфена: выписываем числа от 2 до N и вычёркиваем кратные каждого найденного простого. Что осталось невычеркнутым — простые.

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):   # вычёркиваем кратные i
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

print("Простые числа до 30:", sieve(30))

Вывод:

Простые числа до 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Решето вычеркнуло все составные и оставило ровно простые. Маленькая оптимизация: внутренний цикл стартует с i·i, потому что меньшие кратные уже вычеркнуты предыдущими простыми. Решето Эратосфена — образец того, как простая идея даёт эффективный алгоритм; именно так находят простые для криптографии.

НОД, НОК и алгоритм Евклида

Наибольший общий делитель (НОД) двух чисел — наибольшее число, на которое делятся оба. Наименьшее общее кратное (НОК) — наименьшее число, которое делится на оба. Они связаны формулой НОД(a,b) · НОК(a,b) = a·b.

Как быстро найти НОД? Не раскладывая на множители! Алгоритм Евклида (ему более 2000 лет) основан на простом наблюдении: НОД(a, b) = НОД(b, a mod b). То есть НОД не меняется, если большее число заменить на остаток от деления на меньшее. Повторяем, пока второе число не станет нулём — тогда первое и есть ответ.

def gcd(a, b):
    while b:
        a, b = b, a % b      # ключевой шаг: (a, b) -> (b, a mod b)
    return a

print("НОД(48, 36) =", gcd(48, 36))
print("НОД(1071, 462) =", gcd(1071, 462))

# НОК через НОД
def lcm(a, b):
    return a * b // gcd(a, b)

print("НОК(4, 6) =", lcm(4, 6))
print("Проверка НОД·НОК = a·b:", gcd(12, 18) * lcm(12, 18) == 12 * 18)

Вывод:

НОД(48, 36) = 12
НОД(1071, 462) = 21
НОК(4, 6) = 12
Проверка НОД·НОК = a·b: True

Алгоритм Евклида находит НОД за считанные шаги даже для больших чисел — гораздо быстрее, чем раскладывать на множители. Почему он работает? Любой общий делитель a и b делит и их разность, а значит, и остаток a mod b. Поэтому множество общих делителей (и их максимум) при замене сохраняется. Это древний, элегантный и до сих пор незаменимый алгоритм.

Расширенный алгоритм Евклида

Есть мощное усиление: расширенный алгоритм Евклида находит не только НОД(a, b), но и целые коэффициенты x, y, такие что a·x + b·y = НОД(a, b) (соотношение Безу). Эти коэффициенты — ключ к нахождению обратных элементов по модулю, а значит, к расшифровке в RSA.

def egcd(a, b):
    if b == 0:
        return a, 1, 0           # НОД = a, x = 1, y = 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

g, x, y = egcd(240, 46)
print(f"НОД(240, 46) = {g}")
print(f"Коэффициенты: x = {x}, y = {y}")
print(f"Проверка: 240*({x}) + 46*({y}) = {240 * x + 46 * y}")

Вывод:

НОД(240, 46) = 2
Коэффициенты: x = -9, y = 47
Проверка: 240*(-9) + 46*(47) = 2

Алгоритм не только сказал, что НОД(240, 46) = 2, но и нашёл, как этот НОД выразить через сами числа: 240·(−9) + 46·47 = 2. Эта возможность «собрать НОД из исходных чисел» — фундамент модулярной арифметики и криптографии, к которой мы перейдём в следующих уроках.

Полином Жегалкина: ещё один взгляд на полноту

Есть красивый способ записать любую булеву функцию — через полином Жегалкина, используя всего две операции: исключающее ИЛИ (⊕) и И (∧), плюс константу 1. Любая функция представима как «сумма по модулю 2» произведений переменных, например f = 1 ⊕ a ⊕ (a ∧ b). Это значит, что система {⊕, ∧, 1} тоже полна — ещё один базис, отличный от привычного {И, ИЛИ, НЕ}.

Чем интересен этот взгляд? Функции, у которых полином Жегалкина не содержит произведений (только ⊕ переменных и констант), называются линейными — это один из пяти классов Поста. По полиному Жегалкина мгновенно видно, линейна функция или нет: достаточно посмотреть, есть ли в ней «нелинейные» слагаемые с ∧. Линейные функции связаны с кодами, исправляющими ошибки, и с криптографией (где, наоборот, ценят нелинейность, чтобы шифр было труднее взломать). Так разные базисы — это не просто академическая забава, а разные «языки», каждый из которых удобен для своих задач.

Типичные ошибки

• Считать 1 простым числом. По определению простое число больше 1. Единица — не простое и не составное.
• Раскладывать на множители ради НОД. Для больших чисел это медленно. Алгоритм Евклида находит НОД без факторизации — гораздо быстрее.
• Путать НОД и НОК. НОД — наибольший общий делитель (он не больше чисел), НОК — наименьшее общее кратное (оно не меньше чисел).

Итог

• Делимость b | a означает a = b·k; она транзитивна и сохраняется для сумм и кратных.
• Простые — атомы умножения; любое число единственно раскладывается на простые (основная теорема арифметики).
• Решето Эратосфена находит все простые до N вычёркиванием кратных.
• Алгоритм Евклида: НОД(a,b) = НОД(b, a mod b); расширенный даёт ещё и коэффициенты Безу.