При́знак дели́мости — алгоритм, позволяющий сравнительно быстро определить, является ли число кратным заранее заданномуС практической точки зрения «сравнительно быстро» означает «быстрее, чем можно было бы выполнить фактическое деление» теми же самыми средствами. Причём эффективность этого алгоритма в немалой степени зависит от формы представления чисел и имеющихся в распоряжении вычислительных возможностей.. Если признак делимости позволяет выяснить не только делимость числа на заранее заданное, но и остаток от деления, то его называют признаком равноостаточности.
Как правило, признаки делимости применяются при ручном счёте и для чисел, представленных в конкретной позиционной системе счисления (обычно десятичной).
Понятия делимости, равноделимости и равноостаточности
Если для двух целых чисел и существует такое целое число что
то говорят, что число делится на
Два целых числа и называются равноделимыми на если либо они оба делятся на либо оба не делятся.
Два целых числа и равноостаточны при делении на натуральное число (или сравнимы по модулю ), если при делении на они дают одинаковые остатки, то есть существует такие целые числа что
Общие принципы построения
Пусть требуется определить, делится ли некоторое натуральное число на другое натуральное число Для этого возьмём последовательность натуральных чисел:
такую, что:
каждый член последовательности определяется предыдущим;
последний член последовательности меньше то есть все члены последовательности имеют одинаковые остатки при делении на
Тогда, если последний член этой последовательности равен нулю, то делится на в противном случае на не делится.
Способ (алгоритм) построения такой последовательности и будет искомым признаком делимости на Математически он может быть описан с помощью функции определяющей каждый следующий член последовательности в зависимости от предыдущего:
удовлетворяющей следующим условиям: при значение не определено; при значение есть натуральное число; если то если то и равноделимы на
Если требование равноделимости для всех членов последовательности заменить на более строгое требование равноостаточности, то последний член этой последовательности будет являться остатком от деления на а способ (алгоритм) построения такой последовательности будет признаком равноостаточности на В силу того, что из равенства остатка при делении на нулю следует делимость на , любой признак равноостаточности может применяться как признак делимости. Математически признак равноостаточности тоже может быть описан с помощью функции определяющей каждый следующий член последовательности в зависимости от предыдущего:
удовлетворяющей следующим условиям: при значение не определено; при значение есть натуральное число; если то если то и равноостаточны при делении на
Примером такой функции, определяющей признак равноостаточности (и, соответственно, признак делимости), может быть функция
а последовательность, построенная с её помощью будет иметь вид:
По сути применение признака равноостаточности на базе этой функции эквивалентно делению при помощи вычитания.
Другим примером может служить общеизвестный признак делимости (а также равноостаточности) на 10. Если последняя цифра в десятичной записи числа равна нулю, то это число делится на 10; кроме того, последняя цифра будет являться остатком от деления исходного числа на 10.
Математически этот признак равноостаточности может быть сформулирован следующим образом. Пусть надо выяснить остаток от деления на 10 натурального числа представленного в виде
Тогда остатком от деления на 10 будет . Функция, описывающая этот признак равноостаточности будет выглядеть как
Легко доказать, что эта функция удовлетворяет всем перечисленным выше требованиям. Причём последовательность, построенная с её помощью, будет содержать всего один или два члена.
Также легко видеть, что такой признак ориентирован именно на десятичное представление числа — так, например, если применять его на компьютере, использующем двоичную запись числа, то чтобы выяснить , программе пришлось бы сначала поделить на 10.
Для построения признаков равноостаточности и делимости чаще всего используется следующие теоремы: При любых целом и натуральном целые числа и равноостаточны при делении на При любых целом , натуральном , целые числа и равноделимы на если целое является взаимно простым с
Признаки делимости в десятичной системе счисления
Признак делимости на 2 Число делится на тогда и только тогда, когда его последняя цифра делится на 2, то есть является чётной.
Соответствующая признаку функция (см. раздел «Общие принципы построения»):
Эта функция помимо признака делимости задаёт и признак равноостаточности.
Признак делимости на 3 Число делится на , когда сумма его цифр делится на 3. Например, число 159 делится на 3, поскольку сумма его цифр 1 + 5 + 9 = 15 делится на 3.
Соответствующая признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 154, и равноостаточны при делении на 3.
Признак делимости на 4 Число делится на , когда две последние цифры нули или составляют число, делящееся на 4. Например, 14676 — последние цифры 76, и число 76 делится на 4: 76:4=19. Двузначное число делится на 4 тогда и только тогда, когда удвоенная цифра в разряде десятков, сложенная с цифрой в разряде единиц, делится на 4. Например, число 42 не делится на 4, так как не делится на 4.
Соответствующая признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, и равноостаточны при делении на 4.
Более простая формулировка: Число делится на 4, если в последнем разряде 0, 4, 8, а предпоследний разряд чётный; или если в последнем разряде 2, 6, а предпоследний разряд нечётный.
Признак делимости на 5 Число делится на тогда и только тогда, когда оно оканчивается на 0 или на 5.
Соответствующая признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности.
Признак делимости на 6 Число делится на тогда и только тогда, когда оно делится и на 2, и на 3 (то есть если оно чётное и сумма его цифр делится на 3).
Другой признак делимости: число делится на 6 тогда и только тогда, когда учетверённое число десятков, сложенное с цифрой в разряде единиц, делится на 6.
Соответствующая признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 73, и равноостаточны при делении на 6.
Признак делимости на 7 Признак 1:
число делится на тогда, когда утроенное число десятков, сложенное с цифрой в разряде единиц, делится на 7. Например, 154 делится на 7, так как на 7 делится 1001 делится на 7, так как на 7 делятся
Соответствующая этому признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, и равноостаточны при делении на 7.
Модификации признака 1:
a) берётся первая цифра слева, умножается на 3, прибавляется следующая, и всё повторяется сначала: например, для 154: . Также на каждом шаге можно брать остаток от деления на 7: остаток 1, остаток 0. В обоих случаях итоговое число равноостаточно при делении на 7 с исходным числом.
b) если удвоенное число единиц числа отнять от оставшегося числа десятков и результат будет делиться на 7, то число кратно 7. Например: 784 делится на 7, так как ( ).
Признак 2:
число делится на 7 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по три цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «−» делится на 7. Например, делится на 7, так как на 7 делится
Соответствующая этому признаку функция:
Признак 3:
если разность между числом, состоящим из трёх последних цифр данного числа, и числом, образованным из оставшихся цифр данного числа (то есть без последних трёх цифр), делится на 7, то данное число делится на 7. Пример для числа 1730736: 1730 − 736 = 994, 994 / 7 = 142.
Признак 4:
число делится на 7 тогда и только тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7. Например, 623 делится на 7, так как на 7 делится . 1001 делится на 7, так как на 7 делится .
Признак делимости на 8 Число делится на , когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой в разряде десятков и учетверённой цифрой в разряде сотен, делится на 8. Например, 952 делится на 8 так как на 8 делится
Соответствующая признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 567, и равноостаточны при делении на 8.
Более простая формулировка: Число делится на 8, если две последние цифры составляют число, делящееся на 8, а разряд перед предпоследним чётный; или если две последние цифры составляют число, которое не делится на 8 (но делится на 4), а разряд перед предпоследним нечётный.
Признак делимости на 9 Число делится на , когда сумма его цифр делится на 9. Например, сумма цифр числа 12345678 делится на 9, следовательно и само число делится на 9.
Соответствующая признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 345, и равноостаточны при делении на 9.
Признак делимости на 10 Число делится на тогда и только тогда, когда оно оканчивается на ноль.
Соответствующая этому признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности.
Признаки делимости на 11 Признак 1: число делится на тогда и только тогда, когда сумма цифр, занимающих нечётные позиции, равна сумме цифр, занимающих чётные места, или отличается от нее на число, кратное 11. Например, делится на 11, так как .
Соответствующая этому признаку функция:
Признак 2: число делится на 11 тогда и только тогда, когда на 11 делится сумма чисел, образующих группы по две цифры (начиная с единиц). Например, 103785 делится на 11, так как на 11 делятся и
Соответствующая признаку функция:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 123456, и равноостаточны при делении на 11.
Признак делимости на 13 Признак 1: Число делится на , когда сумма числа десятков с учетверённой цифрой в разряде единиц делится на 13. Например 845 делится на 13, так как на 13 делятся и
Признак 2: Число делится на , когда разность числа десятков с девятикратным числом, стоящего в разряде единиц, делится на 13. Например 845 делится на 13, так как на 13 делятся
Соответствующая этому признаку функция:
Признак 3: Число делится на , если разность между числом, состоящим из трёх последних цифр данного числа, и числом, образованным из оставшихся цифр данного числа (то есть без последних трёх цифр), делится на 13. Например 192218 делится на 13, так как 218-192=26, а 26 делится на 13.
Признак 4: Число делится на тогда, когда утроенное число десятков без цифры в разряде единиц, делится на . Например, делится на , так как и , а также , а делится на .
Признак делимости на 17 Число делится на в следующих случаях:
— когда модуль разности числа десятков и умноженной на 5 цифрой в разряде единиц делится на 17. Например, 221 делится на 17, так как делится на 17.
— когда модуль суммы числа десятков и умноженной на 12 цифрой в разряде единиц делится на 17. Например, 221 делится на 17, так как делится на 17.
Соответствующая этому признаку функция:
Признак делимости на 19 Число делится на тогда и только тогда, когда число десятков, сложенное с удвоенной цифрой в разряде единиц, делится на 19. Например, 646 делится на 19, так как на 19 делятся и
Соответствующая этому признаку функция:
Признак делимости на 20 Число делится на тогда и только тогда, когда число, образованное двумя последними цифрами, делится на 20.
Другая формулировка: число делится на 20 тогда и только тогда, когда последняя цифра числа — 0, а предпоследняя — чётная.
Соответствующая этому признаку функция: