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

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

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


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

bq=a,bq=a,
 то говорят, что число aa делится на b.b.
 Два целых числа aa и bb называются равноделимыми на m,m, еслилибо они оба делятся на m,m, либо оба не делятся.
 Два целых числа aa и bb равноостаточны при делении нанатуральное число mm (или сравнимы по модулю mm), если приделении на mm они дают одинаковые остатки, то есть существует такиецелые числа q1,q2,r,q1,q2,r, что

a=mq1+r,b=mq2+r.a=mq1+r,b=mq2+r.

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


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

A0,A1,A2,A3,,An,A0,A1,A2,A3,,An,
 такую, что:

  1. A0=A;A0=A;
  2. каждый член последовательности вполне определяется предыдущим;
  3. Ai<Ai1,i=1,2,3,,n1;Ai<Ai1,i=1,2,3,,n1;
  4. последний член последовательности меньше m,m, то есть 0An<m.0An<m.
  5. все члены последовательности являются равноделимыми на m.m.

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

Ai=f(Ai1),i=1,2,3,,n,Ai=f(Ai1),i=1,2,3,,n,
 удовлетворяющей следующим условиям:

  1. при x<mx<m значение f(x)f(x) не определено;
  2. при xmxm значение f(x)f(x) есть натуральное число;
  3. если xm,xm, то f(x)<x;f(x)<x;
  4. если xm,xm, то f(x)f(x) и xx равноделимы на m.m.

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

Ai=f(Ai1),i=1,2,3,,n,Ai=f(Ai1),i=1,2,3,,n,
 удовлетворяющей следующим условиям:

  1. при x<mx<m значение f(x)f(x) не определено;
  2. при xmxm значение f(x)f(x) есть натуральное число;
  3. если xm,xm, то f(x)<x;f(x)<x;
  4. если xm,xm, то f(x)f(x) и xx равноостаточны при делении на m.m.

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

f(x)=xm,xm,f(x)=xm,xm,
 а последовательность, построенная с её помощью будет иметь вид:

A,Am,A2m,A3m,A,Am,A2m,A3m,
 По сути применение признака равноостаточности на базе этой функцииэквивалентно делению при помощи вычитания.
 Другим примером может служить общеизвестный признак делимости (а такжеравноостаточности) на 10.

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

A=10b+a,0a<10,b0.A=10b+a,0a<10,b0.
 Тогда остатком от деления AA на 10 будет aa. Функция, описывающая этопризнак равноостаточности будет выглядеть как

f(A)=a,A10.f(A)=a,A10.
 Легко доказать, что эта функция удовлетворяет всем перечисленным вышетребованиям. Причём последовательность, построенная с её помощью, будетсодержать всего один или два члена.
 Также легко видеть, что такой признак ориентирован именно на десятичноепредставление числа AA — так, например, если применять его накомпьютере, использующем двоичную запись числа, то чтобы выяснить aa,программе пришлось бы сначала поделить AA на 10.
 Для построения признаков равноостаточности и делимости чаще всегоиспользуется следующие теоремы:

  1. При любых целом qq и натуральном mm целые числа AA и A+mqA+mq равноостаточны при делении на m.m.
  2. При любых целом qq, натуральном mm, целые числа AA и pA+mqpA+mq равноделимы на m,m, если целое pp является взаимно простым с m.m.

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


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


 Число делится на тогда и только тогда, когда его последняя цифра делитсяна 2, то есть является чётной.
 Соответствующая признаку функция (см. раздел «Общие принципыпостроения»):

A=10a1+a0,0a0,<10,a10,A=10a1+a0,0a0,<10,a10,
F(A)={a0,A10A2,2A<10.F(A)={a0,A2,A102A<10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.

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


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

A=ni=010iai,0ai<10,i=0,1,n,A=ni=010iai,0ai<10,i=0,1,n,
F(A)={ni=0ai,A10,A3,3A<10.F(A)={ni=0ai,A3,A10,3A<10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 154, 1+5+4=10 и 1+0=1равноостаточны при делении на 3.

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


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

A=100a2+10a1+a0,0a0<10,0a1<10,a20,
F(A)={2a1+a0,A10,A4,4A<10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 87, 82+7=23 и22+3=7 равноостаточны при делении на 4.
 Более простая формулировка: Число делится на 4, если в последнем разряде0, 4, 8, а предпоследний разряд чётный; или если в последнем разряде 2,6, а предпоследний разряд нечётный.

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


 Число делится на тогда и только тогда, когда оно оканчивается на 0 илина 5.
 Соответствующая признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={a0,A10,A5,5A<10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.

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


 Число делится на тогда, когда оно делится и на 2, и на 3 (то есть еслионо четное и сумма его цифр делится на 3).
 Другой признак делимости: число делится на 6 тогда и только тогда, когдаучетверённое число десятков, сложенное с цифрой в разряде единиц,делится на 6.
 Соответствующая признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={4a1+a0,A10,A6,6A<10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 73, 74+3=31,34+1=13 и 14+3=7 равноостаточны при делении на6.

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


Признак 1: число делится на тогда, когда утроенное числодесятков, сложенное с цифрой в разряде единиц, делится на 7. Например,154 делится на 7, так как на 7 делится 153+4=49. 1001делится на 7, так как на 7 делятся1003+1=301,303+1=91,93+1=28,23+8=14,13+4=7.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={3a1+a0,A10,A7,7A<10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 87, 83+7=31,33+1=10 и 13+0=3 равноостаточны при делении на7.
 Модификация признака 1: Берётся первая слева цифра, умножается на3, прибавляется следующая, и всё повторяется сначала: например, для 154:13+5=8,83+4=28. Также на каждом шаге можнобрать остаток от деления на 7: 13+5=8 остаток 1,13+4=14 остаток 0. В обоих случаях итоговое числоравноостаточно при делении на 7 с исходным числом.
Признак 2: число делится на 7 тогда и только тогда, когда модульалгебраической суммы чисел, образующих нечётные группы по три цифры(начиная с единиц), взятых со знаком «+», и чётных со знаком «-» делитсяна 7. Например, делится на 7, так как на 7 делится|138689+257|=294.
 Соответствующая этому признаку функция:

A=ni=01000iai,0ai<1000,i=0,1,n,
F(A)={|ni=0(1)iai|,A1000,A7,7A<1000.
Признак 3: если разность между числом, состоящим из 3 последнихцифр данного числа, и числом, образованным из оставшихся цифр данногочисла (то есть без последних 3 цифр), делится на 7, то данное числоделится на 7. Пример для числа 1730736: 1730-736=994, 994/7=142.
Признак 4: если удвоенное число единиц числа отнять отоставшегося числа десятков и результат будет делиться на 7, то числократно 7. Например: 784 делится на 7, так как 78-(2×4)=78-8=70

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


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

A=1000a3+100a2+10a1+a0,0a0<10,0a1<10,0a2<10,a30,
F(A)={4a2+2a1+a0,A10,A8,8A<10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 567,54+62+7=39, 32+9=15 и12+5=7 равноостаточны при делении на 8.

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


 Число делится на , когда сумма его цифр делится на 9. Например, суммацифр числа 12345678 делится на 9, следовательно и само число делится на9. 1+2+3+4+5+6+7+8=36.
 Соответствующая признаку функция:

A=ni=010iai,0ai<10,i=0,1,n,
F(A)={ni=0ai,A10,0,A=9.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 345, 3+4+5=12 и 1+2=3равноостаточны при делении на 9.

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


 Число делится на тогда и только тогда, когда оно оканчивается на ноль.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)=a0,A10.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.

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


Признак 1: число делится на тогда и только тогда, когда модульразности между суммой цифр, занимающих нечётные позиции, и суммой цифр,занимающих чётные места, делится на 11. Например, делится на 11, так как|(9+6+6+7)(1+3+2)|=22 делится на 11.Другой пример — 99077 делится на 11, так как|(9+0+7)(9+7)|=0 делится на 11.
 Соответствующая этому признаку функция:

A=ni=010iai0ai<10,i=0,1,n,
F(A)=|ni=0(1)iai|,A11.
Признак 2: число делится на 11 тогда и только тогда, когда на 11делится сумма чисел, образующих группы по две цифры (начиная с единиц).Например, 103785 делится на 11, так как на 11 делятся10+37+85=132 и 01+32=33.
 Соответствующая признаку функция:

A=ni=0100iai,0ai<100,i=0,1,n,
F(A)={ni=0ai,A100,A11,11A<100.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 123456, 12+34+56=102 и1+2=3 равноостаточны при делении на 11.

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


Признак 1: Число делится на , когда сумма числа десятков сучетверенной цифрой в разряде единиц делится на 13. Например 845 делитсяна 13, так как на 13 делятся 84+54=104 и10+44=26.
 - когда разность числа десятков с девятикратным числом, стоящего вразряде единиц, делится на 13. Например 845 делится на 13, так как на 13делятся 8495=39.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={a1+4a0,A40,A13,13A<40.
Признак 2: зачеркнув в данном числе три последние цифры, вычитаютиз числа, образованного оставшимися цифрами, число, образованноезачеркнутыми цифрами (или наоборот, в зависимости от того, какое из нихбольше); если остаток равен нулю или делится на 13, то данное числоразделится.

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


 Число делится на тогда:- когда модуль разности числа десятков иумноженной на 5 цифрой в разряде единиц делится на 17. Например, 221делится на 17, так как |2251|=17 делится на17.
 - когда модуль суммы числа десятков и числа двенадцать умноженной накол-во единиц делится на 17. Например, 221 делится на 17, так как|22+121|=34 делится на 17.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={|a15a0|,A40,A17,17A<40.

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


 Число делится на тогда и только тогда, когда число десятков, сложенное судвоенной цифрой в разряде единиц, делится на 19. Например, 646 делитсяна 19, так как на 19 делятся 64+26=76 и7+26=19.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={a1+2a0,A20,0,A=19.

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


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

A=100a1+a0,0a0<100,a10,
F(A)={a0,A100,A20,20A<100.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.

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


Признак 1: число делится на тогда и только тогда, когда числосотен, сложенное с утроенным числом, образованным двумя последнимицифрами, делится на 23. Например, 28842 делится на 23, так как на 23делятся 288+342=414 и 4+314=46.
Признак 2: число делится на 23 тогда и только тогда, когда числодесятков, сложенное с умноженной на 7 цифрой в разряде единиц, делитсяна 23. Например, 391 делится на 23, так как 39+71=46делится на 23.
Признак 3: число делится на 23 тогда и только тогда, когда числосотен, сложенное с умноженной на 7 цифрой в разряде десятков и утроеннойцифрой в разряде единиц, делится на 23. Например, 391 делится на 23, таккак 3+79+31=69 делится на 23.

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


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

A=100a1+a0,0a0<100,a10,
F(A)={a0,A100,A25,25A<100.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.

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


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

A=ni=01000iai,0ai<1000,i=0,1,n,
F(A)={ni=0ai,A1000,A27,27A<1000.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.

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


 Число делится на тогда и только тогда, когда число десятков, сложенное сутроенной цифрой в разряде единиц, делится на 29. Например, 261 делитсяна 29, так как 26+31=29 делится на 29.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={a1+3a0,A30,0,A=29.

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


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

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


 Число делится на тогда и только тогда, когда модуль разности числадесятков и утроенной цифры в разряде единиц делится на 31. Например, 217делится на 31, так как |2137|=0 делится на31.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)=|a13a0|,A31.

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


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

A=ni=01000iai,0ai<1000,i=0,1,n,
F(A)={ni=0ai,A1000,A37,37A<1000.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.
Признак 2: число делится на 37 тогда и только тогда, когда на 37делится модуль утроенного числа сотен, сложенного с учетверённой цифройв разряде десятков, за вычетом цифры в разряде единиц, умноженной насемь. Например, число 481 делится на 37, так как на 37 делится|34+487|=37.
 Соответствующая признаку функция:

A=100a2+10a1+a0,0a0<10,0a1<10,a20,
F(A)=|3a2+4a17a0|,A37.
Признак 3: число делится на 37 тогда и только тогда, когда на 37делится модуль суммы числа сотен с цифрой в разряде единиц, умноженнойна десять, за вычетом цифры в разряде десятков, умноженной на 11.Например, число 481 делится на 37, так как на 37 делится|4118+101|=74.
 Соответствующая признаку функция:

A=100a2+10a1+a0,0a0<10,0a1<10,a20,
F(A)={|a211a1+10a0|,A100,A37,37A<100.

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


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

A=10a1+a0,0a0<10,a10,
F(A)=|a14a0|,A41.
Признак 2: чтобы проверить, делится ли число на 41, его следуетсправа налево разбить на грани по 5 цифр в каждой. Затем в каждой гранипервую справа цифру умножить на 1, вторую цифру умножить на 10, третью— на 18, четвёртую — на 16, пятую — на 37 и все полученныепроизведения сложить. Если результат будет делиться на 41, тогда итолько тогда само число будет делиться на 41.
 Есть и другие (более удобные) признаки делимости на 41, см. 41 (число).

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


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

A=100a1+a0,0a0<100,a10,
F(A)={a0,A100,A50,50A<100.
 Эта функция помимо признака делимости задаёт и признакравноостаточности.

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


 Число делится на тогда и только тогда, когда число десятков, сложенное сцифрой в разряде единиц, умноженной на 6, делится на 59. Например, 767делится на 59, так как на 59 делятся 76+67=118 и11+68=59.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={a1+6a0,A60,0,A=59.

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


 Число делится на тогда и только тогда, когда число десятков, сложенное сцифрой в разряде единиц, умноженной на 8, делится на 79. Например, 711делится на 79, так как на 79 делятся 71+81=79.
 Соответствующая этому признаку функция:

A=10a1+a0,0a0<10,a10,
F(A)={a1+8a0,A80,0,A=79.

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


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

A=ni=0100iai,0ai<100,i=0,1,n,
F(A)={ni=0ai,A100,0,A=99.
 Эта функция помимо признака делимости задаёт и признакравноостаточности. Например, числа 123456, 12+34+56=102 и1+2=3 равноостаточны при делении на 99.

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


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

A=ni=0100iai,0ai<100,i=0,1,n,
F(A)=|ni=0(1)iai|,A101.

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


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


 Если для некоторых натуральных t и n число tn делится нанатуральное m, то любое целое число A, записанное в системесчисления по основанию t, равноостаточно с числом, образованным nмладшими его цифрами. Это свойство позволяет построить признак делимостии равноостаточности на делитель степени основания системы счисления.
 Соответствующая этому признаку функция:

A=tna1+a0,0a0<tn,a10,tnm,
F(A)={a0,Atn,Am,mA<tn.
 Например, в десятичной системе счисления это позволяет построитьпризнаки делимости на 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50 и т. д.

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


 Если для некоторых натуральных t и n число tn1 делится нанатуральное m, то любое целое число A, записанное в системесчисления по основанию t, равноделимо с суммой чисел, образованныхразбиением на группы по n цифр, начиная с самой младшей. Это свойствопозволяет построить признак делимости на m.
 Соответствующая этому признаку функция:

A=ni=0tinai,0ai<tn,(tn1)m,
F(A)={ni=0ai,Atn,Am,mA<tn.
 Например, в десятичной системе счисления это позволяет построитьпризнаки делимости на 3, 9, 11, 27, 33, 37, 99, 101, 111, 303, 333, 999,1111, 3333, 9999 и т. д.

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


 Если для некоторых натуральных t и n число tn+1 делится нанатуральное m, то любое целое число A, записанное в системесчисления по основанию t, равноделимо с модулем знакопеременной суммычисел, образованных разбиением на группы по n цифр, начиная с самоймладшей. Это свойство позволяет построить признак делимости на m.
 Соответствующая этому признаку функция:

A=ni=0tinai,0ai<tn,(tn+1)m,
F(A)={|ni=0(1)iai|,Atn,Am,mA<tn.
 Например, в десятичной системе счисления это позволяет построитьпризнаки делимости на 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.