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

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

Общий видПравить

Пусть есть натуральное число $A$$A$ , записываемое в десятичной системе счисления как $\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2{a}_1{a}_0}$$\overline {a_{n}a_{{n-1}}\ldots a_{2}a_{1}a_{0}}$ , где $a_0$$a_{0}$  — единицы, $a_1$$a_{1}$  — десятки и т. д.

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

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

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

$r_2$$r_{2}$  — остаток от деления $10\cdot <!--\; \cdot \; -->r_1$$10\cdot r_{1}$  на $m$$m$ 

$r_3$$r_3$  — остаток от деления $10\cdot <!--\; \cdot \; -->r_2$$10\cdot r_{2}$  на $m$$m$ 

…

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

Формально:

$r_1\equiv <!--\; \equiv \; -->10(\mathrm{mod}m)$$r_{1}\equiv 10{\pmod m}$ 

$r_i\equiv <!--\; \equiv \; -->10\cdot <!--\; \cdot \; -->r_{i-<!--\; -\; -->1}(\mathrm{mod}m),i=\stackrel{¯<!--\; ¯\; -->}{\mathrm{2...}n}$$r_{i}\equiv 10\cdot r_{{i-1}}{\pmod m},\;i=\overline {2...n}$ 

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

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

$r_n\cdot <!--\; \cdot \; -->a_n+\dots <!--\; \dots \; -->+r_2\cdot <!--\; \cdot \; -->a_2+r_1\cdot <!--\; \cdot \; -->a_1+a_0$$r_{n}\cdot a_{n}+\ldots +r_{2}\cdot a_{2}+r_{1}\cdot a_{1}+a_{0}$ .

ДоказательствоПравить

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

$A(\mathrm{mod}m)=(\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2{a}_1{a}_0})(\mathrm{mod}m)=(\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2{a}_1}\cdot <!--\; \cdot \; -->10+a_0)(\mathrm{mod}m)$$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}}$  $=(\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2{a}_1}\cdot <!--\; \cdot \; -->r_1+a_0{r}_0)(\mathrm{mod}m)$$=({\overline {a_{n}a_{n-1}\ldots a_{2}a_{1}}}\cdot r_{1}+a_{0}r_{0}){\pmod {m}}$  $=((\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2}\cdot <!--\; \cdot \; -->10+a_1)\cdot <!--\; \cdot \; -->r_1+a_0{r}_0)(\mathrm{mod}m)$$=(({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot 10+a_{1})\cdot r_{1}+a_{0}r_{0}){\pmod {m}}$  $=(\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2}\cdot <!--\; \cdot \; -->10r_1+a_1{r}_1+a_0{r}_0)(\mathrm{mod}m)$$=({\overline {a_{n}a_{n-1}\ldots a_{2}}}\cdot 10r_{1}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}$  $=(\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2}\cdot <!--\; \cdot \; -->r_2+a_1{r}_1+a_0{r}_0)(\mathrm{mod}m)=\dots <!--\; \dots \; -->=$$=({\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+\dots <!--\; \dots \; -->+a_2{r}_2+a_1{r}_1+a_0{r}_0)(\mathrm{mod}m)$$(a_{n}r_{n}+\ldots +a_{2}r_{2}+a_{1}r_{1}+a_{0}r_{0}){\pmod {m}}$ 

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

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

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

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

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

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

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

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

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

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

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

1. $10=1\cdot <!--\; \cdot \; -->7+3\Rightarrow <!--\; \Rightarrow \; -->r_1=3$$10=1\cdot 7+3\Rightarrow r_{1}=3$ 
2. $10\cdot <!--\; \cdot \; -->r_1=4\cdot <!--\; \cdot \; -->7+2\Rightarrow <!--\; \Rightarrow \; -->r_2=2$$10\cdot r_{1}=4\cdot 7+2\Rightarrow r_{2}=2$ 
3. $10\cdot <!--\; \cdot \; -->r_2=2\cdot <!--\; \cdot \; -->7+6\Rightarrow <!--\; \Rightarrow \; -->r_3=6$$10\cdot r_{2}=2\cdot 7+6\Rightarrow r_{3}=6$ 
4. $10\cdot <!--\; \cdot \; -->r_3=8\cdot <!--\; \cdot \; -->7+4\Rightarrow <!--\; \Rightarrow \; -->r_4=4$$10\cdot r_{3}=8\cdot 7+4\Rightarrow r_{4}=4$ 
5. $10\cdot <!--\; \cdot \; -->r_4=5\cdot <!--\; \cdot \; -->7+5\Rightarrow <!--\; \Rightarrow \; -->r_5=5$$10\cdot r_{4}=5\cdot 7+5\Rightarrow r_{5}=5$ 
6. $10\cdot <!--\; \cdot \; -->r_5=7\cdot <!--\; \cdot \; -->7+1\Rightarrow <!--\; \Rightarrow \; -->r_6=1=r_0$$10\cdot r_{5}=7\cdot 7+1\Rightarrow r_{6}=1=r_{0}$ , цикл замкнулся.

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

$A=\stackrel{¯<!--\; ¯\; -->}{a_n{a}_{n-<!--\; -\; -->1}\dots <!--\; \dots \; -->a_2{a}_1{a}_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+\dots <!--\; \dots \; -->$$a_{0}+3a_{1}+2a_{2}+6a_{3}+4a_{4}+5a_{5}+a_{6}+\ldots$ .

ПримерПравить

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

$48916\equiv <!--\; \equiv \; -->6+3\cdot <!--\; \cdot \; -->1+2\cdot <!--\; \cdot \; -->9+6\cdot <!--\; \cdot \; -->8+4\cdot <!--\; \cdot \; -->4=$$48916\equiv 6+3\cdot 1+2\cdot 9+6\cdot 8+4\cdot 4=$ 

$6+3+18+48+16=91\equiv <!--\; \equiv \; -->0(\mathrm{mod}7)$$6+3+18+48+16=91\equiv 0{\pmod {7}}$ ,

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

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

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

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

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

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

ЛитератураПравить

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