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

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

Общий вид

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

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

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

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

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

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

…

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

Формально:

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

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

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

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

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

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

Пользуясь тем, что в алгебраическом выражении по модулю $m$ можно заменять числа их остатками от деления на $m$, получаем $A={\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}a_{0}}}={\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}}}\cdot 10+a_{0}{}$Невозможно разобрать выражение (SVG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://localhost:6011/ru.wikipedia.org/v1/»:): {\displaystyle ={} \overline{a_na_{n-1}\ldots a_2a_1} \cdot r_1 + a_0 r_0 \pmod m {}} $={}{\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot 10r_{1}+a_{1}r_{1}+a_{0}r_{0}{\pmod {m}}{}$$={}{\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot r_{2}+a_{1}r_{1}+a_{0}r_{0}{\pmod {m}}=\ldots {}$$={}a_{n}r_{n}+\ldots +a_{2}r_{2}+a_{1}r_{1}+a_{0}r_{0}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

$6+3+18+48+16=91\equiv 0(mod\ 7)$,

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

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

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

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

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

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

Литература

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