Русская Википедия:Признак Паскаля
При́знак Паска́ля — математический метод, позволяющий получить признаки делимости на любое число. Своего рода «универсальный признак делимости».
Общий вид
Пусть есть натуральное число <math>A</math>, записываемое в десятичной системе счисления как <math>\overline{a_na_{n-1}\ldots a_2a_1a_0}</math>, где <math>a_0</math> — единицы, <math>a_1</math> — десятки и т. д.
Пусть <math>m</math> — произвольное натуральное число, на которое мы хотим делить и выводить признак делимости на него.
Находим ряд остатков по следующей схеме:
- <math>r_1</math> — остаток от деления <math>10</math> на <math>m</math>
- <math>r_2</math> — остаток от деления <math>10\cdot r_1</math> на <math>m</math>
- <math>r_3</math> — остаток от деления <math>10\cdot r_2</math> на <math>m</math>
- …
- <math>r_n</math> — остаток от деления <math>10\cdot r_{n-1}</math> на <math>m</math>.
Формально:
- <math>r_1\equiv 10\pmod m</math>
- <math>r_i\equiv 10\cdot r_{i-1}\pmod m, \; i=\overline{2...n}</math>
Так как остатков конечное число (а именно не больше <math>m</math>), то этот процесс зациклится (не позже, чем через <math>m</math> шагов) и дальше можно его не продолжать: Начиная с некоторого <math>i=i_0:~r_{i+p}=r_i</math>, где <math>p</math> — получившийся период последовательности <math>\{r_i\}</math>. Для единообразия можно принять, что <math>r_0=1</math>.
Тогда <math>A</math> имеет тот же остаток от деления на <math>m</math>, что и число
<math>r_n\cdot a_n + \ldots + r_2\cdot a_2 + r_1\cdot a_1 + a_0</math>.
Доказательство
Пользуясь тем, что в алгебраическом выражении по модулю <math>m</math> можно заменять числа их остатками от деления на <math>m</math>, получаем:
<math>A \pmod m= (\overline{a_na_{n-1}\ldots a_2a_1a_0}) \pmod m = (\overline{a_na_{n-1}\ldots a_2a_1} \cdot 10 + a_0) \pmod m</math> <math> =(\overline{a_na_{n-1}\ldots a_2a_1} \cdot r_1 + a_0 r_0) \pmod m </math> <math> =((\overline{a_na_{n-1}\ldots a_2} \cdot 10 + a_1) \cdot r_1 + a_0 r_0) \pmod m </math> <math> =(\overline{a_na_{n-1}\ldots a_2} \cdot 10 r_1 + a_1 r_ 1 + a_0 r_0) \pmod m </math> <math> =(\overline{a_na_{n-1}\ldots a_2} \cdot r_2 + a_1 r_ 1 + a_0 r_0) \pmod m = \ldots =</math> <math> (a_n r_n + \ldots + a_2 r_2 + a_1 r_1 + a_0 r_0) \pmod m</math>
Основные частные случаи
Признак делимости на 2
Здесь <math>m=2</math>. Так как <math>10~\vdots~2</math>, то <math>r_0=1,~r_i=0,~i\in\mathbb{N}</math>. Отсюда получаем известный признак: остаток от деления числа на 2 равен остатку от деления его последней цифры на 2, или обычно: число делится на 2, если его последняя цифра чётна.
Признаки делимости на 3 и 9
Здесь <math>m=3</math> или <math>m=9</math>. Так как <math>10^i\equiv 1 \pmod 3, i\in\mathbb{N}</math> (остаток от деления 10 как на 3, так и на 9 равен 1), то все <math>r_i=1</math>. Значит, остаток от деления числа на 3 (или на 9) равен остатку от деления суммы его цифр на 3 (соответственно, 9), или иначе: число делится на 3 (или 9), если сумма его цифр делится на 3 (или 9).
Признак делимости на 4
Здесь <math>m=4</math>. Находим последовательность остатков: <math>r_0=1,~r_1=2,~r_i=0,~i\in\mathbb{N}</math>. Отсюда получаем признак: остаток от деления числа на 4 равен остатку от деления <math>2 \cdot a_1 + a_0</math> на 4, или, заметив, что остаток зависит только от 2 последних цифр: число делится на 4, если число, состоящее из 2 его последних цифр, делится на 4.
Признак делимости на 5
Здесь <math>m=5</math>. Так как <math>10~\vdots ~5</math>, то <math>r_0=1,~r_i=0,~i\in\mathbb{N}</math>. Отсюда получаем известный признак: остаток от деления числа на 5 равен остатку от деления его последней цифры на 5, или обычно: число делится на 5, если его последняя цифра — 0 или 5.
Признак делимости на 7
Здесь <math>m=7</math>. Находим остатки.
- <math>10 = 1\cdot 7 + 3 \Rightarrow r_1 = 3</math>
- <math>10\cdot r_1 = 4\cdot 7 + 2 \Rightarrow r_2 = 2</math>
- <math>10\cdot r_2 = 2\cdot 7 + 6 \Rightarrow r_3 = 6</math>
- <math>10\cdot r_3 = 8\cdot 7 + 4 \Rightarrow r_4 = 4</math>
- <math>10\cdot r_4 = 5\cdot 7 + 5 \Rightarrow r_5 = 5</math>
- <math>10\cdot r_5 = 7\cdot 7 + 1 \Rightarrow r_6 = 1 = r_0</math>, цикл замкнулся.
Следовательно, для любого числа
- <math>A=\overline{a_na_{n-1}\ldots a_2a_1a_0}</math>
его остаток от деления на 7 равен
- <math>a_0 + 3a_1 + 2a_2 + 6a_3 + 4a_4 + 5a_5 + a_6 + \ldots</math>.
Пример
Рассмотрим число 48916. По доказанному выше,
- <math>48916\equiv 6 + 3\cdot 1 + 2\cdot 9 + 6\cdot 8 + 4\cdot 4=</math>
- <math>6+3+18+48+16=91 \equiv 0 \pmod 7</math>,
а значит, 48916 делится на 7.
Признак делимости на 11
Здесь <math>m=11</math>. Так как <math>10^{2n}=99\cdot 101\ldots 01+1\equiv 1 \pmod {11}</math>, то все <math>r_{2i}=1</math>, а <math>r_{2i-1}=10\equiv -1 \pmod {11}</math>. Отсюда можно получить простой признак делимости на 11:
- остаток от деления числа на 11 равен остатку от деления его суммы цифр, где каждая нечётная (начиная с единиц) цифра взята со знаком «−», на 11.
Проще говоря:
- если разбить все цифры числа на 2 группы — через одну цифру (в одну группу попадут все цифры с нечётными позициями, в другую — с чётными), сложить все цифры в каждой группе и вычесть одну полученную сумму из другой, то остаток от деления на 11 результата будет такой же, что и у первоначального числа.
Литература
