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

Материал из Википедии — свободной энциклопедии

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

Содержание

1 Общий вид
2 Основные частные случаи
3 Литература

[править] Общий вид

Пусть есть натуральное число $~A$ записываемое в десятичной системе счисления как $\overline{a_na_{n-1}\ldots a_2a_1a_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$ .

[править] Основные частные случаи

[править] Признак делимости на 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$ . Находим остатки.

$10 = 1\cdot 7 + 3 \Rightarrow r_1 = 3$
$10\cdot r_1 = 4\cdot 7 + 2 \Rightarrow r_2 = 2$
$10\cdot r_2 = 2\cdot 7 + 6 \Rightarrow r_3 = 6$
$10\cdot r_3 = 8\cdot 7 + 4 \Rightarrow r_4 = 4$
$10\cdot r_4 = 5\cdot 7 + 5 \Rightarrow r_5 = 5$
$10\cdot r_5 = 7\cdot 7 + 1 \Rightarrow r_6 = 1 = r_0$ , цикл замкнулся.

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

$A=\overline{a_na_{n-1}\ldots a_2a_1a_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 результата будет такой же, что и у первоначального числа.