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

Делитель целого числа a — это целое число d, не равное нулю, на которое a делится без остатка: a = d * k для некоторого целого k. Кратное числа d — любое число вида d * k. Это одна связь, увиденная с двух сторон: «3 — делитель 12» и «12 кратно 3» значат одно и то же. Ниже — как найти все делители числа, признаки делимости, НОД и НОК и алгоритм Евклида в коде (примеры проверены на Python 3.14.7, сентябрь 2026).

Мини-словарь: делитель, кратное, НОД, НОК

Граничные случаи, на которых путаются:

• у ненулевого числа конечное число делителей, но бесконечно много кратных; у нуля наоборот: его делит любое ненулевое число;
• 1 и само число всегда входят в делители (для n >= 1);
• 0 кратен любому числу (0 = d * 0), но делителем не бывает: на ноль не делят;
• в школе делители считают среди натуральных чисел; в теории чисел у 12 есть и делители -1, -2, …, -12. Дальше, если не сказано иное, речь о натуральных.

Частая ошибка в школьных пересказах — «у 21 два делителя: 3 и 7». На самом деле делителей четыре: 1, 3, 7, 21. Числа 3 и 7 — это нетривиальные делители (все, кроме 1 и самого числа). Собственными обычно называют все делители, кроме самого числа: у 21 это 1, 3 и 7.

Как найти все делители числа

Делители идут парами: если d делит n, то делит и n / d. Для 36 это пары 1-36, 2-18, 3-12, 4-9 и 6-6. Меньший элемент пары не больше корня из n, поэтому перебирать все числа до n не нужно — хватит проверить d от 1 до √n.

Прогоним руками для 36 (√36 = 6):

d = 1  -> 36 % 1 = 0 -> пара (1, 36)
d = 2  -> 36 % 2 = 0 -> пара (2, 18)
d = 3  -> 36 % 3 = 0 -> пара (3, 12)
d = 4  -> 36 % 4 = 0 -> пара (4, 9)
d = 5  -> 36 % 5 = 1 -> не делитель
d = 6  -> 36 % 6 = 0 -> пара (6, 6), это один делитель

Тот же алгоритм в коде:

import math

def divisors(n: int) -> list[int]:
    """Все натуральные делители n >= 1 за O(sqrt(n)) проверок."""
    if n < 1:
        raise ValueError("нужно натуральное n >= 1")
    small, large = [], []
    for d in range(1, math.isqrt(n) + 1):
        if n % d == 0:
            small.append(d)
            if d != n // d:          # у квадрата пара d*d - один делитель
                large.append(n // d)
    return small + large[::-1]

print(divisors(36))
print(divisors(21))
print(divisors(97))
print(len(divisors(720720)))

Вывод:

[1, 2, 3, 4, 6, 9, 12, 18, 36]
[1, 3, 7, 21]
[1, 97]
240

math.isqrt дает целый корень без погрешности float. Для 720 720 это 848 проверок вместо 720 720.

Ошибка: двойной счет у точного квадрата. Если добавлять оба элемента пары без проверки, делитель 6 у числа 36 попадет в список дважды:

import math

def divisors_bad(n):
    res = []
    for d in range(1, math.isqrt(n) + 1):
        if n % d == 0:
            res += [d, n // d]
    return sorted(res)

print(divisors_bad(36), len(divisors_bad(36)))

[1, 2, 3, 4, 6, 6, 9, 12, 18, 36] 10

Исправление — условие if d != n // d, как в рабочей версии. Ошибка видна только на точных квадратах: тест на 12 или 21 ее не поймает.

Простые и составные числа через делители

Простое число — натуральное число больше 1, у которого ровно два натуральных делителя: 1 и оно само (divisors(97) выше). Составное — натуральное число больше 1, у которого делителей больше двух. Единица не относится ни к тем, ни к другим: у нее один делитель.

Проверка на простоту перебором стоит O(√n), а не O(n): у делителя больше √n пара меньше √n и найдется раньше. Для чисел в сотни цифр применяют вероятностные тесты (например, Миллера — Рабина).

Если известно разложение n на простые множители n = p1^a1 * p2^a2 * …, то число делителей равно (a1 + 1)(a2 + 1)… Для 720 720 = 2^4 * 3^2 * 5 * 7 * 11 * 13 это 5 * 3 * 2 * 2 * 2 * 2 = 240, что совпадает с выводом кода. Само разложение на множители — отдельная тема.

Признаки делимости

Признаки делимости позволяют проверить делимость в уме по цифрам числа. В коде достаточно n % d == 0.

Почему они работают: 10 при делении на 9 (и на 3) дает остаток 1, поэтому любое число имеет тот же остаток, что и сумма его цифр. А 10 при делении на 11 дает остаток -1, отсюда знакопеременная сумма. Признак для 6 — частный случай общего правила: если число делится на два взаимно простых числа (НОД = 1), оно делится и на их произведение. Для 4 и 6 это не так: 12 делится на оба, но не на 24.

Проверим признаки кодом и сравним с прямой проверкой остатка на первом миллионе чисел:

def digit_sum(n):
    return sum(int(c) for c in str(n))

def alt_sum(n):
    # знакопеременная сумма цифр справа налево: + - + - ...
    return sum(int(c) * (-1) ** i for i, c in enumerate(reversed(str(n))))

for n in (4752, 4753):
    print(n, "сумма цифр", digit_sum(n), "-> на 3:", n % 3 == 0, "на 9:", n % 9 == 0)
    print(n, "знакоперем. сумма", alt_sum(n), "-> на 11:", n % 11 == 0)

# проверим признаки на первом миллионе чисел
ok = all((digit_sum(k) % 3 == 0) == (k % 3 == 0) and
         (digit_sum(k) % 9 == 0) == (k % 9 == 0) and
         (alt_sum(k) % 11 == 0) == (k % 11 == 0)
         for k in range(1, 1_000_001))
print(ok)

4752 сумма цифр 18 -> на 3: True на 9: True
4752 знакоперем. сумма 0 -> на 11: True
4753 сумма цифр 19 -> на 3: False на 9: False
4753 знакоперем. сумма 1 -> на 11: False
True

Прогон на миллионе чисел — проверка, а не доказательство; доказательство — рассуждение про остатки выше.

НОД и НОК

НОД (наибольший общий делитель) двух чисел — самое большое число, которое делит оба. НОК (наименьшее общее кратное) — самое маленькое положительное число, которое делится на оба. Для натуральных a и b они связаны формулой НОД(a, b) * НОК(a, b) = a * b. Для 84 и 36: НОД = 12, НОК = 252, и 12 * 252 = 3024 = 84 * 36.

Где что нужно:

Если НОД(a, b) = 1, числа называют взаимно простыми: 8 и 15 взаимно простые, хотя ни одно из них не простое.

Алгоритм Евклида: как быстро найти НОД

Алгоритм Евклида опирается на свойство НОД(a, b) = НОД(b, a mod b) и НОД(a, 0) = a. Делим с остатком, пока остаток не станет нулем; последний ненулевой остаток — НОД.

Для 84 и 36:

84 = 2*36 + 12
36 = 3*12 + 0

Остаток стал нулем, последний ненулевой — 12, значит НОД(84, 36) = 12. Реализация на Python:

import math

def gcd(a: int, b: int) -> int:
    """НОД по алгоритму Евклида (с делением с остатком)."""
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

def lcm(a: int, b: int) -> int:
    if a == 0 or b == 0:
        return 0
    return abs(a // gcd(a, b) * b)

print(gcd(84, 36), lcm(84, 36))
print(gcd(-12, 18), gcd(0, 5), gcd(0, 0))
print(math.gcd(84, 36), math.lcm(84, 36), math.gcd(12, 18, 30), math.lcm(4, 6, 10))

12 252
6 5 0
12 252 6 60

abs делает НОД положительным для отрицательных чисел. gcd(0, 0) = 0 — соглашение, принятое и в стандартной библиотеке. В рабочем коде берите math.gcd и math.lcm: с Python 3.9 они принимают любое число аргументов.

Алгоритм быстрый: число шагов растет как логарифм от меньшего числа. Худший случай — соседние числа Фибоначчи, где все частные, кроме последнего, равны 1. Для 89 и 55 нужно 9 делений с остатком, а для 1 000 000 и 999 999 — всего 2.

Ошибка: НОК через / на больших числах. Формула a * b / НОД верна математически, но оператор / в Python возвращает float, у которого 53 бита мантиссы:

import math
a, b = 2**61 - 1, 2**59 - 1          # два больших взаимно простых числа
bad = int(a * b / math.gcd(a, b))    # "/" дает float
good = a // math.gcd(a, b) * b
print(bad == good, good - bad)
print(math.lcm(a, b) == good)

False -2882303761517117439
True

Исправление — целочисленное деление //, причем до умножения: a // gcd(a, b) * b. В Python это только экономит память, а в C, C++ и Java с типами фиксированной ширины деление первым еще и уменьшает риск переполнения при умножении.

Остаток от отрицательных чисел: зависит от языка

Проверка n % d == 0 работает во всех популярных языках, а сравнение остатка с ненулевым значением — нет. В Python знак остатка совпадает со знаком делителя, в JavaScript, Java, C и C++ — со знаком делимого:

const isOddBad = n => n % 2 === 1;
const isOdd = n => n % 2 !== 0;
console.log(-7 % 3, -3 % 2);
console.log(isOddBad(-3), isOdd(-3));

-1 -1
false true

В Node.js 24 -3 % 2 дает -1, поэтому isOddBad(-3) ошибочно возвращает false. В Python то же выражение -7 % 3 дает 2, а -3 % 2 — 1. Исправление — проверять остаток на неравенство нулю (n % 2 !== 0), а не на равенство 1. То же касается индекса в кольцевом буфере при отрицательном сдвиге.

Выводы

• Делитель и кратное — одна связь с двух сторон: d делит n тогда и только тогда, когда n кратно d. У ненулевого числа конечное число делителей и бесконечно много кратных; 0 кратен любому числу, но делителем не бывает.
• Все делители n находятся перебором до √n парами (d, n / d); на точных квадратах не забывайте про двойной счет.
• Признаки делимости нужны для счета в уме и объясняются остатками 10 при делении на 3, 9 и 11; в коде достаточно n % d == 0.
• НОД сокращает дроби и режет на равные части, НОК дает общий знаменатель и период совпадения; НОД * НОК = a * b для натуральных чисел.
• Алгоритм Евклида находит НОД за логарифмическое число шагов; в Python берите math.gcd и math.lcm, а НОК вручную считайте через //, не через /.

Где применяется / связь с практикой

Делители, НОД и НОК встречаются в коде чаще, чем кажется: сокращение дробей в fractions.Fraction, расчет периодов у расписаний и анимаций, шаг обхода массива, который должен быть взаимно простым с его длиной, чтобы посетить все ячейки. В криптографии расширенный алгоритм Евклида находит обратный элемент по модулю — на этом строится вычисление ключа в RSA.

FAQ

Как найти НОД трех и более чисел?
Последовательно: НОД(a, b, c) = НОД(НОД(a, b), c). Так же считается НОК. В Python math.gcd(12, 18, 30) сразу вернет 6.

Чем делитель отличается от множителя?
Множитель — роль числа в произведении: в 12 = 3 * 4 оба числа множители. Любой натуральный множитель в таком разложении — делитель результата, но слово «делитель» описывает отношение между числами, а не конкретную запись.

Что такое расширенный алгоритм Евклида?
Он находит не только НОД(a, b), но и целые x и y, для которых a * x + b * y = НОД(a, b). Когда числа взаимно простые, x дает обратный к a элемент по модулю b; с Python 3.8 то же самое вычисляет pow(a, -1, b).