Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

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

Пусть есть натуральное число ~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. Находим остатки.

  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_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 результата будет такой же, что и у первоначального числа.

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

Шаблон:Нет интервики

Викия-сеть

Случайная вики