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

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

Общий вид


 Пусть есть натуральное число 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=1, а r2i1=101(mod11). Отсюда можно получить простой признак делимости на 11:

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

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