Задача на делимость, число из одних единиц.

[gaz_v_pol]

Число из одних единиц делится на 2017. Докажите, что оно также делится и на 9.

Задача выглядела бы очень естественной, если бы 2017 делилось на 9. Но 2017 не делится на 9. А утверждение все равно верно!

Если кто-то решит, мне было бы интересно почитать, напишите в комментарии, пожалуйста.

Comments

[a_shen]

111... : k <=> 10^s =1 mod 9k
ord 10 modulo 2017*9 -> wolframalpha -> 2016 (можно просто вычислять ord 10 modulo 2017, так как по модулю 9 всё равно единица)
ord 10 modulo 81 -> 9.

2016 делится на 9

[russhatter]

"ord A modulo B" - как это читать в человеческой нотации?
Я не понимаю, что означает "просто вычислять ord 10 modulo 2017" - вроде бы 10 и есть, и что тут можно вычислять?...

[a_shen]

это обозначение, которое можно использовать, задавая вопросы системе wolfram alpha, поэтому я так написал - а имеется в виду порядок элемента 10 в мультипликативной группе вычетов по (простому) модулю 2017, и он равен 2016, т.е. 10 - одна из образующих этой группы. Соответственно, единица по модулю 2017 будет повторяться с периодом 2016, равно как и делимость на 2017*9

[russhatter]

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

[potok_mislei]

1) Находим ряд остатков по признаку Паскаля из википедии.
2) Обнаруживаем, что по условию задачи все ai оттуда же равны 1. А значит можно просто вычислить сумму ряда остатков до нужного знака.
3) Вычисляем суммы ряда остатков для каждого количества единиц и проверяем делятся ли они на 2017.
4) Видим что делятся только 2016-ое. Получается что число из 2016 единиц делится на 2017, а значит и все остальные соответствующие.
5) Проверяем делится ли число из 2016 единиц на 9, по признаку делимости на 9, по которому сумма цифр должна делиться на 9.
6) В итоге нашли: все числа из единиц, которые делятся на 2017 и доказали, что они делятся на 9. Радуемся, что что-то смогли доказать. ))

А вот если бы 2017 делилось на 9, то это была бы очень странная задача.

[m_strazhnik]

Лень считать. Тупо делим в столбик число из единиц на 2017, пока остаток не станет равен нулю. Если утверждение задачи истинно, то число единиц будет кратно 9.

[m_strazhnik]

Правильно ленился. На 2017 делится число из 2016 единиц. На паскале написал программку деления в столбик.
Поскольку сумма цифр (2016) делится на 9, то и любое число из 2016*n единиц (и только оно) будет делиться на 2017.