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

Общий вид

Пусть есть натуральное число ${\displaystyle A}$ , записываемое в десятичной системе счисления как ${\displaystyle {\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}}}}$ , где ${\displaystyle a_{0}}$ — единицы, ${\displaystyle a_{1}}$ — десятки и т. д.

Пусть ${\displaystyle m}$ — произвольное натуральное число, на которое мы хотим делить и выводить признак делимости на него.

Находим ряд остатков по следующей схеме:

${\displaystyle r_{1}}$ — остаток от деления ${\displaystyle 10}$ на ${\displaystyle m}$

${\displaystyle r_{2}}$ — остаток от деления ${\displaystyle 10\cdot r_{1}}$ на ${\displaystyle m}$

${\displaystyle r_{3}}$ — остаток от деления ${\displaystyle 10\cdot r_{2}}$ на ${\displaystyle m}$

…

${\displaystyle r_{n}}$ — остаток от деления ${\displaystyle 10\cdot r_{n-1}}$ на ${\displaystyle m}$ .

Формально:

${\displaystyle r_{1}\equiv 10{\pmod {m}}}$

${\displaystyle r_{i}\equiv 10\cdot r_{i-1}{\pmod {m}},\;i={\overline {2...n}}}$

Так как остатков конечное число (а именно не больше ${\displaystyle m}$ ), то этот процесс зациклится (не позже, чем через ${\displaystyle m}$ шагов) и дальше можно его не продолжать: Начиная с некоторого ${\displaystyle i=i_{0}:~r_{i+p}=r_{i}}$ , где ${\displaystyle p}$ — получившийся период последовательности ${\displaystyle \{r_{i}\}}$ . Для единообразия можно принять, что ${\displaystyle r_{0}=1}$ .

Тогда ${\displaystyle A}$ имеет тот же остаток от деления на ${\displaystyle m}$ , что и число

${\displaystyle r_{n}\cdot a_{n}+\ldots +r_{2}\cdot a_{2}+r_{1}\cdot a_{1}+a_{0}}$ .

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

Пользуясь тем, что в алгебраическом выражении по модулю ${\displaystyle m}$ можно заменять числа их остатками от деления на ${\displaystyle m}$ , получаем:

${\displaystyle A{\pmod {m}}=({\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}}}){\pmod {m}}=({\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}}}\cdot 10+a_{0}){\pmod {m}}}$ ${\displaystyle =({\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}}}\cdot r_{1}+a_{0}r_{0}){\pmod {m}}}$ ${\displaystyle =(({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot 10+a_{1})\cdot r_{1}+a_{0}r_{0}){\pmod {m}}}$ ${\displaystyle =({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot 10r_{1}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}}$ ${\displaystyle =({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot r_{2}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}=\ldots =}$ ${\displaystyle (a_{n}r_{n}+\ldots +a_{2}r_{2}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}}$

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

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

Здесь ${\displaystyle m=2}$ . Так как ${\displaystyle 10~\vdots ~2}$ , то ${\displaystyle r_{0}=1,~r_{i}=0,~i\in \mathbb {N} }$ . Отсюда получаем известный признак: остаток от деления числа на 2 равен остатку от деления его последней цифры на 2 , или обычно: число делится на 2, если его последняя цифра чётна .

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

Здесь ${\displaystyle m=3}$ или ${\displaystyle m=9}$ . Так как ${\displaystyle 10^{i}\equiv 1{\pmod {3}},i\in \mathbb {N} }$ ( остаток от деления 10 как на 3, так и на 9 равен 1 ), то все ${\displaystyle r_{i}=1}$ . Значит, остаток от деления числа на 3 (или на 9) равен остатку от деления суммы его цифр на 3 (соответственно, 9) , или иначе: число делится на 3 (или 9), если сумма его цифр делится на 3 (или 9) .

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

Здесь ${\displaystyle m=4}$ . Находим последовательность остатков: ${\displaystyle r_{0}=1,~r_{1}=2,~r_{i}=0,~i\in \mathbb {N} }$ . Отсюда получаем признак: остаток от деления числа на 4 равен остатку от деления ${\displaystyle 2\cdot a_{1}+a_{0}}$ на 4 , или, заметив, что остаток зависит только от 2 последних цифр: число делится на 4, если число, состоящее из 2 его последних цифр, делится на 4 .

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

Здесь ${\displaystyle m=5}$ . Так как ${\displaystyle 10~\vdots ~5}$ , то ${\displaystyle r_{0}=1,~r_{i}=0,~i\in \mathbb {N} }$ . Отсюда получаем известный признак: остаток от деления числа на 5 равен остатку от деления его последней цифры на 5 , или обычно: число делится на 5, если его последняя цифра — 0 или 5 .

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

Здесь ${\displaystyle m=7}$ . Находим остатки.

1. ${\displaystyle 10=1\cdot 7+3\Rightarrow r_{1}=3}$
2. ${\displaystyle 10\cdot r_{1}=4\cdot 7+2\Rightarrow r_{2}=2}$
3. ${\displaystyle 10\cdot r_{2}=2\cdot 7+6\Rightarrow r_{3}=6}$
4. ${\displaystyle 10\cdot r_{3}=8\cdot 7+4\Rightarrow r_{4}=4}$
5. ${\displaystyle 10\cdot r_{4}=5\cdot 7+5\Rightarrow r_{5}=5}$
6. ${\displaystyle 10\cdot r_{5}=7\cdot 7+1\Rightarrow r_{6}=1=r_{0}}$ , цикл замкнулся.

Следовательно, для любого числа

${\displaystyle A={\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}}}}$

его остаток от деления на 7 равен

${\displaystyle a_{0}+3a_{1}+2a_{2}+6a_{3}+4a_{4}+5a_{5}+a_{6}+\ldots }$ .

Пример

Рассмотрим число 48916. По доказанному выше,

${\displaystyle 48916\equiv 6+3\cdot 1+2\cdot 9+6\cdot 8+4\cdot 4=}$

${\displaystyle 6+3+18+48+16=91\equiv 0{\pmod {7}}}$ ,

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

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

Здесь ${\displaystyle m=11}$ . Так как ${\displaystyle 10^{2n}=99\cdot 101\ldots 01+1\equiv 1{\pmod {11}}}$ , то все ${\displaystyle r_{2i}=1}$ , а ${\displaystyle r_{2i-1}=10\equiv -1{\pmod {11}}}$ . Отсюда можно получить простой признак делимости на 11:

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

Проще говоря:

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

Литература

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