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

[Батороев]

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

Начнем с делимости чисел на $ 11 $.

1. Число делится на $11 $, если знакопеременная сумма его цифр (последняя цифра со знаком +) делится на $ 11 $.

Кто еще какие признаки знает?

[Brukvalub]

Вот в этой брошюрке: Воробьев Н.Н. — Признаки делимости вопрос рассмотрен всесторонне.

[Батороев]

Красивая книжка...
с подписью: "Скачать книжку с нашего сайта нельзя".

[PAV]

А poiskknig на что?

http://www.poiskknig.ru/cgi-bin/poisk.cgi?lang=ru&st=%D0%BF%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%B8+%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8&network=1

[Батороев]

Brukvalub, PAV , спасибо!
Посмотрел книжку Н. Н. Воробьева. "Признаки делимости" и нашел, что хотел.

Ранее странным показалось, что среди признаков делимости на $11$ в Инете не нашел, такой:
2. Число делится на 11, если сумма двойных разрядов делится на 11.
(Например, $ 143564 $ на $11$ не делится, т.к. на него не делится $14+35+64=113 $, в отличии от числа $143561 $).

Сам признак то может и не столь существенен, как тот принцип, на котором он основывается.

Т.е. имеется число $ n $, делимость на которое необходимо проверить число $ m $.

Необходимо найти такое $ k $, чтобы
$ 10^k\equiv 1\pmod {n} $. (1)

После этого число $ m $ разбивается на $k$ разрядов, находится сумма полученных чисел (из $k$ разрядов), которая затем проверяется делится ли она на $n$.

Все такие операции можно производить в любой системе счисления. Тогда вместо $ 10 $ в выражении (1) подставляем соответсвующее основание.
Особенно интересным, мне показалось, что делимость на $7$ можно проверить, разбив любое число по три разряда в двоичной системе (что очень удобно для компьютера ).

[TOTAL]

Батороев писал(а):

1. Число делится на $11 $, если знакопеременная сумма его цифр (последняя цифра со знаком +) делится на $ 11 $.

Кто еще какие признаки знает?

Я знаю другой признак деления на 11:
Число делится на $11 $, если знакопеременная сумма его цифр (последняя цифра со знаком $-$) делится на $ 11 $.

[Батороев]

Со знаком + удобнее вычислять остаток, если число все же не делится на $11$.

[ip]

Еще для 11:
Если сумма всех нечетных, начиная с конца цифр, и сумма всех четных цифр, умноженная на 10, делится на 11, то и все число делится на 11, это легко проверяется.

[Батороев]

Мне, главным образом, хотелось обсудить тот принцип, который я описал в посте №5 в данной теме.

Но коль пошла такая пьянка

Тогда, вот такой (из любимых ):

Число делится на $ 11 $ ( $7,13$), если знакопеременная сумма из трех разрядов числа делится на $ 11 $ ($7, 13 $).

[ИСН]

Все признаки делимости сводятся к факторизации чисел, состоящих главным образом из девяток (вариант: нулей). А дальше банально.

[e7e5]

Как доказать признак делимости, например на 3?

[ip]

Любое число можно написать, разбив по разрядам. На пример для 3-х значного числа это будет выглядеть так: a+10b+100c, где a,b и c - цифры единиц, десятков и сотен соответственно. Теперь выделим часть, которая при любых значениях переменных будет кратна трем: 9b+99c+a+b+c. Чтобы все число было кратно трем, надо чтобы и a+b+c было кратно трем, а это на самом деле сумма цифр этого числа. Чтобы число делилось на 3 достаточно,чтобы его сумма цифр делилась на 3.

[Батороев]

ИСН писал(а):

Все признаки делимости сводятся к факторизации чисел, состоящих главным образом из девяток (вариант: нулей). А дальше банально.

Мне все же кажется, что для определения признаков делимости можно использовать несколько принципов.

Например, такой:
Допустим, имеется число в десятичной записи:
$A =a_n...a_4a_3a_2a_1a_0 $
Для того, чтобы определить делится ли данное число на $ 7 $, можно рассмотреть остатки степеней десятки или, что эквивалентно, степеней тройки по основанию $7$.
$3^0\equiv 1\pmod {7} $
$3^1\equiv 3\pmod {7} $
$3^2\equiv 2\pmod {7} $
$3^3\equiv 6\pmod {7} $
$3^4\equiv 4\pmod {7} $
$3^5\equiv 5\pmod {7} $
$3^6\equiv 1\pmod {7} $
. . . . .

Тогда одним из признаков делимости числа $ A $ на $ 7 $ может служить делимость на него выражения:
$ ... +a_6+5a_5+4a_4+6a_3+2a_2+3a_1+a_0 $

[Батороев]

Для проверки делимости числа на число, превышающее $10$, например на $13$, можно использовать степени ста:
$ 100^0\equiv 1\pmod {13} $
$ 100^1\equiv 9\pmod {13} $
$ 100^2\equiv 3\pmod {13} $
$ 100^3\equiv 1\pmod {13} $
$ . . . . . . . $

Тогда признаком делимости числа $ A $ на $13$ может служить делимость на него выражения:
$ ....+ (a_7a_6) + 3(a_5a_4)+9(a_3a_2)+(a_1a_0) $.

p.s. Это возможно потому, что разбивая любое число в десятичной системе по два разряда, мы тем самым "переводим" его в $100$-чную систему.

[незваный гость]

7, 11, 13:
$...a_9a_8a_7a_6a_5a_4a_3a_2a_1a_0 \equiv (a_2a_1a_0)-(a_5a_4a_3)+(a_8a_7a_6)-...$

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

Например, $...a_9a_8a_7a_6a_5a_4a_3a_2a_1a_0 \equiv (a_2a_1a_0)+(a_5a_4a_3)+(a_8a_7a_6)+...$ по модулям $27$ и $37$.