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


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

Общий вид

Пусть есть натуральное число A {displaystyle A} записываемое в десятичной системе счисления как a n a n − 1 … a 2 a 1 a 0 ¯ {displaystyle {overline {a_{n}a_{n-1}ldots a_{2}a_{1}a_{0}}}} , где a 0 {displaystyle a_{0}} — единицы, a 1 {displaystyle a_{1}} — десятки и т. д.

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

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

r 1 {displaystyle r_{1}} — остаток от деления 10 {displaystyle 10} на m {displaystyle m} r 2 {displaystyle r_{2}} — остаток от деления 10 ⋅ r 1 {displaystyle 10cdot r_{1}} на m {displaystyle m} r 3 {displaystyle r_{3}} — остаток от деления 10 ⋅ r 2 {displaystyle 10cdot r_{2}} на m {displaystyle m} … r n {displaystyle r_{n}} — остаток от деления 10 ⋅ r n − 1 {displaystyle 10cdot r_{n-1}} на m {displaystyle m} .

Формально:

r 1 ≡ 10 ( mod m ) {displaystyle r_{1}equiv 10{pmod {m}}} r i ≡ 10 ⋅ r i − 1 ( mod m ) , i = 2... n ¯ {displaystyle r_{i}equiv 10cdot r_{i-1}{pmod {m}},;i={overline {2...n}}}

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

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

r n ⋅ a n + … + r 2 ⋅ a 2 + r 1 ⋅ a 1 + a 0 {displaystyle r_{n}cdot a_{n}+ldots +r_{2}cdot a_{2}+r_{1}cdot a_{1}+a_{0}} .

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

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

A ( mod m ) = ( a n a n − 1 … a 2 a 1 a 0 ¯ ) ( mod m ) = ( a n a n − 1 … a 2 a 1 ¯ ⋅ 10 + a 0 ) ( mod m ) {displaystyle 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}}} = ( a n a n − 1 … a 2 a 1 ¯ ⋅ r 1 + a 0 r 0 ) ( mod m ) {displaystyle =({overline {a_{n}a_{n-1}ldots a_{2}a_{1}}}cdot r_{1}+a_{0}r_{0}){pmod {m}}} = ( ( a n a n − 1 … a 2 ¯ ⋅ 10 + a 1 ) ⋅ r 1 + a 0 r 0 ) ( mod m ) {displaystyle =(({overline {a_{n}a_{n-1}ldots a_{2}}}cdot 10+a_{1})cdot r_{1}+a_{0}r_{0}){pmod {m}}} = ( a n a n − 1 … a 2 ¯ ⋅ 10 r 1 + a 1 r 1 + a 0 r 0 ) ( mod m ) {displaystyle =({overline {a_{n}a_{n-1}ldots a_{2}}}cdot 10r_{1}+a_{1}r_{1}+a_{0}r_{0}){pmod {m}}} = ( a n a n − 1 … a 2 ¯ ⋅ r 2 + a 1 r 1 + a 0 r 0 ) ( mod m ) = … = {displaystyle =({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 + … + a 2 r 2 + a 1 r 1 + a 0 r 0 ) ( mod m ) {displaystyle (a_{n}r_{n}+ldots +a_{2}r_{2}+a_{1}r_{1}+a_{0}r_{0}){pmod {m}}}

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

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

Здесь m = 2 {displaystyle m=2} . Так как 10   ⋮   2 {displaystyle 10~vdots ~2} , то r 0 = 1 ,   r i = 0 ,   i ∈ N {displaystyle r_{0}=1,~r_{i}=0,~iin mathbb {N} } . Отсюда получаем известный признак: остаток от деления числа на 2 равен остатку от деления его последней цифры на 2, или обычно: число делится на 2, если его последняя цифра чётна.

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

Здесь m = 3 {displaystyle m=3} или m = 9 {displaystyle m=9} . Так как 10 i ≡ 1 ( mod 3 ) , i ∈ N {displaystyle 10^{i}equiv 1{pmod {3}},iin mathbb {N} } (остаток от деления 10 как на 3, так и на 9 равен 1), то все r i = 1 {displaystyle r_{i}=1} . Значит, остаток от деления числа на 3 (или на 9) равен остатку от деления суммы его цифр на 3 (соответственно, 9), или иначе: число делится на 3 (или 9), если сумма его цифр делится на 3 (или 9).

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

Здесь m = 4 {displaystyle m=4} . Находим последовательность остатков: r 0 = 1 ,   r 1 = 2 ,   r i = 0 ,   i ∈ N {displaystyle r_{0}=1,~r_{1}=2,~r_{i}=0,~iin mathbb {N} } . Отсюда получаем признак: остаток от деления числа на 4 равен остатку от деления 2 ⋅ a 1 + a 0 {displaystyle 2cdot a_{1}+a_{0}} на 4, или, заметив, что остаток зависит только от 2 последних цифр: число делится на 4, если число, состоящее из 2 его последних цифр, делится на 4.

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

Здесь m = 5 {displaystyle m=5} . Так как 10   ⋮   5 {displaystyle 10~vdots ~5} , то r 0 = 1 ,   r i = 0 ,   i ∈ N {displaystyle r_{0}=1,~r_{i}=0,~iin mathbb {N} } . Отсюда получаем известный признак: остаток от деления числа на 5 равен остатку от деления его последней цифры на 5, или обычно: число делится на 5, если его последняя цифра — 0 или 5.

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

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

  • 10 = 1 ⋅ 7 + 3 ⇒ r 1 = 3 {displaystyle 10=1cdot 7+3Rightarrow r_{1}=3}
  • 10 ⋅ r 1 = 4 ⋅ 7 + 2 ⇒ r 2 = 2 {displaystyle 10cdot r_{1}=4cdot 7+2Rightarrow r_{2}=2}
  • 10 ⋅ r 2 = 2 ⋅ 7 + 6 ⇒ r 3 = 6 {displaystyle 10cdot r_{2}=2cdot 7+6Rightarrow r_{3}=6}
  • 10 ⋅ r 3 = 8 ⋅ 7 + 4 ⇒ r 4 = 4 {displaystyle 10cdot r_{3}=8cdot 7+4Rightarrow r_{4}=4}
  • 10 ⋅ r 4 = 5 ⋅ 7 + 5 ⇒ r 5 = 5 {displaystyle 10cdot r_{4}=5cdot 7+5Rightarrow r_{5}=5}
  • 10 ⋅ r 5 = 7 ⋅ 7 + 1 ⇒ r 6 = 1 = r 0 {displaystyle 10cdot r_{5}=7cdot 7+1Rightarrow r_{6}=1=r_{0}} , цикл замкнулся.

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

    A = a n a n − 1 … a 2 a 1 a 0 ¯ {displaystyle A={overline {a_{n}a_{n-1}ldots a_{2}a_{1}a_{0}}}}

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

    a 0 + 3 a 1 + 2 a 2 + 6 a 3 + 4 a 4 + 5 a 5 + a 6 + … {displaystyle a_{0}+3a_{1}+2a_{2}+6a_{3}+4a_{4}+5a_{5}+a_{6}+ldots } .

    Пример

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

    48916 ≡ 6 + 3 ⋅ 1 + 2 ⋅ 9 + 6 ⋅ 8 + 4 ⋅ 4 = {displaystyle 48916equiv 6+3cdot 1+2cdot 9+6cdot 8+4cdot 4=} 6 + 3 + 18 + 48 + 16 = 91 ≡ 0 ( mod 7 ) {displaystyle 6+3+18+48+16=91equiv 0{pmod {7}}} ,

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

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

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

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

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

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

    Имя:*
    E-Mail:
    Комментарий: