Признаки делимости для простых чисел: линейный алгоритм a ± kb

Линейный алгоритм проверки делимости — это универсальный метод, позволяющий проверить делимость на любое простое число с помощью одной формулы a ± kb. Для каждого простого числа существует свой коэффициент k, но принцип одинаков: отделяем последнюю цифру, умножаем её на k и складываем (или вычитаем) с оставшейся частью числа. Операцию повторяем до получения очевидного результата. Метод особенно полезен в олимпиадной математике и при работе с числами, не покрытыми другими признаками.

Принцип метода

Любое натуральное число можно представить в виде 10a + b, где:

b — последняя цифра числа (единицы),
a — число, образованное остальными цифрами (десятки и выше).

Например, для числа 371: a = 37, b = 1.

Для каждого простого числа p существует коэффициент k такой, что:

Число 10a + b делится на простое число p тогда и только тогда, когда a ± k·b делится на p. Результат можно проверять рекурсивно — снова отделять последнюю цифру и применять формулу.

💡 Рекурсивность

Формула применяется повторно к результату, пока число не станет достаточно маленьким для проверки «в лоб». Обычно достаточно 2–4 итераций даже для шестизначных чисел.

Пошаговый разбор: делимость на 7

Признак делимости на 7: a − 2b. Коэффициент k = 2, знак — минус.

Проверим, делится ли число 2 744 на 7:

Итерация 1. Число 2744: a = 274, b = 4. Считаем: 274 − 2×4 = 274 − 8 = 266.
Итерация 2. Число 266: a = 26, b = 6. Считаем: 26 − 2×6 = 26 − 12 = 14.
Итерация 3. Число 14: a = 1, b = 4. Считаем: 1 − 2×4 = 1 − 8 = −7.

Число −7 делится на 7 → 2 744 делится на 7. Проверка: 2 744 ÷ 7 = 392.

А теперь число 503:

Итерация 1. 503: a = 50, b = 3. Считаем: 50 − 2×3 = 50 − 6 = 44.
Итерация 2. 44: a = 4, b = 4. Считаем: 4 − 2×4 = 4 − 8 = −4.

Число −4 не делится на 7 → 503 не делится на 7.

Признаки для отдельных простых чисел

Признак делимости на 7: a − 2b

Отделите последнюю цифру, умножьте её на 2 и вычтите из оставшейся части. Повторяйте до очевидного результата.

Пример. 868 → 86 − 2×8 = 86 − 16 = 70 → 70 делится на 7 ✓ (868 ÷ 7 = 124).

Признак делимости на 13: a + 4b

Отделите последнюю цифру, умножьте на 4 и прибавьте к оставшейся части.

Пример. 2 366 → 236 + 4×6 = 236 + 24 = 260 → 26 + 4×0 = 26 → 26 = 2×13 ✓ (2 366 ÷ 13 = 182).

Признак делимости на 17: a − 5b

Отделите последнюю цифру, умножьте на 5 и вычтите из оставшейся части.

Пример. 782 → 78 − 5×2 = 78 − 10 = 68 → 6 − 5×8 = 6 − 40 = −34 → −34 = −2×17 ✓ (782 ÷ 17 = 46).

Признак делимости на 19: a + 2b

Отделите последнюю цифру, умножьте на 2 и прибавьте к оставшейся части.

Пример. 1 349 → 134 + 2×9 = 134 + 18 = 152 → 15 + 2×2 = 19 → 19 делится на 19 ✓ (1 349 ÷ 19 = 71).

Признак делимости на 23: a + 7b

Отделите последнюю цифру, умножьте на 7 и прибавьте к оставшейся части.

Пример. 1 817 → 181 + 7×7 = 181 + 49 = 230 → 23 + 7×0 = 23 → делится ✓ (1 817 ÷ 23 = 79).

Таблица коэффициентов для простых чисел от 7 до 151

В таблице указаны коэффициент k и знак операции для каждого простого числа. Формула: a ± k·b.

Простое p	Формула	Простое p	Формула
7	a − 2b	71	a − 7b
13	a + 4b	79	a + 8b
17	a − 5b	83	a + 25b
19	a + 2b	89	a + 9b
23	a + 7b	97	a − 29b
29	a + 3b	103	a + 31b
31	a − 3b	107	a − 32b
41	a − 4b	109	a + 11b
43	a + 13b	113	a + 34b
47	a − 14b	127	a − 38b
53	a + 16b	131	a − 13b
59	a + 6b	139	a + 14b
61	a − 6b	149	a + 15b
67	a − 20b	151	a − 15b

💡 Замечание о знаке

Если результат получился отрицательным — это нормально. Важна только делимость на p, а не знак. Числа 0, p, −p, 2p, −2p и т. д. — все означают делимость.

Как найти коэффициент самостоятельно

Для продвинутых читателей: коэффициент k можно вычислить для любого простого числа p (не равного 2 и 5).

Найдите число m, которое при умножении на 10 даёт остаток 1 при делении на p. То есть 10m ≡ 1 (mod p). Такое m называется обратным элементом к 10 по модулю p.
Тогда k = m (знак «+»). Или, альтернативно, k = p − m (знак «−»). Выбирают тот вариант, где k меньше.

Пример для 7. Ищем m: 10×5 = 50 = 7×7 + 1, значит 10×5 ≡ 1 (mod 7), m = 5. Альтернатива: k = 7 − 5 = 2 (знак «−»). Поскольку 2 < 5, используем формулу a − 2b.

📐 Почему это работает

Число 10a + b ≡ 0 (mod p) эквивалентно a + m·b ≡ 0 (mod p), ведь мы умножили обе части на обратный к 10 элемент m. Это и есть наша формула a + kb.

Другие методы проверки делимости

🧩

Признаки по блокам цифр

Альтернативный способ для 7, 11, 13 и 37 — через блоки по 3 цифры. Быстрее для очень больших чисел.

Изучить метод

🔗

Делимость на составное число

Как комбинировать признаки для простых чисел, чтобы проверять делимость на 6, 12, 15 и другие составные.