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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
м откат правок 109.252.63.9 (обс.) к версии LGB
Метка: откат
 
(не показано 249 промежуточных версий, сделанных более чем 100 участниками)
Строка 1: Строка 1:
'''При́знак [[Делимость|дели́мости]]''' — [[алгоритм]], позволяющий сравнительно быстро определить, является ли число кратным заранее заданному<ref>С практической точки зрения ''«сравнительно быстро»'' означает ''«быстрее, чем можно было бы выполнить фактическое деление»'' теми же самыми средствами. Причём эффективность этого алгоритма в немалой степени зависит от формы представления чисел и имеющихся в распоряжении вычислительных возможностей.</ref>. Если признак делимости позволяет выяснить не только [[делимость]] числа на заранее заданное, но и остаток от деления, то его называют '''признаком равноостаточности'''.
'''При́знак дели́мости''' — [[алгоритм]], позволяющий сравнительно быстро определить, является ли число кратным заранее заданному<ref>С практической точки зрения ''«сравнительно быстро»'' означает ''«быстрее, чем можно было бы выполнить фактическое деление»'' теми же самыми средствами. Причём эффективность этого алгоритма в немалой степени зависит от формы представления чисел и имеющихся в распоряжении вычислительных возможностей.</ref>. Если признак делимости позволяет выяснить не только [[делимость]] числа на заранее заданное, но и остаток от деления, то его называют '''признаком [[Сравнение по модулю|равноостаточности]]'''.


Как правило, признаки делимости применяются при ручном счёте и для чисел, представленных в конкретной [[Позиционная система счисления|позиционной системе счисления]] (обычно [[Десятичная система счисления|десятичной]]).
Как правило, признаки делимости применяются при ручном счёте и для чисел, представленных в конкретной [[Позиционная система счисления|позиционной системе счисления]] (обычно [[Десятичная система счисления|десятичной]]).
Строка 10: Строка 10:
то говорят, что число <math>a</math> ''делится'' на <math>b.</math>
то говорят, что число <math>a</math> ''делится'' на <math>b.</math>


Два целых числа <math>a</math> и <math>b</math> называются ''равноделимыми'' на <math>m,</math> если либо они оба делятся на <math>m,</math> либо оба не делятся<ref>{{книга|автор=Воробьев&nbsp;Н.&nbsp;Н.|заглавие=Признаки делимости|серия=[[Популярные лекции по математике]]|издание=4-е изд., испр|место=М.|издательство=Наука|год=1988|isbn=5-02-013731-6|страницы=42}}</ref>.
Два целых числа <math>a</math> и <math>b</math> называются ''равноделимыми'' на <math>m,</math> если либо они оба делятся на <math>m,</math> либо оба не делятся<ref>{{книга|автор=Воробьёв&nbsp;Н.&nbsp;Н.|заглавие=Признаки делимости|серия=[[Популярные лекции по математике]]|издание=4-е изд., испр|место=М.|издательство=Наука|год=1988|isbn=5-02-013731-6|страницы=42}}</ref>.


Два целых числа <math>a</math> и <math>b</math> ''равноостаточны'' при делении на [[натуральное число]] <math>m</math> (или [[Сравнение по модулю|''сравнимы по модулю'']] <math>m</math>), если при делении на <math>m</math> они дают одинаковые остатки, то есть существует такие целые числа <math>q_1,\,q_2,\,r,</math> что
Два целых числа <math>a</math> и <math>b</math> ''равноостаточны'' при делении на [[натуральное число]] <math>m</math> (или ''[[Сравнение по модулю|сравнимы по модулю]]'' <math>m</math>), если при делении на <math>m</math> они дают одинаковые остатки, то есть существует такие целые числа <math>q_1,\,q_2,\,r,</math> что
: <math>a = m\,q_1 + r,\;\;b = m\,q_2 + r.</math>
: <math>a = m\,q_1 + r,\;\;b = m\,q_2 + r.</math>


== Общие принципы построения ==
== Общие принципы построения ==
{{проще|раздел|обс=Проще|дата=2016-09-26}}
Пусть требуется определить, [[Делимость|делится]] ли некоторое [[натуральное число]] <math>A</math> на другое натуральное число <math>m.</math> Для этого будем строить последовательность натуральных чисел:
Пусть требуется определить, [[Делимость|делится]] ли некоторое [[натуральное число]] <math>A</math> на другое натуральное число <math>m.</math> Для этого возьмём последовательность натуральных чисел:
: <math>A_0,\,A_1,\,A_2,\,A_3,\,\dots,\,A_n,</math>
: <math>A_0,\,A_1,\,A_2,\,A_3,\,\dots,\,A_n,</math>
такую, что:
такую, что:
# <math>A_0 = A;\,</math>
# <math>A_0 = A;</math>
# каждый член последовательности вполне определяется предыдущим;
# каждый член последовательности определяется предыдущим;
# <math>A_i < A_{i-1},\quad i=1,\,2,\,3,\,\dots,\,n-1;</math>
# <math>A_i < A_{i-1},\quad i=1,\,2,\,3,\,\dots,\,n-1;</math>
# последний член последовательности меньше <math>m,</math> то есть <math>0 \leqslant A_n < m.\,</math>
# последний член последовательности меньше <math>m,</math> то есть <math>0 \leqslant A_n < m.</math>
# все члены последовательности являются равноделимыми на <math>m.</math>
# все члены последовательности имеют одинаковые остатки при делении на <math>m.</math>


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


Способ (алгоритм) построения такой последовательности и будет искомым ''признаком делимости'' на <math>m.</math> Математически он может быть описан с помощью функции <math>f(x),\,</math> определяющей каждый следующий член последовательности в зависимости от предыдущего:
Способ (алгоритм) построения такой последовательности и будет искомым ''признаком делимости'' на <math>m.</math> Математически он может быть описан с помощью функции <math>f(x),</math> определяющей каждый следующий член последовательности в зависимости от предыдущего:
: <math>A_i = f\left(A_{i-1}\right),\quad i=1,\,2,\,3,\,\dots,\,n,</math>
: <math>A_i = f\left(A_{i-1}\right),\quad i=1,\,2,\,3,\,\dots,\,n,</math>
удовлетворяющей следующим условиям:
удовлетворяющей следующим условиям:
# при <math>x < m\,</math> значение <math>f(x)\,</math> не определено;
# при <math>x < m</math> значение <math>f(x)</math> не определено;
# при <math>x \geqslant m</math> значение <math>f(x)\,</math> есть натуральное число;
# при <math>x \geqslant m</math> значение <math>f(x)</math> есть натуральное число;
# если <math>x \geqslant m,</math> то <math>f(x) < x;\,</math>
# если <math>x \geqslant m,</math> то <math>f(x) < x;</math>
# если <math>x \geqslant m,</math> то <math>f(x)\,</math> и <math>x</math> равноделимы на <math>m.</math>
# если <math>x \geqslant m,</math> то <math>f(x)</math> и <math>x</math> равноделимы на <math>m.</math>


Если требование равноделимости для всех членов последовательности заменить на более строгое требование равноостаточности, то последний член этой последовательности будет являться остатком от деления <math>A</math> на <math>m,</math> а способ (алгоритм) построения такой последовательности будет ''признаком равноостаточности'' на <math>m.</math> В силу того, что из равенства остатка при делении на <math>m</math> нулю следует делимость на <math>m</math>, любой признак равноостаточности может применяться как признак делимости. Математически признак равноостаточности тоже может быть описан с помощью функции <math>f(x),\,</math> определяющей каждый следующий член последовательности в зависимости от предыдущего:
Если требование равноделимости для всех членов последовательности заменить на более строгое требование равноостаточности, то последний член этой последовательности будет являться остатком от деления <math>A</math> на <math>m,</math> а способ (алгоритм) построения такой последовательности будет ''признаком равноостаточности'' на <math>m.</math> В силу того, что из равенства остатка при делении на <math>m</math> нулю следует делимость на <math>m</math>, любой признак равноостаточности может применяться как признак делимости. Математически признак равноостаточности тоже может быть описан с помощью функции <math>f(x),</math> определяющей каждый следующий член последовательности в зависимости от предыдущего:
: <math>A_i = f\left(A_{i-1}\right),\quad i=1,\,2,\,3,\,\dots,\,n,</math>
: <math>A_i = f\left(A_{i-1}\right),\quad i=1,\,2,\,3,\,\dots,\,n,</math>
удовлетворяющей следующим условиям:
удовлетворяющей следующим условиям:
# при <math>x < m\,</math> значение <math>f(x)\,</math> не определено;
# при <math>x < m</math> значение <math>f(x)</math> не определено;
# при <math>x \geqslant m</math> значение <math>f(x)\,</math> есть натуральное число;
# при <math>x \geqslant m</math> значение <math>f(x)</math> есть натуральное число;
# если <math>x \geqslant m,</math> то <math>f(x) < x;\,</math>
# если <math>x \geqslant m,</math> то <math>f(x) < x;</math>
# если <math>x \geqslant m,</math> то <math>f(x)\,</math> и <math>x</math> равноостаточны при делении на <math>m.</math>
# если <math>x \geqslant m,</math> то <math>f(x)</math> и <math>x</math> равноостаточны при делении на <math>m.</math>


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


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


Математически этот признак равноостаточности может быть сформулирован следующим образом. Пусть надо выяснить остаток от деления на 10 натурального числа <math>A,</math> представленного в виде
Математически этот признак равноостаточности может быть сформулирован следующим образом. Пусть надо выяснить остаток от деления на 10 натурального числа <math>A,</math> представленного в виде
: <math>A = 10\,b + a,\quad 0 \leqslant a < 10,\quad b \geqslant 0.</math>
: <math>A = 10\,b + a,\quad 0 \leqslant a < 10,\quad b \geqslant 0.</math>
Тогда остатком от деления <math>A</math> на 10 будет <math>a</math>. Функция, описывающая это признак равноостаточности будет выглядеть как
Тогда остатком от деления <math>A</math> на 10 будет <math>a</math>. Функция, описывающая этот признак равноостаточности будет выглядеть как
: <math>f(A) = a,\quad A \geqslant 10.</math>
: <math>f(A) = a,\quad A \geqslant 10.</math>
Легко доказать, что эта функция удовлетворяет всем перечисленным выше требованиям. Причём последовательность, построенная с её помощью, будет содержать всего один или два члена.
Легко доказать, что эта функция удовлетворяет всем перечисленным выше требованиям. Причём последовательность, построенная с её помощью, будет содержать всего один или два члена.


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


Для построения признаков равноостаточности и делимости чаще всего используется следующие теоремы:
Для построения признаков равноостаточности и делимости чаще всего используется следующие теоремы:
Строка 79: Строка 80:
:<math>f(A) = \begin{cases} 3\,a_1 + a_0, & A \geqslant 10, \\ A - 7, & 7 \leqslant A < 10. \end{cases}</math>
:<math>f(A) = \begin{cases} 3\,a_1 + a_0, & A \geqslant 10, \\ A - 7, & 7 \leqslant A < 10. \end{cases}</math>


А из второй теоремы полагая <math>q = 3\,a_1</math> и <math>p = -2,</math> взаимно простое с 7, будет следовать, что <math>A</math> будет равноделимы на 7 с числом
А из второй теоремы, полагая <math>q = 3\,a_1</math> и <math>p = -2,</math> взаимно простое с 7, будет следовать, что <math>A</math> будет равноделимы на 7 с числом
: <math>A' = 7 \cdot 3 a_1 - 2 A = \left(21 - 20 \right)a_1 - 2\,a_0 = a_1 - 2\,a_0.</math>
: <math>A' = 7 \cdot 3 a_1 - 2 A = \left(21 - 20 \right)a_1 - 2\,a_0 = a_1 - 2\,a_0.</math>


Строка 92: Строка 93:


=== Признак делимости на 2 ===
=== Признак делимости на 2 ===
Число делится на [[2 (число)|2]] [[тогда и только тогда]], когда его последняя цифра делится на 2, то есть является [[Чётные и нечётные числа|чётной]].
Число делится на {{num1|2}} [[тогда и только тогда]], когда его последняя цифра делится на 2, то есть является [[Чётные и нечётные числа|чётной]].


Соответствующая признаку функция (см. раздел [[#Общие принципы построения|«Общие принципы построения»]]):
Соответствующая признаку функция (см. раздел [[#Общие принципы построения|«Общие принципы построения»]]):
: <math>A = 10\,a_1 + a_0,\quad 0 \leqslant a_0, < 10,\quad a_1 \geqslant 0,</math>
: <math>A = 10\,a_1 + a_0,\quad 0 \leqslant a_0 < 10,\quad a_1 \geqslant 0,</math>
: <math>F(A) = \begin{cases} a_0, & A \geqslant 10 \\ A - 2 , & 2 \leqslant A < 10. \end{cases}</math>
: <math>F(A) = \begin{cases} a_0, & A \geqslant 10 \\ A - 2 , & 2 \leqslant A < 10. \end{cases}</math>


Строка 101: Строка 102:


=== Признак делимости на 3 ===
=== Признак делимости на 3 ===
Число делится на [[3 (число)|3]], когда сумма его цифр делится на 3.
Число делится на {{num1|3}}, когда сумма его цифр делится на 3. Например, число 159 делится на 3, поскольку сумма его цифр 1 + 5 + 9 = 15 делится на 3.


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


=== Признак делимости на 4 ===
=== Признак делимости на 4 ===
Число делится на 4, когда две последние цифры или нули, или составляют число, делящееся на 4. Например, 14676 — последние цифры 76, и число 76 делится на 4: 76:4=19. Двузначное число делится на 4 тогда и только тогда, когда удвоенное число десятков, сложенное с числом единиц делится на 4. Например, число 42 не делится на 4, так как <math>2 \cdot 4 + 2 = 10</math> не делится на 4.
Число делится на {{num1|4}}, когда две последние цифры нули или составляют число, делящееся на 4. Например, 14676 — последние цифры 76, и число 76 делится на 4: 76:4=19. Двузначное число делится на 4 тогда и только тогда, когда удвоенная цифра в разряде десятков, сложенная с цифрой в разряде единиц, делится на 4. Например, число 42 не делится на 4, так как <math>2 \cdot 4 + 2 = 10</math> не делится на 4.


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


Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, <math>8 \cdot 2 + 7 = 23</math> и <math>2 \cdot 2 + 3 = 7</math> равноостаточны при делении на 4.
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, <math>8 \cdot 2 + 7 = 23</math> и <math>2 \cdot 2 + 3 = 7</math> равноостаточны при делении на 4.

Более простая формулировка: Число делится на 4, если в последнем разряде 0, 4, 8, а предпоследний разряд чётный; или если в последнем разряде 2, 6, а предпоследний разряд нечётный.


=== Признак делимости на 5 ===
=== Признак делимости на 5 ===
Число делится на [[5 (число)|5]] тогда и только тогда, когда последняя цифра делится на 5, т.&nbsp;е. если она 0 или 5.
Число делится на {{num1|5}} тогда и только тогда, когда оно оканчивается на 0 или на 5.


Соответствующая признаку функция:
Соответствующая признаку функция:
Строка 125: Строка 128:
: <math>F(A) = \begin{cases} a_0, & A \geqslant 10, \\ A - 5 , & 5 \leqslant A < 10. \end{cases}</math>
: <math>F(A) = \begin{cases} a_0, & A \geqslant 10, \\ A - 5 , & 5 \leqslant A < 10. \end{cases}</math>


Эта функция помимо признака делимости задаёт и признак равностаточности.
Эта функция помимо признака делимости задаёт и признак равноостаточности.


=== Признак делимости на 6 ===
=== Признак делимости на 6 ===
Число делится на [[6 (число)|6]] тогда, когда оно делится и на 2, и на 3 (то есть если оно четное и сумма его цифр делится на 3).
Число делится на {{num1|6}} тогда и только тогда, когда оно делится и на 2, и на 3 (то есть если оно чётное и сумма его цифр делится на 3).


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


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


=== Признак делимости на 7 ===
=== Признак делимости на 7 ===
''Признак 1'':
''Признак 1'': число делится на [[7 (число)|7]] когда утроенное число десятков, сложенное с числом единиц, делится на 7. Например, 154 делится на 7, так как на 7 делится <math>15 \cdot 3 + 4 = 49.</math> Другой пример — число 1001 делится на 7, так как на 7 делятся <math>100 \cdot 3 + 1 = 301,\quad 30 \cdot 3 +1 = 91,\quad 9 \cdot 3 + 1 = 28,\quad 2 \cdot 3 + 8 = 14.</math>

число делится на {{num1|7}} тогда, когда утроенное число десятков, сложенное с цифрой в разряде единиц, делится на 7. Например, 154 делится на 7, так как на 7 делится <math>15 \cdot 3 + 4 = 49.</math> 1001 делится на 7, так как на 7 делятся <math>100 \cdot 3 + 1 = 301,\quad 30 \cdot 3 +1 = 91,\quad 9 \cdot 3 + 1 = 28,\quad 2 \cdot 3 + 8 = 14,\quad 1 \cdot 3 + 4 = 7.</math>


Соответствующая этому признаку функция:
Соответствующая этому признаку функция:
Строка 147: Строка 152:
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, <math>8 \cdot 3 + 7 = 31,</math> <math>3 \cdot 3 + 1 = 10</math> и <math>1 \cdot 3 + 0 = 3</math> равноостаточны при делении на 7.
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, <math>8 \cdot 3 + 7 = 31,</math> <math>3 \cdot 3 + 1 = 10</math> и <math>1 \cdot 3 + 0 = 3</math> равноостаточны при делении на 7.


Модификации ''признака 1'':
''Признак 2''. число делится на 7 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по три цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 7. Например, 138689257 делится на 7, так как на 7 делится <math>\left | 138 - 689 + 257 \right | = 294.</math>

a) берётся первая цифра слева, умножается на 3, прибавляется следующая, и всё повторяется сначала: например, для 154: <math>1 \cdot 3 + 5 = 8,\quad 8 \cdot 3 + 4 = 28</math>. Также на каждом шаге можно брать остаток от деления на 7: <math>1 \cdot 3 + 5 = 8</math> остаток 1, <math>1 \cdot 3 + 4 = 7</math> остаток 0. В обоих случаях итоговое число равноостаточно при делении на 7 с исходным числом.

b) если удвоенное число единиц числа отнять от оставшегося числа десятков и результат будет делиться на 7, то число кратно 7. Например: 784 делится на 7, так как {{nobr|1=78 − (2 × 4) = 78 − 8 = 70}} (<math>a_1 - 2\,a_0 = 0 \bmod 7 \Leftrightarrow</math> <math>3\,a_1 - 6\,a_0 = 0 \bmod 7 \Leftrightarrow</math> <math>3\,a_1 - 6\,a_0 + 7\,a_0 = 0 \bmod 7 \Leftrightarrow</math> <math>3\,a_1 + a_0 = 0 \bmod 7</math>).

''Признак 2'':

число делится на 7 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по три цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «» делится на 7. Например, {{num|138689257}} делится на 7, так как на 7 делится <math>|138 - 689 + 257| = 294.</math>


Соответствующая этому признаку функция:
Соответствующая этому признаку функция:
: <math>A = \sum_{i=0}^n 1000^i a_i , \quad 0 \leqslant a_i < 1000,\quad i = 0, 1, \, \dots \, n,</math>
: <math>A = \sum_{i=0}^n 1000^i a_i , \quad 0 \leqslant a_i < 1000,\quad i = 0, 1, \, \dots \, n,</math>
: <math>F(A) = \begin{cases} \left | \sum_{i=0}^n \left ( -1 \right )^i a_i \right |, & A \geqslant 1000, \\ A - 7 , & 7 \leqslant A < 1000. \end{cases}</math>
: <math>F(A) = \begin{cases} \left | \sum_{i=0}^n \left ( -1 \right )^i a_i \right |, & A \geqslant 1000, \\ A - 7 , & 7 \leqslant A < 1000. \end{cases}</math>

''Признак 3'':

если разность между числом, состоящим из трёх последних цифр данного числа, и числом, образованным из оставшихся цифр данного числа (то есть без последних трёх цифр), делится на 7, то данное число делится на 7.
Пример для числа 1730736: 1730 − 736 = 994, 994 / 7 = 142.


=== Признак делимости на 8 ===
=== Признак делимости на 8 ===
Число делится на [[8 (число)|8]], когда три последние цифры или нули, или составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда число единиц, сложенное с удвоенным числом десятков и учетверённым числом сотен, делится на 8. Например, 952 делится на 8 так как на 8 делится <math>9 \cdot 4 + 5 \cdot 2 + 2 = 48.</math>
Число делится на {{num1|8}}, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой в разряде десятков и учетверённой цифрой в разряде сотен, делится на 8. Например, 952 делится на 8 так как на 8 делится <math>9 \cdot 4 + 5 \cdot 2 + 2 = 48.</math>


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


=== Признак делимости на 9 ===
=== Признак делимости на 9 ===
Число делится на [[9 (число)|9]], когда сумма его цифр делится на 9. Например, сумма цифр числа 12345678 делится на 9, следовательно и само число делится на 9. <math>1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36.</math>
Число делится на {{num1|9}}, когда сумма его цифр делится на 9. Например, сумма цифр числа 12345678 делится на 9, следовательно и само число делится на 9. <math>1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36.</math>


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


=== Признак делимости на 10 ===
=== Признак делимости на 10 ===
Число делится на [[10 (число)|10]] тогда и только тогда, когда оно оканчивается на [[Ноль (цифра)|н]]<nowiki/>уль.
Число делится на {{num1|10}} тогда и только тогда, когда оно оканчивается на [[Ноль (цифра)|ноль]].


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


=== Признаки делимости на 11 ===
=== Признаки делимости на 11 ===
''Признак 1:'' число делится на [[11 (число)|11]] тогда и только тогда, когда модуль разности между суммой цифр, занимающих нечётные позиции, и суммой цифр, занимающих чётные места делится на 11. Например, 9163627 делится на 11, так как <math>\left | (9 + 6 + 6 + 7) - (1 + 3 + 2) \right |= 22</math> делится на 11. Другой пример — 99077 делится на 11, так как <math>\left | (9 + 0 + 7) - (9 + 7) \right |= 0</math> делится на 11.
''Признак 1:'' число делится на {{num1|11}} тогда и только тогда, когда сумма цифр, занимающих нечётные позиции, равна сумме цифр, занимающих чётные места, или отличается от нее на число, кратное 11. Например, {{num|28017}} делится на 11, так как <math>(2 + 0 + 7) = (8 + 1)</math>.


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


Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 123456, <math>12 + 34 + 56 = 102</math> и <math>1 + 2 = 3</math> равноостаточны при делении на 11.
Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 123456, <math>12 + 34 + 56 = 102</math> и <math>1 + 2 = 3</math> равноостаточны при делении на 11.



=== Признак делимости на 13 ===
=== Признак делимости на 13 ===
Число делится на [[13 (число)|13]] тогда:- когда сумма числа десятков с учетверенным числом единиц делится на 13. Например
''Признак 1'': Число делится на {{num1|13}}, когда сумма числа десятков с учетверённой цифрой в разряде единиц делится на 13. Например
845 делится на 13, так как на 13 делятся <math>84 + 5 \cdot 4 = 104</math> и <math>10 + 4 \cdot 4 = 26.</math>
845 делится на 13, так как на 13 делятся <math>84 + 5 \cdot 4 = 104</math> и <math>10 + 4 \cdot 4 = 26.</math>


- когда разность числа десятков с девятикратным числом единиц делится на 13. Например
''Признак 2'': Число делится на {{num1|13}}, когда разность числа десятков с девятикратным числом, стоящего в разряде единиц, делится на 13. Например
845 делится на 13, так как на 13 делятся <math>84 - 9 \cdot 5 = 39.</math>
845 делится на 13, так как на 13 делятся <math>84 - 9 \cdot 5 = 39.</math>


Строка 206: Строка 223:
: <math>A = 10\,a_1 + a_0, \quad 0 \leqslant a_0 < 10, \quad a_1 \geqslant 0,</math>
: <math>A = 10\,a_1 + a_0, \quad 0 \leqslant a_0 < 10, \quad a_1 \geqslant 0,</math>
: <math>F(A) = \begin{cases} a_1 + 4\,a_0, & A \geqslant 40, \\ A - 13, & 13 \leqslant A < 40. \end{cases}</math>
: <math>F(A) = \begin{cases} a_1 + 4\,a_0, & A \geqslant 40, \\ A - 13, & 13 \leqslant A < 40. \end{cases}</math>

''Признак 3'': Число делится на {{num1|13}}, если разность между числом, состоящим из трёх последних цифр данного числа, и числом, образованным из оставшихся цифр данного числа (то есть без последних трёх цифр), делится на 13. Например 192218 делится на 13, так как 218-192=26, а 26 делится на 13.

''Признак 4'': Число делится на {{num1|13}} тогда, когда утроенное число десятков без цифры в разряде единиц, делится на {{num1|13}}. Например, <math>624</math> делится на <math>13</math>, так как <math>62 \cdot 3 - 4 =186-4= 182</math> и <math>18\cdot 3 - 2 =54-2= 52</math>, а также <math>5\cdot 3 - 2 =15-2= 13</math>, а <math>13</math> делится на <math>13</math>.


=== Признак делимости на 17 ===
=== Признак делимости на 17 ===
Число делится на [[17 (число)|17]] тогда:- когда модуль разности числа десятков и пятикратного числа единиц делится на 17. Например, 221 делится на 17, так как <math>\left| 22 - 5 \cdot 1 \right| = 17</math> делится на 17.
Число делится на {{num1|17}} в следующих случаях:
когда модуль разности числа десятков и умноженной на 5 цифрой в разряде единиц делится на 17. Например, 221 делится на 17, так как <math>\left| 22 - 5 \cdot 1 \right| = 17</math> делится на 17.


- когда модуль суммы числа десятков и числа двенадцать умноженной на кол-во единиц делится на 17. Например, 221 делится на 17, так как <math>\left| 22 + 12 \cdot 1 \right| = 34</math> делится на 17.
когда модуль суммы числа десятков и умноженной на 12 цифрой в разряде единиц делится на 17. Например, 221 делится на 17, так как <math>\left| 22 + 12 \cdot 1 \right| = 34</math> делится на 17.


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


=== Признак делимости на 19 ===
=== Признак делимости на 19 ===
Число делится на [[19 (число)|19]] тогда и только тогда, когда число десятков, сложенное с удвоенным числом единиц, делится на 19. Например, 646 делится на 19, так как на 19 делятся <math>64 + 2 \cdot 6 = 76</math> и <math>7 + 2 \cdot 6 = 19.</math>
Число делится на {{num1|19}} тогда и только тогда, когда число десятков, сложенное с удвоенной цифрой в разряде единиц, делится на 19. Например, 646 делится на 19, так как на 19 делятся <math>64 + 2 \cdot 6 = 76</math> и <math>7 + 2 \cdot 6 = 19.</math>


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


=== Признак делимости на 20 ===
=== Признак делимости на 20 ===
Число делится на [[20 (число)|20]] тогда и только тогда, когда число, образованное двумя последними цифрами, делится на 20.
Число делится на {{num1|20}} тогда и только тогда, когда число, образованное двумя последними цифрами, делится на 20.


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


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


=== Признаки делимости на 23 ===
=== Признаки делимости на 23 ===
''Признак 1'': число делится на [[23 (число)|23]] тогда и только тогда, когда число сотен, сложенное с утроенным числом, образованным двумя последними цифрами, делится на 23. Например, 28842 делится на 23, так как на 23 делятся <math>288 + 3 \cdot 42 = 414</math> и <math>4 + 3 \cdot 14 = 46.</math>
''Признак 1'': число делится на {{num1|23}} тогда и только тогда, когда число сотен, сложенное с утроенным числом, образованным двумя последними цифрами, делится на 23. Например, 28842 делится на 23, так как на 23 делятся <math>288 + 3 \cdot 42 = 414</math> и <math>4 + 3 \cdot 14 = 46.</math>




''Признак 2'': число делится на [[23 (число)|23]] тогда и только тогда, когда число десятков, сложенное с семикратным числом единиц, делится на 23. Например, 391 делится на 23, так как <math>39 + 7 \cdot 1 = 46</math> делится на 23.
''Признак 2'': число делится на 23 тогда и только тогда, когда число десятков, сложенное с умноженной на 7 цифрой в разряде единиц, делится на 23. Например, 391 делится на 23, так как <math>39 + 7 \cdot 1 = 46</math> делится на 23.




''Признак 3'': число делится на [[23 (число)|23]] тогда и только тогда, когда число сотен, сложенное с семикратным числом десятков и утроенным числом единиц, делится на 23. Например, 391 делится на 23, так как <math>3 + 7 \cdot 9 + 3 \cdot 1 = 69</math> делится на 23.
''Признак 3'': число делится на 23 тогда и только тогда, когда число сотен, сложенное с умноженной на 7 цифрой в разряде десятков и утроенной цифрой в разряде единиц, делится на 23. Например, 391 делится на 23, так как <math>3 + 7 \cdot 9 + 3 \cdot 1 = 69</math> делится на 23.


=== Признак делимости на 25 ===
=== Признак делимости на 25 ===
Число делится на [[25 (число)|25]] тогда и только тогда, когда две его последние цифры составляют число, которое делится на 25.
Число делится на {{num1|25}} тогда и только тогда, когда две его последние цифры составляют число, которое делится на 25. Другими словами, на 25 делятся числа, оканчивающиеся на 00, 25, 50 или 75.


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


=== Признак делимости на 27 ===
=== Признак делимости на 27 ===
Число делится на [[27 (число)|27]] тогда и только тогда, когда на 27 делится сумма чисел, образующих группы по три цифры (начиная с единиц).
Число делится на {{num1|27}} тогда и только тогда, когда на 27 делится сумма чисел, образующих группы по три цифры (начиная с единиц).


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


=== Признак делимости на 29 ===
=== Признак делимости на 29 ===
Число делится на [[29 (число)|29]] тогда и только тогда, когда число десятков, сложенное с утроенным числом единиц, делится на 29. Например, 261 делится на 29, так как <math>26 + 3 \cdot 1 = 29</math> делится на 29.
Число делится на {{num1|29}} тогда и только тогда, когда число десятков, сложенное с утроенной цифрой в разряде единиц, делится на 29. Например, 261 делится на 29, так как <math>26 + 3 \cdot 1 = 29</math> делится на 29.


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


=== Признак делимости на 30 ===
=== Признак делимости на 30 ===
Число делится на 30 тогда и только тогда, когда оно заканчивается на 0 и сумма всех цифр делится на 3. Например: 510 делится на 30, а 678 - нет.
Число делится на {{num1|30}} тогда и только тогда, когда оно заканчивается на 0 и сумма всех цифр делится на 3. Например: 510 делится на 30, а 678 — нет.


=== Признак делимости на 31 ===
=== Признак делимости на 31 ===
Число делится на [[31 (число)|31]] тогда и только тогда, когда модуль разности числа десятков и утроенного числа единиц делится на 31. Например, 217 делится на 31, так как <math>\left| 21 - 3 \cdot 7 \right| = 0</math> делится на 31.
Число делится на {{num1|31}} тогда и только тогда, когда модуль разности числа десятков и утроенной цифры в разряде единиц делится на 31. Например, 217 делится на 31, так как <math>\left| 21 - 3 \cdot 7 \right| = 0</math> делится на 31.


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


=== Признак делимости на 37 ===
=== Признак делимости на 37 ===
''Признак 1:'' число делится на [[37 (число)|37]] тогда и только тогда, когда при разбивании числа на группы по три цифры (начиная с единиц) сумма этих групп кратна 37.
''Признак 1:'' число делится на {{num1|37}} тогда и только тогда, когда при разбивании числа на группы по три цифры (начиная с единиц) сумма этих групп кратна 37.


Соответствующая признаку функция:
Соответствующая признаку функция:
Строка 287: Строка 310:
Эта функция помимо признака делимости задаёт и признак равноостаточности.
Эта функция помимо признака делимости задаёт и признак равноостаточности.


''Признак 2:'' число делится на 37 тогда и только тогда, когда на 37 делится модуль утроенного числа сотен, сложенного с учетверённым числом десятков, за вычетом числа единиц, умноженного на семь. Например, число 481 делится на 37, так как на 37 делится <math>\left | 3 \cdot 4 + 4 \cdot 8 - 7 \right | = 37.</math>
''Признак 2:'' число делится на 37 тогда и только тогда, когда на 37 делится модуль утроенного числа сотен, сложенного с учетверённой цифрой в разряде десятков, за вычетом цифры в разряде единиц, умноженной на семь. Например, число 481 делится на 37, так как на 37 делится <math>\left | 3 \cdot 4 + 4 \cdot 8 - 7 \cdot 1 \right | = 37.</math>


Соответствующая признаку функция:
Соответствующая признаку функция:
Строка 293: Строка 316:
: <math>F(A) = \left | 3 \, a_2 + 4 \, a_1 - 7 \, a_0 \right |, \quad A \geqslant 37.</math>
: <math>F(A) = \left | 3 \, a_2 + 4 \, a_1 - 7 \, a_0 \right |, \quad A \geqslant 37.</math>


''Признак 3:'' число делится на 37 тогда и только тогда, когда на 37 делится модуль суммы числа сотен с числом единиц, умноженного на десять, за вычетом числа десятков, умноженного на 11. Например, число 481 делится на 37, так как на 37 делится <math>\left | 4 - 11 \cdot 8 + 10 \cdot 1 \right | = 74.</math>
''Признак 3:'' число делится на 37 тогда и только тогда, когда на 37 делится модуль суммы числа сотен с цифрой в разряде единиц, умноженной на десять, за вычетом цифры в разряде десятков, умноженной на 11. Например, число 481 делится на 37, так как на 37 делится <math>\left | 4 - 11 \cdot 8 + 10 \cdot 1 \right | = 74.</math>


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


=== Признак делимости на 41 ===
=== Признак делимости на 41 ===
''Признак 1'': число делится на [[41 (число)|41]] тогда и только тогда, когда модуль разности числа десятков и четырёхкратного числа единиц делится на 41. Например, 369 делится на 41, так как <math>\left| 36 - 4 \cdot 9 \right| = 0</math> делится на 41.
''Признак 1'': число делится на {{num1|41}} тогда и только тогда, когда модуль разности числа десятков и четырёхкратной цифры в разряде единиц делится на 41. Например, 369 делится на 41, так как <math>\left| 36 - 4 \cdot 9 \right| = 0</math> делится на 41.


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


=== Признак делимости на 50 ===
=== Признак делимости на 50 ===
Число делится на [[50 (число)|50]] тогда и только тогда, когда число, образованное двумя его младшими десятичными цифрами, делится на 50.
Число делится на {{num1|50}} тогда и только тогда, когда число, образованное двумя его младшими десятичными цифрами, делится на 50.


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


=== Признак делимости на 59 ===
=== Признак делимости на 59 ===
Число делится на [[59 (число)|59]] тогда и только тогда, когда число десятков, сложенное с числом единиц, умноженное на 6, делится на 59. Например, 767 делится на 59, так как на 59 делятся <math>76 + 6 \cdot 7 = 118</math> и <math>11 + 6 \cdot 8 = 59.</math>
Число делится на {{num1|59}} тогда и только тогда, когда число десятков, сложенное с цифрой в разряде единиц, умноженной на 6, делится на 59. Например, 767 делится на 59, так как на 59 делятся <math>76 + 6 \cdot 7 = 118</math> и <math>11 + 6 \cdot 8 = 59.</math>


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


=== Признак делимости на 79 ===
=== Признак делимости на 79 ===
Число делится на [[79 (число)|79]] тогда и только тогда, когда число десятков, сложенное с числом единиц, умноженное на 8, делится на 79. Например, 711 делится на 79, так как на 79 делятся <math>71 + 8 \cdot 1 = 79</math>.
Число делится на {{num1|79}} тогда и только тогда, когда число десятков, сложенное с цифрой в разряде единиц, умноженной на 8, делится на 79. Например, 711 делится на 79, так как на 79 делятся <math>71 + 8 \cdot 1 = 79</math>.


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


=== Признак делимости на 99 ===
=== Признак делимости на 99 ===
Число делится на [[99 (число)|99]] тогда и только тогда, когда на 99 делится сумма чисел, образующих группы по две цифры (начиная с единиц). Например, 12573 делится на 99, так как на 99 делится <math>1 + 25 + 73 = 99.</math>
Число делится на {{num1|99}} тогда и только тогда, когда на 99 делится сумма чисел, образующих группы по две цифры (начиная с единиц). Например, 12573 делится на 99, так как на 99 делится <math>1 + 25 + 73 = 99.</math>


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


=== Признак делимости на 101 ===
=== Признак делимости на 101 ===
Число делится на 101 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по две цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 101. Например, 590547 делится на 101, так как на 101 делится <math>\left | 59 - 5 + 47 \right | = 101.</math>
Число делится на {{num1|101}} тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по две цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 101. Например, 590547 делится на 101, так как на 101 делится <math>\left | 59 - 5 + 47 \right | = 101.</math>


Соответствующая этому признаку функция:
Соответствующая этому признаку функция:
: <math>A = \sum_{i=0}^n 100^i a_i , \quad 0 \leqslant a_i < 100,\quad i = 0, 1, \, \dots \, n,</math>
: <math>A = \sum_{i=0}^n 100^i a_i , \quad 0 \leqslant a_i < 100,\quad i = 0, 1, \, \dots \, n,</math>
: <math>F(A) = \left | \sum_{i=0}^n \left ( -1 \right )^i a_i \right |, \quad A \geqslant 101.</math>
: <math>F(A) = \left | \sum_{i=0}^n \left ( -1 \right )^i a_i \right |, \quad A \geqslant 101.</math>

=== Признак делимости на 1091 ===
Число делится на 1091 тогда и только тогда, когда разность числа десятков и умноженной на 109 цифры в разряде единиц делится на 1091. Например, 18547 делится на 1091, так как 1854 - 7 * 109 = 1091 делится на 1091.


== Общие признаки делимости ==
== Общие признаки делимости ==
Строка 377: Строка 403:


Например, в десятичной системе счисления это позволяет построить признаки делимости на 7, 11, 13, 73, 77, 91, 101, 137, 143, 1001, 10001 и т. д.
Например, в десятичной системе счисления это позволяет построить признаки делимости на 7, 11, 13, 73, 77, 91, 101, 137, 143, 1001, 10001 и т. д.

=== Деление в столбик ===
Время работы алгоритма, проверяющего делимость числа <math>n</math> на некоторое другое число делением «в столбик», составляет <math>O(\log n)</math>. Таким образом во многих случаях так называемые «признаки делимости» не дают заметного выигрыша в количестве совершённых элементарных операций. Исключение составляют признаки делимости на числа вида <math>2^a5^b</math>, время работы которых не зависит от размера проверяемого числа.


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

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

* число делится на 10<sup>''n''</sup>, если оно оканчивается на ''n'' нулей.
* число делится на 10<sup>''n''</sup>, если оно оканчивается на ''n'' нулей.


Если основание системы счисления равно ''k'', то любое число делится на ''k-1'' тогда и только тогда, когда сумма его цифр делится на ''k-1'' без остатка. В частности:
Если основание системы счисления равно 1 [[сравнение по модулю|по модулю]] некоторого числа ''k'' (то есть остаток от деления основания на ''k'' равен 1), то любое число делится на ''k'' тогда и только тогда, когда сумма его цифр делится на ''k'' без остатка. В частности:
* число делится на 10 − 1, если сумма его цифр делится на 10 − 1;

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

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

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


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


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

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


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


== Литература ==
== Литература ==
* {{книга
* {{книга
|автор = [[Воробьёв, Николай Николаевич (математик)|Воробьёв Н. Н.]]
|автор = Воробьев Н. Н.
|заглавие = Признаки делимости
|заглавие = Признаки делимости
|ссылка = http://ilib.mccme.ru/plm/ann/a39.htm
|ссылка = http://ilib.mccme.ru/plm/ann/a39.htm
Строка 418: Строка 441:
== Примечания ==
== Примечания ==
{{примечания}}
{{примечания}}


<!-- перенаправление на [[:de:Teilbarkeit]] -->


[[Категория:Теоретико-числовые алгоритмы]]
[[Категория:Теоретико-числовые алгоритмы]]
[[Категория:Устный счёт]]
[[Категория:Устный счёт]]
[[Категория:Делимость и остатки]]
[[Категория:Делимость и остатки]]

<!-- перенаправление на [[:de:Teilbarkeit]] -->

Текущая версия от 18:40, 20 ноября 2024

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

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

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

[править | править код]

Если для двух целых чисел и существует такое целое число что

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

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

Два целых числа и равноостаточны при делении на натуральное число (или сравнимы по модулю ), если при делении на они дают одинаковые остатки, то есть существует такие целые числа что

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

[править | править код]

Пусть требуется определить, делится ли некоторое натуральное число на другое натуральное число Для этого возьмём последовательность натуральных чисел:

такую, что:

  1. каждый член последовательности определяется предыдущим;
  2. последний член последовательности меньше то есть
  3. все члены последовательности имеют одинаковые остатки при делении на

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

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

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

  1. при значение не определено;
  2. при значение есть натуральное число;
  3. если то
  4. если то и равноделимы на

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

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

  1. при значение не определено;
  2. при значение есть натуральное число;
  3. если то
  4. если то и равноостаточны при делении на

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

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

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

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

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

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

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

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

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

Для построения признаков равноостаточности и делимости чаще всего используется следующие теоремы:

  1. При любых целом и натуральном целые числа и равноостаточны при делении на
  2. При любых целом , натуральном , целые числа и равноделимы на если целое является взаимно простым с

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

[править | править код]

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

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

[править | править код]

Число делится на 3, когда сумма его цифр делится на 3. Например, число 159 делится на 3, поскольку сумма его цифр 1 + 5 + 9 = 15 делится на 3.

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 154, и равноостаточны при делении на 3.

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

[править | править код]

Число делится на 4, когда две последние цифры нули или составляют число, делящееся на 4. Например, 14676 — последние цифры 76, и число 76 делится на 4: 76:4=19. Двузначное число делится на 4 тогда и только тогда, когда удвоенная цифра в разряде десятков, сложенная с цифрой в разряде единиц, делится на 4. Например, число 42 не делится на 4, так как не делится на 4.

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, и равноостаточны при делении на 4.

Более простая формулировка: Число делится на 4, если в последнем разряде 0, 4, 8, а предпоследний разряд чётный; или если в последнем разряде 2, 6, а предпоследний разряд нечётный.

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

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

[править | править код]

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

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 73, и равноостаточны при делении на 6.

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

[править | править код]

Признак 1:

число делится на 7 тогда, когда утроенное число десятков, сложенное с цифрой в разряде единиц, делится на 7. Например, 154 делится на 7, так как на 7 делится 1001 делится на 7, так как на 7 делятся

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 87, и равноостаточны при делении на 7.

Модификации признака 1:

a) берётся первая цифра слева, умножается на 3, прибавляется следующая, и всё повторяется сначала: например, для 154: . Также на каждом шаге можно брать остаток от деления на 7: остаток 1, остаток 0. В обоих случаях итоговое число равноостаточно при делении на 7 с исходным числом.

b) если удвоенное число единиц числа отнять от оставшегося числа десятков и результат будет делиться на 7, то число кратно 7. Например: 784 делится на 7, так как 78 − (2 × 4) = 78 − 8 = 70 ( ).

Признак 2:

число делится на 7 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по три цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «−» делится на 7. Например, 138 689 257 делится на 7, так как на 7 делится

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

Признак 3:

если разность между числом, состоящим из трёх последних цифр данного числа, и числом, образованным из оставшихся цифр данного числа (то есть без последних трёх цифр), делится на 7, то данное число делится на 7. Пример для числа 1730736: 1730 − 736 = 994, 994 / 7 = 142.

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

[править | править код]

Число делится на 8, когда три последние цифры составляют число, делящееся на 8. Трёхзначное число делится на 8 тогда и только тогда, когда цифра в разряде единиц, сложенная с удвоенной цифрой в разряде десятков и учетверённой цифрой в разряде сотен, делится на 8. Например, 952 делится на 8 так как на 8 делится

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 567, и равноостаточны при делении на 8.

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 345, и равноостаточны при делении на 9.

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

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

[править | править код]

Признак 1: число делится на 11 тогда и только тогда, когда сумма цифр, занимающих нечётные позиции, равна сумме цифр, занимающих чётные места, или отличается от нее на число, кратное 11. Например, 28 017 делится на 11, так как .

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

Признак 2: число делится на 11 тогда и только тогда, когда на 11 делится сумма чисел, образующих группы по две цифры (начиная с единиц). Например, 103785 делится на 11, так как на 11 делятся и

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 123456, и равноостаточны при делении на 11.

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

[править | править код]

Признак 1: Число делится на 13, когда сумма числа десятков с учетверённой цифрой в разряде единиц делится на 13. Например 845 делится на 13, так как на 13 делятся и

Признак 2: Число делится на 13, когда разность числа десятков с девятикратным числом, стоящего в разряде единиц, делится на 13. Например 845 делится на 13, так как на 13 делятся

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

Признак 3: Число делится на 13, если разность между числом, состоящим из трёх последних цифр данного числа, и числом, образованным из оставшихся цифр данного числа (то есть без последних трёх цифр), делится на 13. Например 192218 делится на 13, так как 218-192=26, а 26 делится на 13.

Признак 4: Число делится на 13 тогда, когда утроенное число десятков без цифры в разряде единиц, делится на 13. Например, делится на , так как и , а также , а делится на .

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

[править | править код]

Число делится на 17 в следующих случаях:

— когда модуль разности числа десятков и умноженной на 5 цифрой в разряде единиц делится на 17. Например, 221 делится на 17, так как делится на 17.

— когда модуль суммы числа десятков и умноженной на 12 цифрой в разряде единиц делится на 17. Например, 221 делится на 17, так как делится на 17.

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

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

[править | править код]

Число делится на 19 тогда и только тогда, когда число десятков, сложенное с удвоенной цифрой в разряде единиц, делится на 19. Например, 646 делится на 19, так как на 19 делятся и

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

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

[править | править код]

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

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

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

[править | править код]

Признак 1: число делится на 23 тогда и только тогда, когда число сотен, сложенное с утроенным числом, образованным двумя последними цифрами, делится на 23. Например, 28842 делится на 23, так как на 23 делятся и


Признак 2: число делится на 23 тогда и только тогда, когда число десятков, сложенное с умноженной на 7 цифрой в разряде единиц, делится на 23. Например, 391 делится на 23, так как делится на 23.


Признак 3: число делится на 23 тогда и только тогда, когда число сотен, сложенное с умноженной на 7 цифрой в разряде десятков и утроенной цифрой в разряде единиц, делится на 23. Например, 391 делится на 23, так как делится на 23.

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

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

[править | править код]

Число делится на 29 тогда и только тогда, когда число десятков, сложенное с утроенной цифрой в разряде единиц, делится на 29. Например, 261 делится на 29, так как делится на 29.

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

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

[править | править код]

Число делится на 30 тогда и только тогда, когда оно заканчивается на 0 и сумма всех цифр делится на 3. Например: 510 делится на 30, а 678 — нет.

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

[править | править код]

Число делится на 31 тогда и только тогда, когда модуль разности числа десятков и утроенной цифры в разряде единиц делится на 31. Например, 217 делится на 31, так как делится на 31.

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

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

[править | править код]

Признак 1: число делится на 37 тогда и только тогда, когда при разбивании числа на группы по три цифры (начиная с единиц) сумма этих групп кратна 37.

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

Признак 2: число делится на 37 тогда и только тогда, когда на 37 делится модуль утроенного числа сотен, сложенного с учетверённой цифрой в разряде десятков, за вычетом цифры в разряде единиц, умноженной на семь. Например, число 481 делится на 37, так как на 37 делится

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

Признак 3: число делится на 37 тогда и только тогда, когда на 37 делится модуль суммы числа сотен с цифрой в разряде единиц, умноженной на десять, за вычетом цифры в разряде десятков, умноженной на 11. Например, число 481 делится на 37, так как на 37 делится

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

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

[править | править код]

Признак 1: число делится на 41 тогда и только тогда, когда модуль разности числа десятков и четырёхкратной цифры в разряде единиц делится на 41. Например, 369 делится на 41, так как делится на 41.

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

Признак 2: чтобы проверить, делится ли число на 41, его следует справа налево разбить на грани по 5 цифр в каждой. Затем в каждой грани первую справа цифру умножить на 1, вторую цифру умножить на 10, третью — на 18, четвёртую — на 16, пятую — на 37 и все полученные произведения сложить. Если результат будет делиться на 41, тогда и только тогда само число будет делиться на 41.

Есть и другие (более удобные) признаки делимости на 41, см. 41 (число).

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности.

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

[править | править код]

Число делится на 59 тогда и только тогда, когда число десятков, сложенное с цифрой в разряде единиц, умноженной на 6, делится на 59. Например, 767 делится на 59, так как на 59 делятся и

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

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

[править | править код]

Число делится на 79 тогда и только тогда, когда число десятков, сложенное с цифрой в разряде единиц, умноженной на 8, делится на 79. Например, 711 делится на 79, так как на 79 делятся .

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

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

[править | править код]

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

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

Эта функция помимо признака делимости задаёт и признак равноостаточности. Например, числа 123456, и равноостаточны при делении на 99.

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

[править | править код]

Число делится на 101 тогда и только тогда, когда модуль алгебраической суммы чисел, образующих нечётные группы по две цифры (начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делится на 101. Например, 590547 делится на 101, так как на 101 делится

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

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

[править | править код]

Число делится на 1091 тогда и только тогда, когда разность числа десятков и умноженной на 109 цифры в разряде единиц делится на 1091. Например, 18547 делится на 1091, так как 1854 - 7 * 109 = 1091 делится на 1091.

Общие признаки делимости

[править | править код]

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

[править | править код]

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

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

Например, в десятичной системе счисления это позволяет построить признаки делимости на 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50 и т. д.

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

[править | править код]

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

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

Например, в десятичной системе счисления это позволяет построить признаки делимости на 3, 9, 11, 27, 33, 37, 99, 101, 111, 303, 333, 999, 1111, 3333, 9999 и т. д.

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

[править | править код]

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

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

Например, в десятичной системе счисления это позволяет построить признаки делимости на 7, 11, 13, 73, 77, 91, 101, 137, 143, 1001, 10001 и т. д.

Деление в столбик

[править | править код]

Время работы алгоритма, проверяющего делимость числа на некоторое другое число делением «в столбик», составляет . Таким образом во многих случаях так называемые «признаки делимости» не дают заметного выигрыша в количестве совершённых элементарных операций. Исключение составляют признаки делимости на числа вида , время работы которых не зависит от размера проверяемого числа.

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

[править | править код]

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

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

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

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

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

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

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

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

Литература

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

Примечания

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