Признак Паскаля

Признак Паскаля — метод, позволяющий получить признакиделимости на любое число. Своего рода «универсальный признак делимости».

Общий вид


 Пусть есть натуральное число A записываемое в десятичной системесчисления как anan1a2a1a0¯, где a0 —единицы, a1 — десятки и т. д.
 Пусть m — произвольное натуральное число, на которое мы хотим делитьи выводить признак делимости на него.
 Находим ряд остатков по следующей схеме:

r1 — остаток от деления 10 на m
r2 — остаток от деления 10r1 на m
r3 — остаток от деления 10r2 на m
 \ldots
rn — остаток от деления 10rn1 на m.
 Формально:

r110(modm)
ri10ri1(modm),i=2...n¯
 Так как остатков конечное число (а именно m), то этот процессзациклится (не позже, чем через m шагов) и дальше можно его непродолжать: Начиная с некоторого i=i0:ri+p=ri, где p —получившийся период последовательности {ri}. Для единообразия можнопринять, что r0=1.
 Тогда A имеет тот же остаток от деления на m, что и число
rnan++r2a2+r1a1+a0.

Доказательство


 Пользуясь тем, что в алгебраическом выражении по модулю m можнозаменять числа их остатками от деления на m, получаем:
A(modm)=(anan1a2a1a0¯)(modm)=(anan1a2a1¯10+a0)(modm)=(anan1a2a1¯r1+a0r0)(modm)=((anan1a2¯10+a1)r1+a0r0)(modm)=(anan1a2¯10r1+a1r1+a0r0)(modm)=(anan1a2¯r2+a1r1+a0r0)(modm)==(anrn++a2r2+a1r1+a0r0)(modm)

Основные частныеслучаи


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


 Здесь m=2. Так как 102, то r0=1,ri=0,iN.Отсюда получаем известный признак: остаток от деления числа на 2равен остатку от деления его последней цифры на 2, или обычно:число делится на 2, если его последняя цифра чётна.

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


 Здесь m=3 или m=9. Так как 10i1(mod3),iN(остаток от деления 10 как на 3, так и на 9 равен 1), то всеri=1. Значит, остаток от деления числа на 3 (или на 9) равеностатку от деления суммы его цифр на 3 (соответственно, 9), или иначе:число делится на 3 (или 9), если сумма его цифр делится на 3(или 9).

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


 Здесь m=4. Находим последовательность остатков:r0=1,r1=2,ri=0,iN. Отсюда получаем признак:остаток от деления числа на 4 равен остатку от деления2a1+a0 на 4, или, заметив, что остаток зависит только от 2последних цифр: число делится на 4, если число, состоящее из 2его последних цифр, делится на 4.

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


 Здесь m=5. Так как 105, то r0=1,ri=0,iN.Отсюда получаем известный признак: остаток от деления числа на 5равен остатку от деления его последней цифры на 5, или обычно:число делится на 5, если его последняя цифра — 0 или 5.

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


 Здесь m=7. Находим остатки.

  1. 10=17+3r1=3
  2. 10r1=47+2r2=2
  3. 10r2=27+6r3=6
  4. 10r3=87+4r4=4
  5. 10r4=57+5r5=5
  6. 10r5=77+1r6=1=r0, цикл замкнулся.

 Следовательно, '''для любого числа
A=anan1a2a1a0¯
его остаток от деления на 7равен
a0+3a1+2a2+6a3+4a4+5a5+a6+
'''.

agraphПример
 Рассмотрим число 48916. По доказанному выше,
489166+31+29+68+44=



6+3+18+48+16=910(mod7),

 а значит, 48916 делится на 7.

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


 Здесь m=11. Так как102n=9910101+11(mod11), то все r2i=1r2i1=101(mod11). Отсюда можно получить простойпризнак делимости на 11:

 остаток от деления числа на 11 равен остатку от деления его суммы цифр,где каждая нечётная (начиная с единиц) цифра взята со знаком «−», на 11.
 Проще говоря:

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