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

Говорят, что если сумма цифер числа делится на 3 то и само число делится тоже на 3. А есть строгое доказательство сего феномена?

Конечно. Мы его даже в школе проходили.

Разумеется, в рамках средней школы элементарно. Достаточно воспользоваться представлением числа в виде a+10b+100c+1000d, где dbca - это цифры в десятичной записи числа. Так же и другие признаки делимости доказываются.

На примере делимости на 9.
Пусть dcba - цифры четырехзначного числа. Его значение 1000d+100c+10b+a. Сумма цифр d+c+b+a.
Разница чисел есть 999d+99c+9b=9 * (111d+11c+b).
Таким образом, если одно число (d+c+b+a) делится на 9, то сумма с другим числом, делящимся на 9, даст число, делящиеся на 9.
Отсюда и для 3: разница в числе и сумме цифр 3 * (333d+33c+3b).
Очевидно, разрядность числа роли не играет.

Девятка не имеет других делителей, кроме трех. Поэтому для других чисел этот признак не работает

ber-viking, спасибо. А то некоторые (не будем тыкать пальцем потому, что и так все знают, что это Базар и Муркенштейн) только умняки кидать умеют, а доказательства не знают.

ProstoTak
А Вы вопрос свой читали? "А есть строгое доказательство сего феномена?" Вот я и ответил - да, есть. Какие претензии?

Старая шутка про математиков, которую програмисты переделали под себя:

Путешественники на воздушном шаре заблудились и спустились вниз, чтобы узнать где они находятся. Спрашивают прохожего - "Где мы находимся?". Тот посмотрел на них внимательно, подумал и ответил:
- Вы находитесь в гондоле воздушного шара.
Далее диалог путешественников:
- Сразу видно, математик.
- Как ты догадался?
- Во-первых, он подумал, перед тем как ответить, во-вторых, его ответ абсолютно верен, а в-третьих, его ответ абсолютно бесполезен.

Дамы и господа!

Держите простейшее доказательство признака делимости целого числа на 3, 9 и многие другие числа.

Итак, представляем целое число как многочлен (скажем, Р (Х) с коэффициентами из совокупности однозначных чисел (цифр) от 0 до 9. Переменная (обозначенная Х, или ИКС) при вычислении многочлена принимает значение 10. Сумма цифр числа оказывается значением многочлена при ИКС равном 1 (легко проверить). Так как разность *ИКС_в_степени_ЭН - 1* делится на *ИКС - 1*, то и разница между Р(10) - Р(1) делится на 9.

Следствие первое: число делится на 9 тогда и только тогда, когда его сумма цифр обладает этим свойством.

Следствие второе: то же про делимость на 3.

Домашнее задание. Введите признаки делимости на 11 и на 27.

Не хочу думать про 11 и 27 но вот в восьмеричной системе получается что если сумма цифр числа делится на 7 то и само число делится на 7. Отсюда вывод. Чтобы проверить делится ли число на 7 нужно перевести его в восьмеричную систему, а дальше всё просто.

Подумайте лучше о том, что 1001 делится на 7. Танцуя от этой печки, можно понять, как вывести признак делимости на 7, не переходя в восьмеричную систему.

Кстати, 1001 - это произведение 7*11*13 - отсюда вывод, что остаток от деления числа А на 7 / 11/ 13 такой же, как остаток от деления (на то же самое) числа А, приведенного по модулю 1001.

А с делимостью на 27 или 37 Вам поможет факт, что 999 = 27*37.

Спокойной ночи - или с добрм утром!

"Подумайте лучше о том, что 1001 делится на 7."
Сами думайте. Не хочу я думать. Думаю только то что само думается. И вообще не люблю я подобных "задачек", как и шахматных задач, ибо на практике, в реальной жизни пользы от них почти нет по сравнению с опухшими мозгами.

Уточнение про 1001 - если к трехзначному числу слева или справа дописать тоже самое число, то получившееся шестизначное число делится на 7, 11, 13.

Я даже знаю, что получится, если разделить это шестизначное число сначала на 7, потом на 11, и затем на 13

Гипотеза признака делимости на 11: сумма цифр, стоящих на четных позициях, равна сумме цифр, стоящих на нечетных позициях.

Нет, разность этих сумм должна делиться на 11.
Например, 209.

Муркенштейн, поправляюсь: сумма "четных" цифр и сумма "нечетных" цмфр равны по модулю 11.
Все-таки равенство, а не разность

Если "равны по модулю", то варианты эквивалентны.

Доказательство, превращающее гипотезу в факт:
Пусть abcd - наше число, в котором сумма цифр на четных позициях a+c и сумма цифр на нечетных позициях b+d сравнимы по модулю 11, или как заметил Муркенштейн, a+c-b-d=11n, где n - целое. Построим число 1001a+99b+11c, которое делится на 11. Вычтем из него a+c-b-d, получим 1000a+100b+10c+d, которое делится на 11. Аналогично, показывается и для нечетного числа цифр, в частности для трех: (99a+11b)+(a+c-b)=100a+10b+c.
Для обобщения на число произвольной длины следует показать, что числа вида 10....01, где m - число нулей - четно, также делится на 11. В случае m=0 11=11 (mod 11). В остальных случах, число (90)91 и 11 являются сомножителями для 10..01, а вот это уже можно показать по индукции