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

[Батороев]

незваный гость писал(а):

:evil:
По сути, известные мне признаки деления на нечётное число сводятся к выбору степени $10^k$ для которой $n|10^k \pm 1$.

Причем, $10$ может быть любым числом, записанным в соответствующей системе счисления.

Например, в двоичной системе $ 111|10^{11} -1$ (где $ 11 = 3_{10} $), следовательно,
$...a_9a_8a_7a_6a_5a_4a_3a_2a_1a_0 \equiv (a_2a_1a_0)+(a_5a_4a_3)+(a_8a_7a_6)+...$ по модулю $111$ ($7_{10}$).

[Droog_Andrey]

Droog_Andrey на форуме iXBT 11 лет назад писал(а):

Вот как найти классический признак делимости на простое число $N$ в системе счисления $D$.

Если $D$ делится на $N$, то делимость проверяемого числа сводится к делимости последнего его разряда.

Если же $D$ не делится на $N$, то находим минимальное положительное $m$, такое, что $D^{2m}-1$ делится на $N$. Например, пусть $D=10$ и $N=13$, тогда $m=3$.
Проверяемое число разбиваем справа налево на группы по $m$ разрядов, и если $D^m-1$ делится на $N$, то складываем все группы, а если $D^m+1$ делится на $N$, то поочерёдно складываем/отнимаем. Делимость результата совпадёт с делимостью исходного числа, это и есть признак.

В нашем примере $10^3+1$ делится на $13$, поэтому разбиваем на группы по три разряда и поочерёдно складываем/отнимаем. Пусть проверяемое число $18446744073709551615$. Тогда раз $+018-446+744-073+709-551+615 = 1016$ не делится на $13$, то и число не делится на $13$.

(Оффтоп)

Правда, человек опытный заметил бы, что число это - $2^{64}-1$ ("шахматное" число), а поскольку $64 = 4 (\mod 12)$, а $2^4-1 = 15$ не делится на $13$, то и "шахматное" число не делится.

P.S. Совпадает не только делимость, но и остаток от деления, если крайняя справа группа берётся со знаком "$+$" (как в примере).

[Батороев]

Не прошлоо и двадцати лет, а уже отвечаю.

Вам то, что напишу, наверняка было известно (я, по-видимому, дошел до этого позже), но школьникам будет полезно.

Разбивая число на группы по $m$ разрядов, мы тем самым переходим в $10^m$ - ричную систему.
В Вашем примере, разбили число на группы по три разряда, следовательно, перешли в $1000$ - ричную систему.
Для $1000$ -ричной следующей системой будет $1000+1=1001$ - ричная.
Число $1001=7\cdot 11\cdot 13$. Поэтому описанный Вами способ проверки годится также и для $7$, и для $11$, и для любых произведений этих простых.