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

При́знак дели́мости — алгоритм, позволяющий сравнительно быстро определить, является ли число кратным заранее заданному^[1]. Если признак делимости позволяет выяснить не только делимость числа на заранее заданное, но и остаток от деления, то его называют признаком равноостаточности.

Как правило, признаки делимости применяются при ручном счёте и для чисел, представленных в конкретной позиционной системе счисления (обычно десятичной).

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

Если для двух целых чисел $a$ и $b$ существует такое целое число $q,$ что

b\,q=a,

то говорят, что число $a$ делится на $b.$

Два целых числа $a$ и $b$ называются равноделимыми на $m,$ если либо они оба делятся на $m,$ либо оба не делятся^[2].

Два целых числа $a$ и $b$ равноостаточны при делении на натуральное число $m$ (или сравнимы по модулю $m$ ), если при делении на $m$ они дают одинаковые остатки, то есть существует такие целые числа $q_{1},\,q_{2},\,r,$ что

a=m\,q_{1}+r,\;\;b=m\,q_{2}+r.

Общие принципы построения

Пусть требуется определить делится ли некоторое натуральное число $A$ на другое натуральное число $m.$ Для этого будем строить последовательность натуральных чисел:

A_{0},\,A_{1},\,A_{2},\,A_{3},\,\dots ,\,A_{n},

такую, что:

$A_{0}=A;\,$
каждый член последовательности вполне определяется предыдущим;
$A_{i}<A_{i-1},\quad i=1,\,2,\,3,\,\dots ,\,n-1;$
последний член последовательности меньше $m,$ то есть $0\leqslant A_{n}<m.\,$
все члены последовательности являются равноделимыми на $m.$

Тогда если последний член этой последовательности равен нулю, то $A$ делится на $m,$ в противном случае $A$ на $m$ не делится.

Способ (алгоритм) построения такой последовательности и будет искомым признаком делимости на $m.$ Математически он может быть описан с помощью функции $f(x),\,$ определяющей каждый следующий член последовательности в зависимости от предыдущего:

A_{i}=f\left(A_{i-1}\right),\quad i=1,\,2,\,3,\,\dots ,\,n-1,

удовлетворяющей следующим условиям:

при $x<m\,$ значение $f(x)\,$ не определено;
при $x\geqslant m$ значение $f(x)\,$ есть натуральное число;
если $x\geqslant m,$ то $f(x)<x;\,$
если $x\geqslant m,$ то $f(x)\,$ и $x$ равноделимы на $m.$

Если требование равноделимости для всех членов последовательности заменить на более строгое требование равноостаточности, то последний член этой последовательности будет являться остатком от деления $A$ на $m,$ а способ (алгоритм) построения такой последовательности будет признаком равноостаточности на $m.$ В силу того, что из равенства остатка при делении на $m$ нулю следует делимость на $m$ , любой признак равноостаточности может применяться как признак делимости. Математически признак равноостаточности тоже может быть описан с помощью функции $f(x),\,$ определяющей каждый следующий член последовательности в зависимости от предыдущего:

A_{i}=f\left(A_{i-1}\right),\quad i=1,\,2,\,3,\,\dots ,\,n-1,

удовлетворяющей следующим условиям:

при $x<m\,$ значение $f(x)\,$ не определено;
при $x\geqslant m$ значение $f(x)\,$ есть натуральное число;
если $x\geqslant m,$ то $f(x)<x;\,$
если $x\geqslant m,$ то $f(x)\,$ и $x$ равноостаточны при делении на $m.$

Примером такой функции, определяющей признак равноостаточности (и, соответственно, признак делимости), может быть функция

f(x)=x-m,\quad x\geqslant m,

а последовательность, построенная с её помощью будет иметь вид:

A,\,A-m,\,A-2m,\,A-3m,\,\dots

По сути применение признака равноостаточности на базе этой функции эквивалентно делению при помощи вычитания.

Другим примером может служить общеизвестный признак делимости (а также равноостаточности) на 10.

Если последняя цифра в десятичной записи числа равна нулю, то это число делится на 10; кроме того, последняя цифра будет являться отстатком от деления исходного числа на 10.

Математически этот признак равноостаточности может быть сформулирован следующим образом. Пусть надо выяснить остаток от деления на 10 натурального числа $A,$ представленного в виде

A=10\,b+a,\quad 0\leqslant a<10,\quad b\geqslant 0.

Тогда остатком от деления $A$ на 10 будет $a$ . Функция, описывающая это признак равноостаточности будет выглядеть как

f(A)=a,\quad A\geqslant 10.

Легко доказать, что эта функция удовлетворяет всем перечисленным выше требованиям. Причём последовательность, построенная с её помощью, будет содержать всего один или два члена.

Также легко видеть, что такой признак ориентирован именно на десятичное представление числа $A$ — так, например, если применять его на компьютере, использующем двоичную запись числа, то чтобы выяснить $a$ , программе пришлось бы сначала поделить $A$ на 10.

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

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

Число делится на 2 тогда и только тогда, когда его последняя цифра делится на 2, то есть является чётной.

Соответствующая признаку функция (см. раздел «Общие принципы построения»):

A=10\,a_{1}+a_{0},\quad 0\leqslant a_{0},<10,\quad a_{1}\geqslant 0,

F(A)={\begin{cases}a_{0},&A\geqslant 10\\A-2,&2\leqslant A<10.\end{cases}}

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

Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.

Соответствующая признаку функция:

A=\sum _{i=0}^{n}10^{i}a_{i},\quad 0\leqslant a_{i}<10,\quad i=0,1,\,\dots \,n,

F(A)={\begin{cases}{\sum _{i=0}^{n}a_{i}},&A\geqslant 10,\\A-3,&3\leqslant A<10.\end{cases}}

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

Число делится на 4 тогда и только тогда, когда две его последние цифры составляют число, которое делится на 4. Двузначное число делится на 4 тогда и только тогда, когда удвоенное число десятков, сложенное с числом единиц делится на 4. Например,число 42 не делится на 4, т.к. $2\cdot 4+2=10$ не делится на 4.

Соответствующая признаку функция:

A=100\,a_{2}+10\,a_{1}+a_{0},\quad 0\leqslant a_{0}<10,\quad 0\leqslant a_{1}<10,\quad a_{2}\geqslant 0,

F(A)={\begin{cases}2\,a_{1}+a_{0},&A\geqslant 20,\\A-4,&4\leqslant A<20.\end{cases}}

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

Число делится на 5 тогда, когда последняя цифра делится на 5, т.е. если она 0 или 5.

Соответствующая признаку функция:

A=10\,a_{1}+a_{0},\quad 0\leqslant a_{0}<10,\quad a_{1}\geqslant 0,

F(A)={\begin{cases}a_{0},&A\geqslant 10,\\A-5,&5\leqslant A<10.\end{cases}}

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

Число делится на 6 тогда и только тогда, когда оно делится и на 2, и на 3 (то есть если оно четное и сумма его цифр делится на 3).

Другой признак делимости: число делится на 6 тогда и только тогда, когда учетверённое число десятков, сложенное с числом единиц делится на 6.

Соответствующая признаку функция:

A=10\,a_{1}+a_{0},\quad 0\leqslant a_{0}<10,\quad a_{1}\geqslant 0,

F(A)={\begin{cases}4\,a_{1}+a_{0},&A\geqslant 10,\\A-6,&6\leqslant A<10.\end{cases}}

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

Число делится на 7 тогда и только тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7 (например, 364 делится на 7, так как 36 − (2 ∙ 4) = 28 делится на 7).

Либо использовать модификацию признака деления на 1001=10³+1, которое само делится на 7:
Для того, чтобы натуральное число делилось на 7 необходимо и достаточно, чтобы алгебраическая сумма чисел, образующих нечётные группы по три цифры (начиная с единиц) взятых со знаком «+» и чётных со знаком «-» делилась на семь (например, число 689255. Первая группа со знаком «+» (255), вторая со знаком «-» (689). Отсюда 255 + (-689) = −434. В свою очередь 434 : 7 = 62).

Ещё один признак — берём первую цифру, умножаем на 3, прибавляем следующую (здесь можно взять остаток от деления на 7 от получившегося числа). И далее — сначала: умножаем на 3, прибавляем следующую… Для 364: 3 * 3 + 6 = 15. Остаток — 1. Далее 1 * 3 + 4 = 7.

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

Число делится на 8 тогда и только тогда, когда число, образованное тремя его последними цифрами, делится на 8.

Чтобы узнать, делится ли трёхзначное число на 8, можно половину единиц прибавить к десяткам. У получившегося числа также половину единиц прибавить к десяткам. Если итоговая сумма делится на 2, значит, число делится на 8. Например, 952: 95 + 2 = 97, далее 9 + 7 = 16, 16 : 2 = 8. Значит, 952 делится на 8.

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

Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9.

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

Число делится на 10 тогда и только тогда, когда оно оканчивается на нoль.

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

Разность цифр на чётных и нечётных позициях

На 11 делятся только те числа, у которых разность между суммой цифр, занимающих нечётные места,и суммой цифр, занимающих чётные места, делится на 11.

Примеры. Число 103785 делится на 11, так как сумма цифр, занимающих нечётные места, 1+3+8=12 равна сумме цифр, занимающих чётные места 0+7+5=12. Число 9 163 627 делится на 11, так как сумма цифр, занимающих нечётные места, есть 9 + 6 + 6 + 7 = 28, а сумма цифр, занимающих чётные места, есть 1 + 3 +2 =6; разность между числами 28 и 6 есть 22, а это число делится на 11. Число 461025 не делится на 11, так как 4+ 1 + 2 = 7 и 6 +0 + 5=11 а их разность 11 —7 = 4 на 11 не делится.

Признак обобщается на группы цифр нечётной длины. При необходимости, к числу можно приписать нули

Примеры. Число 103785 делится на 11, так как разбивается на блоки 103 и 785, и сумма чисел в нечётных блоках (103) отличается от суммы чисел в чётных блоках (785) на число 682, делящееся на 11. Число 9 163 627 делится на 11, так как 009+627=636 отличается от 163 на число 636-163=473, делящееся на 11. Число 461025 не делится на 11, так как 461-025=436 не делится на 11.

Разность единиц и десятков

Ещё один признак: отнимайте единицы от десятков. Если результат делится на 11, то и само число тоже.

Пример. 103785 10378-5=10373 1037-3=1034 103-4=99 9-9=0

Признак обобщается на нечётные степени 10.

Пример. 103785 делится на 11, так как число тысяч (103) минус число единиц равно 103-785=-682 делится на 11.

Сумма блоков по две цифры

Число разделяется на группы по две рядом стоящие цифры (если необходимо, добавляется нуль в конец или начало числа). Если сумма полученных чисел делится на 11, то и само число делится на 11.

Примеры. Число 103785 делится на 11, так как 10+37+85=132 делится на 11. Число 9 163 627 делится на 11, так как 09+16+36+27=88 делится на 11 (или потому что 91+63+62+70=286 делится на 11). Число 461025 не делится на 11, так как 46+10+25=81 не делится на 11.

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

Число делится на 13 тогда и только тогда, когда сумма числа, полученного отбрасыванием последней цифры и учётверённой последней цифры, делится на 13. Например 845 : 13 , так как 84+(4*5)=104:13 10+(4*4)= 26:13.

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

Число делится на 17 тогда и только тогда, когда число его десятков, сложенное с увеличенным в 12 раз числом единиц, кратно 17 (например, 29053→2905+36=2941→294+12=306→30+72=102→10+24=34. Поскольку 34 делится на 17, то и 29053 делится на 17). Признак не всегда удобен, но имеет определенное значение в математике. Есть способ немного проще — число делится на 17 тогда и только тогда, когда разность между числом его десятков и упятерённым числом единиц кратна 17 (например, 32952→3295-10=3285→328-25=303→30-15=15; поскольку 15 не делится на 17, то и 32952 не делится на 17).

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

Число делится на 19 тогда и только тогда, когда число его десятков, сложенное с удвоенным числом единиц, кратно 19 (например, 646 делится на 19, так как 64 + (6 × 2) = 76 делится на 19).

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

Число делится на 20 тогда и только тогда, когда оно оканчивается на 0 и его предпоследняя цифра чётная.

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

Число делится на 23 тогда и только тогда, когда число его сотен, сложенное с утроенным числом десятков и единиц, кратно 23 (например, 28842 делится на 23, так как 288 + (3 * 42) = 414; продолжаем: 4 + (3 * 14) = 46 — очевидно, делится на 23).

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

Число делится на 25 тогда и только тогда, когда число, образованное его последними двумя цифрами делится на 25 (то есть последние две цифры образуют 00, 25, 50 или 75).

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

Разобьём число на группы по 2 цифры справа налево (в самой левой группе может быть одна цифра) и найдём сумму этих групп, считая их двузначными числами. Эта сумма делится на 99 тогда и только тогда, когда само число делится на 99.

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

Разобьём число на группы по 2 цифры справа налево (в самой левой группе может быть одна цифра) и найдём алгебраическую сумму этих групп с переменными знаками, считая их двузначными числами. Эта сумма делится на 101 тогда и только тогда, когда само число делится на 101. Например, 590547 делится на 101, так как 59-05+47=101 делится на 101.

Признак делимости на $2^{n}$

Число делится на n-ю степень двойки тогда и только тогда, когда число, образованное его последними n цифрами, делится на ту же степень. (n>0)

Признак делимости на $5^{n}$

Число делится на n-ю степень пятёрки тогда и только тогда, когда число, образованное его последними n цифрами, делится на ту же степень. (n>0)

Признак делимости на $10^{n}-1$

Разобьем число на группы по n цифр справа налево (в самой левой группе может быть от 1 до n цифр) и найдем сумму этих групп, считая их n-значными числами. Эта сумма делится на $10^{n}-1$ тогда и только тогда, когда само число делится на $10^{n}-1$ .

Признак делимости на $10^{n}$

Число делится на n-ю степень десятки тогда и только тогда, когда n его последних цифр — нули.

Признак делимости на $10^{n}+1$

Разобьем число на группы по n цифр справа налево (в самой левой группе может быть от 1 до n цифр) и найдем сумму этих групп с переменными знаками, считая их n-значными числами. Эта сумма делится на $10^{n}+1$ тогда и только тогда, когда само число делится на $10^{n}+1$ .

Признаки делимости в других системах счисления

Признаки делимости в других системах счисления аналогичны таковым в десятичной. В частности, в любой системе счисления (числа записаны в той системе, в которой мы работаем в данный момент):

число делится на 10ⁿ, если оно оканчивается на n нулей.

Если основание системы счисления равно k, то любое число делится на k-1 тогда и только тогда, когда сумма его цифр делится на k-1 без остатка. В частности:

число делится на 10−1, если сумма его цифр делится на 10−1;
если основание системы счисления нечётное, то число делится на 2, если сумма его цифр делится на 2.

Если основание системы счисления равно k, то любое число делится на k+1 тогда и только тогда, когда сумма цифр, занимающих нечётные места,отличается от суммы цифр на чётных местах на число, делящееся на k+1. В частности:

число делится на 11, если сумма цифр, занимающих нечётные места, либо равна сумме цифр, занимающих чётные места, либо отличается от неё на число, делящееся на 11.

Если основание системы счисления делится на некоторое число k, то любое число делится на k тогда и только тогда, когда его последняя цифра делится на k. В частности:

если основание системы счисления чётное, то число делится на 2, если его последняя цифра делится на 2.

См. также

Признак Паскаля — универсальный признак делимости, позволяющий для любых целых a и b определить, делится ли a на b. Точнее, он позволяет вывести почти все из выше приведённых признаков.

Литература

Воробьев Н. Н. Признаки делимости. — 4-е изд. — М.: Наука, 1988. — Т. 39. — 94 с. — (Популярные лекции по математике). — ISBN 5-02-013731-6.

Примечания

↑ С практической точки зрения «сравнительно быстро» означает «быстрее, чем можно было бы выполнить фактическое деление» теми же самыми средствами. Причём эффективность этого алгоритма в немалой степени зависит от формы представления чисел и имеющихся в распоряжении вычислительных возможностей.
↑ Воробьев Н. Н. Признаки делимости. — 4-е изд., испр.. — М.: Наука, 1988. — С. 42. — (Популярные лекции по математике). — ISBN 5-02-013731-6.

[1] С практической точки зрения «сравнительно быстро» означает «быстрее, чем можно было бы выполнить фактическое деление» теми же самыми средствами. Причём эффективность этого алгоритма в немалой степени зависит от формы представления чисел и имеющихся в распоряжении вычислительных возможностей.

[2] Воробьев Н. Н. Признаки делимости. — 4-е изд., испр.. — М.: Наука, 1988. — С. 42. — (Популярные лекции по математике). — ISBN 5-02-013731-6.

[1]

[2]

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

Содержание

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

Общие принципы построения