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

http://ru.wikipedia.org/wiki/%CF%F0%E8%E7%ED%E0%EA%E8_%E4%E5%EB%E8%EC%EE%F1%F2%E8

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

Число делится на 7 тогда и только тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7 (например, 364 делится на 7, так как 36 − (2 ∙ 4) = 28 делится на 7).

Либо использовать модификацию признака деления на 1001=10³+1, которое само делится на 7:
Для того, чтобы натуральное число делилось на 7 необходимо и достаточно, чтобы алгебраическая сумма чисел, образующих нечётные группы по три цифры (начиная с единиц) взятых со знаком «+» и чётных со знаком «-» делилась на семь (например, число 689255. Первая группа со знаком «+» (255), вторая со знаком «-» (689). Отсюда 255 + (-689) = −434. В свою очередь 434 : 7 = 62).

Ещё один признак — берём первую цифру, умножаем на 3, прибавляем следующую (здесь можно взять остаток от деления на 7 от получившегося числа). И далее — сначала: умножаем на 3, прибавляем следующую… Для 364: 3 * 3 + 6 = 15. Остаток — 1. Далее 1 * 3 + 4 = 7.

Рассмотрим цитату: «Число делится на 7 тогда и только тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7 (например, 364 делится на 7, так как 36 − (2 ∙ 4) = 28 делится на 7).»
Можно проще. Для пояснения, почему можно проще, приведу сначала доказательство признака из цитаты, из которого (такого доказательства) вытекает ответ, почему можно проще.

0. 7n=70m+a, где n=0,1,2,3,.. , m=0,1,2,.. , a=0,7,14,21,28,35,42,49,56,63.
Для приведённого в цитате признака выполняется:
1. 70m+0=10(7m+0)+0 -> 7m+0-2*0=7m – делится на 7
2. 70m+7=10(7m+0)+7 -> 7m+0-2*7=7m-14 – делится на 7
3. 70m+14=10(7m+1)+4 -> 7m+1-2*4=7m-7 – делится на 7
4. 70m+21=10(7m+2)+1 -> 7m+2-2*1=7m – делится на 7
5. 70m+28=10(7m+2)+8 -> 7m+2-2*8=7m-14 – делится на 7
6. 70m+35=10(7m+3)+5 -> 7m+3-2*5=7m-7 – делится на 7
7. 70m+42=10(7m+4)+2 -> 7m+4-2*2=7m – делится на 7
8. 70m+49=10(7m+4)+9 -> 7m+4-2*9=7m-14 – делится на 7
9. 70m+56=10(7m+5)+6 -> 7m+5-2*6=7m-7 – делится на 7
10. 70m+63=10(7m+6)+3 -> 7m+6-2*3=7m – делится на 7
Таким образом мы доказали признак из приведённой цитаты.
Но, используя теперь пункт 0, сформулируем другой признак:
Число делится на 7 тогда и только тогда, когда результат вычитания чисел 0,7,14,21,28,35,42,49,56,63, соответственно последней цифре, из этого числа делится на 7 .

Проше потому, что не надо «удвоенной последней цифры»!
А последнюю цифру ноль после вычитания разумеется откидываем перед следующим вычитанием.

Примеры:

1) 364-14=350 -> 35 делится на 7

2) 6913580247-7=6913580240 -> отбрасываем 0, и таким же образом далее
691358024-14
69135801-21
6913578-28
691355-35
69132-42
6909-49
686-56
63

http://ru.wikipedia.org/wiki/%CF%F0%E8%E7%ED%E0%EA%E8_%E4%E5%EB%E8%EC%EE%F1%F2%E8

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

Число делится на 13 тогда и только тогда, когда сумма числа, полученного отбрасыванием последней цифры и учётверённой последней цифры, делится на 13. Например 845 : 13 , так как 84+(4*5)=104:13 10+(4*4)= 26:13.

Аналогично доказывается и также формулируем признак:
Число делится на 13 тогда и только тогда, когда результат вычитания чисел 0,13,26,39,52,65,78,91,104,117, соответственно последней цифре, из этого числа делится на 13 .

Примеры:

1) 845-65=780 -> 78 делится на 13

2) 12839506173-13
1283950616-26
128395059-39
12839502-52
1283945-65
128388-78
12831-91
1274-104
117

http://ru.wikipedia.org/wiki/%CF%F0%E8%E7%ED%E0%EA%E8_%E4%E5%EB%E8%EC%EE%F1%F2%E8

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

Число делится на 17 тогда и только тогда, когда число его десятков, сложенное с увеличенным в 12 раз числом единиц, кратно 17 (например, 29053→2905+36=2941→294+12=306→30+72=102→10+24=34. Поскольку 34 делится на 17, то и 29053 делится на 17). Признак не всегда удобен, но имеет определенное значение в математике. Есть способ немного проще — число делится на 17 тогда и только тогда, когда разность между числом его десятков и упятерённым числом единиц кратна 17 (например, 32952→3295-10=3285→328-25=303→30-15=15; поскольку 15 не делится на 17, то и 32952 не делится на 17)..

Аналогично доказывается и также формулируем признак:
Число делится на 17 тогда и только тогда, когда результат вычитания чисел 0,17,34,51,68,85,102,119,136,153, соответственно последней цифре, из этого числа делится на 17 .

Примеры:

1) 29053-153=28900
289-119=170 -> 17 делится на 17

2) 32952-102
3285-85
32 - не делится на 17

3) 16790123457-17
1679012344-34
167901231-51
16790118-68
1679005-85
167892-102
16779-119
1666-136
153

http://ru.wikipedia.org/wiki/%CF%F0%E8%E7%ED%E0%EA%E8_%E4%E5%EB%E8%EC%EE%F1%F2%E8

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

Число делится на 19 тогда и только тогда, когда число его десятков, сложенное с удвоенным числом единиц, кратно 19 (например, 646 делится на 19, так как 64 + (6 × 2) = 76 делится на 19)..

Аналогично доказывается и также формулируем признак:
Число делится на 19 тогда и только тогда, когда результат вычитания чисел 0,19,38,57,76,95,114,133,152,171, соответственно последней цифре, из этого числа делится на 19 .

Примеры:

1) 646-76=570 -> 57 делится на 19

2) 1865432099-19
1876543208-38
187654317-57
18765426-76
1876535-95
187644-114
18753-133
1862-152
171

http://ru.wikipedia.org/wiki/%CF%F0%E8%E7%ED%E0%EA%E8_%E4%E5%EB%E8%EC%EE%F1%F2%E8

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

Число делится на 23 тогда и только тогда, когда число его сотен, сложенное с утроенным числом десятков и единиц, кратно 23 (например, 28842 делится на 23, так как 288 + (3 * 42) = 414; продолжаем: 4 + (3 * 14) = 46 — очевидно, делится на 23).

Аналогично доказывается и также формулируем признак:
Число делится на 23 тогда и только тогда, когда результат вычитания чисел 0,23,46,69,92,115,138,161,184,207, соответственно последней цифре, из этого числа делится на 23.

Примеры:

1) 28842-92
2875-115
276-46
23

2) 22716049383-23
2271604936-46
227160489-69
22716042-92
2271595-115
227148-138
22701-161
2254-184
207

Я бы с семеркой (да и вообще с любым мерсенновским числом) особенно бы не заморачивался.

Перевел бы исходное в восьмеричную (вариант - двоичную) систему счисления и посмотрел бы делимость суммы цифр.

Как в случае делимости на 3 или на 9 числа в 10-системе.

Да, с мерсенновскими можно проще. Эти признаки привёл кучей к одной схеме - ну семёрку туда до кучи. На семёрке показывать работу схемы проще.

Аналогично доказывается и также формулируем признаки:

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

Число делится на 29 тогда и только тогда, когда результат вычитания чисел 0,29,58,87,116,145,174,203,232,261, соответственно последней цифре, из этого числа делится на 29.

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

Число делится на 31 тогда и только тогда, когда результат вычитания чисел 0,31,62,93,124,155,186,217,248,279, соответственно последней цифре, из этого числа делится на 31.

Таким образом мы пришли к единой схеме признаков делимости для чисел 7,13,17,19,23,29,31. Для полноты не хватает признака делимости на 11 по данной схеме.

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

Число делится на 11 тогда и только тогда, когда результат вычитания чисел 0,11,22,33,44,55,66,77,88,99, соответственно последней цифре, из этого числа делится на 11.

Это нам нужно для обобщения признаков делимости по данной схеме для любого числа вида 30k+а, где а=1,7,11,13,17,19,23,29, k=0,1,2,3,... (при k=0, а=/=1)

Практическим в этой таблице является - практический способ получения любой строчки для любого делителя - в этой схеме. То есть - таблица эта бесконечна и отвечает требованиям схемы, сформулированной для признаков делимости 8-ми чисел: 7,11,13,17,19,23,29,31.

Пример (обозначен рыжей заливкой двух строчек в таблице): Чтобы получить строчку чиисел для делителя 43 , нужно к каждому числу в строчке с делителем 13 прибавить 30 умноженное на номер колонки (фиолетовая цифра).
Например, в колонке с фиолетовой цифрой 4 для строчки с делителем 13 стоит число 52. Чтобы получить число в колонке 4 для делителя 43 нужно прибавить 4*30.
Получится: 4*30+52=120+52=172, что и обнаруживаем в рыжей строчке в колонке 4 для делителя 43.

Это называется "взять в клещи схему"

Честно говоря, я не очень понял смысл новых признаков делимости.

Классика проверки делимости на 3 предствляет редукцию проверки делимости числа N к проверке делимости существенно меньшего числа К (сумма цифр)

K = O(log N)

c возможной последующей итерацией, если и К велико.

В предлагаемых признаках редукция практически не уменьшает величины тестируемого числа.

Точно так же не имеют смысла признаки делимости на 13, 17, 19, 23, приводимые в Википедии и других местах. Вот, например:

http://ru.wikipedia.org/wiki/%CF%F0%E8%E7%ED%E0%EA%E8_%E4%E5%EB%E8%EC%EE%F1%F2%E8

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

Число делится на 13 тогда и только тогда, когда сумма числа, полученного отбрасыванием последней цифры и учётверённой последней цифры, делится на 13. Например 845 : 13 , так как 84+(4*5)=104:13 10+(4*4)= 26:13.

Тоже никакой редукции, а последовательное уменьшение знаков числа. Если для чего-то нужны такие признаки, то можно обойтись схемкой по-проще.
Во-первых, проще по количеству операций. Во-вторых, проще для запоминания (одна формулировка для всех таких "слабых" признаков). Обобщение всех таких "слабых" признаков. И таблица со схемкой её получения - для удобства в использовании (или в запоминании).

Теперь упростим выбор числа. Как узнать, на какой делитель не нужно проверять число?
И как узнать, какие делители могут быть у числа?
Признаки делимости на 2,3,5,6,9,10 – хорошо работают. Поэтому выберем делители: 7,11,13,17,19,23,29,31,37,41,43… - это числа в прогрессиях 30k+a, где а=1, 7,11,13,17,19,23,29, k=0,1,2,… (а=/=1 при k=0)
Тогда получим 8 вариантов чисел в прогрессиях с этими делителями:

1) 30q+1 могут быть представлены только произведениями:
(30n+1)*(30m+1),
(30n+7)*(30m+13),
(30n+11)*(30m+11),
(30n+17)*(30m+23),
(30n+19)*(30m+19),
(30n+29)*(30m+29), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1, 7,11,17,19,29

2) 30q+7 могут быть представлены только произведениями:
(30n+1)*(30m+7),
(30n+11)*(30m+17),
(30n+13)*(30m+19),
(30n+23)*(30m+29), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1,11,13,23

3) 30q+11 могут быть представлены только произведениями:
(30n+1)*(30m+11),
(30n+7)*(30m+23),
(30n+13)*(30m+17),
(30n+19)*(30m+29), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1,7,13,19

4) 30q+13 могут быть представлены только произведениями:
(30n+1)*(30m+13),
(30n+7)*(30m+19),
(30n+11)*(30m+23),
(30n+17)*(30m+29), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1,7,11,17

5) 30q+17 могут быть представлены только произведениями:
(30n+1)*(30m+17),
(30n+7)*(30m+11),
(30n+13)*(30m+29),
(30n+19)*(30m+23), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1,7,13,19

6) 30q+19 могут быть представлены только произведениями:
(30n+1)*(30m+19),
(30n+7)*(30m+7),
(30n+11)*(30m+29),
(30n+13)*(30m+13),
(30n+17)*(30m+17),
(30n+23)*(30m+23), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1, 7,11,13,17,23

7) 30q+23 могут быть представлены только произведениями:
(30n+1)*(30m+23),
(30n+7)*(30m+29),
(30n+11)*(30m+13),
(30n+17)*(30m+19), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1,7,11,17

8 ) 30q+29 могут быть представлены только произведениями:
(30n+1)*(30m+29),
(30n+7)*(30m+17),
(30n+11)*(30m+19),
(30n+13)*(30m+23), где q=1,2,3,.., n,m=0,1,2,…
Таким образом, достаточно проверить делители 30k+a, где а=1,7,11,13

Наблюдение:
30k+1 - -- проверяется в 8-ми вариантах,,
30k+7 - -- проверяется в 7-ми вариантах,
30k+11 - -- проверяется в 6-ти вариантах,
30k+13 - -- проверяется в 5-ти вариантах,
30k+17 - -- проверяется в 4-х вариантах,
30k+19 - -- проверяется в 3-х вариантах,
30k+23 - -- проверяется в 2-х вариантах,
30k+29 - -- проверяется в 1-м варианте