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

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

Общий вид

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

1. <math>10 = 1\cdot 7 + 3 \Rightarrow r_1 = 3</math>
2. <math>10\cdot r_1 = 4\cdot 7 + 2 \Rightarrow r_2 = 2</math>
3. <math>10\cdot r_2 = 2\cdot 7 + 6 \Rightarrow r_3 = 6</math>
4. <math>10\cdot r_3 = 8\cdot 7 + 4 \Rightarrow r_4 = 4</math>
5. <math>10\cdot r_4 = 5\cdot 7 + 5 \Rightarrow r_5 = 5</math>
6. <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 (mod\ 7)</math>,

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

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

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

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

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

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

Литература

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

Отрывок, характеризующий Признак Паскаля

Старик находился в хорошем расположении духа после дообеденного сна. (Он говорил, что после обеда серебряный сон, а до обеда золотой.) Он радостно из под своих густых нависших бровей косился на сына. Князь Андрей подошел и поцеловал отца в указанное им место. Он не отвечал на любимую тему разговора отца – подтруниванье над теперешними военными людьми, а особенно над Бонапартом.
– Да, приехал к вам, батюшка, и с беременною женой, – сказал князь Андрей, следя оживленными и почтительными глазами за движением каждой черты отцовского лица. – Как здоровье ваше?
– Нездоровы, брат, бывают только дураки да развратники, а ты меня знаешь: с утра до вечера занят, воздержен, ну и здоров.
– Слава Богу, – сказал сын, улыбаясь.
– Бог тут не при чем. Ну, рассказывай, – продолжал он, возвращаясь к своему любимому коньку, – как вас немцы с Бонапартом сражаться по вашей новой науке, стратегией называемой, научили.
Князь Андрей улыбнулся.
– Дайте опомниться, батюшка, – сказал он с улыбкою, показывавшею, что слабости отца не мешают ему уважать и любить его. – Ведь я еще и не разместился.
– Врешь, врешь, – закричал старик, встряхивая косичкою, чтобы попробовать, крепко ли она была заплетена, и хватая сына за руку. – Дом для твоей жены готов. Княжна Марья сведет ее и покажет и с три короба наболтает. Это их бабье дело. Я ей рад. Сиди, рассказывай. Михельсона армию я понимаю, Толстого тоже… высадка единовременная… Южная армия что будет делать? Пруссия, нейтралитет… это я знаю. Австрия что? – говорил он, встав с кресла и ходя по комнате с бегавшим и подававшим части одежды Тихоном. – Швеция что? Как Померанию перейдут?
Князь Андрей, видя настоятельность требования отца, сначала неохотно, но потом все более и более оживляясь и невольно, посреди рассказа, по привычке, перейдя с русского на французский язык, начал излагать операционный план предполагаемой кампании. Он рассказал, как девяностотысячная армия должна была угрожать Пруссии, чтобы вывести ее из нейтралитета и втянуть в войну, как часть этих войск должна была в Штральзунде соединиться с шведскими войсками, как двести двадцать тысяч австрийцев, в соединении со ста тысячами русских, должны были действовать в Италии и на Рейне, и как пятьдесят тысяч русских и пятьдесят тысяч англичан высадятся в Неаполе, и как в итоге пятисоттысячная армия должна была с разных сторон сделать нападение на французов. Старый князь не выказал ни малейшего интереса при рассказе, как будто не слушал, и, продолжая на ходу одеваться, три раза неожиданно перервал его. Один раз он остановил его и закричал:
– Белый! белый!
Это значило, что Тихон подавал ему не тот жилет, который он хотел. Другой раз он остановился, спросил:
– И скоро она родит? – и, с упреком покачав головой, сказал: – Нехорошо! Продолжай, продолжай.
В третий раз, когда князь Андрей оканчивал описание, старик запел фальшивым и старческим голосом: «Malbroug s'en va t en guerre. Dieu sait guand reviendra». [Мальбрук в поход собрался. Бог знает вернется когда.]
Сын только улыбнулся.
– Я не говорю, чтоб это был план, который я одобряю, – сказал сын, – я вам только рассказал, что есть. Наполеон уже составил свой план не хуже этого.
– Ну, новенького ты мне ничего не сказал. – И старик задумчиво проговорил про себя скороговоркой: – Dieu sait quand reviendra. – Иди в cтоловую.


В назначенный час, напудренный и выбритый, князь вышел в столовую, где ожидала его невестка, княжна Марья, m lle Бурьен и архитектор князя, по странной прихоти его допускаемый к столу, хотя по своему положению незначительный человек этот никак не мог рассчитывать на такую честь. Князь, твердо державшийся в жизни различия состояний и редко допускавший к столу даже важных губернских чиновников, вдруг на архитекторе Михайле Ивановиче, сморкавшемся в углу в клетчатый платок, доказывал, что все люди равны, и не раз внушал своей дочери, что Михайла Иванович ничем не хуже нас с тобой. За столом князь чаще всего обращался к бессловесному Михайле Ивановичу.
В столовой, громадно высокой, как и все комнаты в доме, ожидали выхода князя домашние и официанты, стоявшие за каждым стулом; дворецкий, с салфеткой на руке, оглядывал сервировку, мигая лакеям и постоянно перебегая беспокойным взглядом от стенных часов к двери, из которой должен был появиться князь. Князь Андрей глядел на огромную, новую для него, золотую раму с изображением генеалогического дерева князей Болконских, висевшую напротив такой же громадной рамы с дурно сделанным (видимо, рукою домашнего живописца) изображением владетельного князя в короне, который должен был происходить от Рюрика и быть родоначальником рода Болконских. Князь Андрей смотрел на это генеалогическое дерево, покачивая головой, и посмеивался с тем видом, с каким смотрят на похожий до смешного портрет.