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

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

Общий вид

Пусть есть натуральное число $A$, записываемое в десятичной системе счисления как $\overline{a_n{a}_{n-1}\dots 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(\mathrm{mod}m)$

$r_i\equiv 10\cdot r_{i-1}(\mathrm{mod}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+\dots +r_2\cdot a_2+r_1\cdot a_1+a_0$.

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

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

$A(\mathrm{mod}m)=(\overline{a_n{a}_{n-1}\dots a_2{a}_1{a}_0})(\mathrm{mod}m)=(\overline{a_n{a}_{n-1}\dots a_2{a}_1}\cdot 10+a_0)(\mathrm{mod}m)$ $=(\overline{a_n{a}_{n-1}\dots a_2{a}_1}\cdot r_1+a_0{r}_0)(\mathrm{mod}m)$ $=((\overline{a_n{a}_{n-1}\dots a_2}\cdot 10+a_1)\cdot r_1+a_0{r}_0)(\mathrm{mod}m)$ $=(\overline{a_n{a}_{n-1}\dots a_2}\cdot 10r_1+a_1{r}_1+a_0{r}_0)(\mathrm{mod}m)$ $=(\overline{a_n{a}_{n-1}\dots a_2}\cdot r_2+a_1{r}_1+a_0{r}_0)(\mathrm{mod}m)=\dots =$ $(a_n{r}_n+\dots +a_2{r}_2+a_1{r}_1+a_0{r}_0)(\mathrm{mod}m)$

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

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

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

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

Здесь $m=3$ или $m=9$. Так как $10^i\equiv 1(\mathrm{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⋮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}\dots a_2{a}_1{a}_0}$

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

$a_0+3a_1+2a_2+6a_3+4a_4+5a_5+a_6+\dots$.

Пример

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

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

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

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

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

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

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

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

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

Литература

• Шаблон:Книга