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

Число и сумма делителей, НОД и НОК, алгоритм Евклида и его расширенная версия — связки, на которых стоит вся арифметика.

НОД(a, b) — наибольшее число, делящее и a, и b; НОК(a, b) — наименьшее число, кратное обоим.

Зачем это в олимпиадах

НОД и НОК — самые частые операции теории чисел: сокращение дробей, синхронизация периодов («через сколько секунд лампочки мигнут одновременно»), приведение к общему знаменателю, проверка взаимной простоты. Число делителей τ(n) и их сумма σ(n) встречаются в задачах про «совершенные числа», «сколько прямоугольников», делительные функции. А расширенный алгоритм Евклида — это вход в модулярную арифметику: через него находят обратный элемент по модулю и решают линейные диофантовы уравнения. Эти инструменты вы будете применять буквально в каждом втором номере.

Число и сумма делителей через разложение

Основная теорема арифметики даёт красивые формулы. Пусть n = p₁a₁ · … · pₖaₖ. Любой делитель получается выбором степени каждого простого от 0 до aᵢ. Значит число делителей:

τ(n) = (a₁ + 1)(a₂ + 1)…(aₖ + 1)

Сумма делителей считается так же по принципу произведения: для каждого простого складываем геометрическую прогрессию его степеней, а ответы перемножаем:

σ(n) = ∏ᵢ (1 + pᵢ + pᵢ2 + … + pᵢaᵢ) = ∏ᵢ (pᵢaᵢ+1 − 1)/(pᵢ − 1)

def factorize(n):
    f = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            f[d] = f.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        f[n] = f.get(n, 0) + 1
    return f

def num_divisors(n):
    res = 1
    for a in factorize(n).values():
        res *= (a + 1)
    return res

def sum_divisors(n):
    res = 1
    for p, a in factorize(n).items():
        res *= (p ** (a + 1) - 1) // (p - 1)  # 1 + p + ... + p^a
    return res

print(num_divisors(360), sum_divisors(360))  # 360 = 2^3*3^2*5
# проверка перебором
def brute(n):
    divs = [d for d in range(1, n + 1) if n % d == 0]
    return len(divs), sum(divs)
print(brute(360))

Вывод:

24 1170
(24, 1170)

Формула совпала с честным перебором. Заметьте: перебор работает за O(n), а через разложение — за O(√n). На больших n разница принципиальна.

Алгоритм Евклида для НОД

Идея гениально проста и опирается на свойство линейных комбинаций: НОД(a, b) = НОД(b, a mod b). Почему? Любой общий делитель a и b делит и a − q·b = a mod b; и наоборот, общий делитель b и a mod b делит a. Значит множества общих делителей у пар (a, b) и (b, a mod b) совпадают, а с ними и наибольший. Повторяем, пока второе число не станет нулём — тогда НОД равен первому.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b   # делим ДО умножения, чтобы не раздувать число

print(gcd(48, 36), lcm(48, 36))
print(gcd(1071, 462))          # классический пример: 21
print(gcd(17, 0))              # НОД с нулём = само число

Вывод:

12 144
21
17

Алгоритм Евклида работает за O(log min(a, b)) — число шагов ограничено логарифмом, потому что остаток убывает минимум вдвое за два шага (худший случай — соседние числа Фибоначчи). НОК выражается через НОД тождеством a·b = НОД(a,b)·НОК(a,b); в коде делим до умножения, чтобы промежуточный результат не переполнялся (в C++ это критично; в Python — лишь вопрос скорости, ведь переполнения нет).

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

Соотношение Безу утверждает: для любых a, b существуют целые x, y такие, что a·x + b·y = НОД(a, b). Расширенный Евклид находит эти x, y попутно с НОД. Рекуррентность выводится так. В базе b = 0: НОД = a, и a·1 + 0·0 = a, то есть x = 1, y = 0. Пусть для пары (b, a mod b) мы нашли (x₁, y₁): b·x₁ + (a mod b)·y₁ = g. Подставим a mod b = a − ⌊a/b⌋·b и сгруппируем:

x = y₁,   y = x₁ − ⌊a/b⌋ · y₁

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0           # gcd, x, y
    g, x1, y1 = ext_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

g, x, y = ext_gcd(240, 46)
print(g, x, y)
print(240 * x + 46 * y)          # должно равняться g
# применение: обратный к 3 по модулю 7
g, x, _ = ext_gcd(3, 7)
print(x % 7, (3 * (x % 7)) % 7)  # обратный и проверка

Вывод:

2 -9 47
2
5 1

Проверка 240·(−9) + 46·47 = −2160 + 2162 = 2 — всё сходится. Найденный x может быть отрицательным; чтобы получить корректный обратный элемент по модулю, берём x % m (в Python это сразу даёт неотрицательное значение). Здесь обратный к 3 по модулю 7 равен 5, ведь 3·5 = 15 ≡ 1 (mod 7). Эту технику мы детально разберём в разделе про модулярную арифметику.

Функция Эйлера: ещё одно применение разложения

Из НОД естественно вырастает функция Эйлера φ(n) — количество чисел от 1 до n, взаимно простых с n. Она встречается в теореме Эйлера (обобщение Ферма), при подсчёте обратимых элементов, в задачах на дроби. Считается через разложение: φ(n) = n · ∏(1 − 1/p) по всем простым делителям p. Интуиция — включения-исключения: из n чисел вычёркиваем кратные каждого простого делителя.

import math

def euler_phi(n):
    result = n
    m = n
    p = 2
    while p * p <= m:
        if m % p == 0:
            while m % p == 0:
                m //= p
            result -= result // p      # умножаем на (1 - 1/p)
        p += 1
    if m > 1:                          # последний простой делитель
        result -= result // m
    return result

print(euler_phi(36), euler_phi(10), euler_phi(7))
# проверка перебором: считаем взаимно простые
def phi_brute(n):
    return sum(1 for k in range(1, n + 1) if math.gcd(k, n) == 1)
print(phi_brute(36), phi_brute(10), phi_brute(7))

Вывод:

12 4 6
12 4 6

Формула совпала с прямым подсчётом: у 36 ровно 12 взаимно простых меньших чисел, у простого 7 — все шесть предыдущих (как и должно быть, φ(p) = p−1 для простого p). Считается за O(√n) против O(n·log n) у перебора с НОД. Эту функцию мы используем в модулярной арифметике для обратного элемента по составному модулю.

Подводные камни

• НОК через произведение. Пишите a // gcd(a, b) * b, а не a * b // gcd(a, b): в языках с фиксированным int первое не переполняется, второе может.
• Знак x в Безу. Коэффициент может быть отрицательным — для обратного элемента приводите по модулю.
• gcd(0, 0). Формально не определён; в коде вернётся 0 — учитывайте крайний случай.
• Сумма делителей и перелив. σ(n) растёт быстро; в C++ берут long long или модуль. В Python — спокойно, числа длинные.

Итог

• τ(n) = ∏(aᵢ+1), σ(n) = ∏(pᵢaᵢ+1−1)/(pᵢ−1) — прямо из разложения.
• Евклид: НОД(a,b) = НОД(b, a mod b) за O(log min).
• НОК(a,b) = a/НОД · b; делим до умножения.
• Расширенный Евклид находит x, y в a·x + b·y = НОД — вход в обратный элемент по модулю.