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

[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]

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

[dima_i]

Да. А скажи, знаешь ли ты способ убедиться в том, что ord 10 modulo 2017 == 2016, вручную, без использования электроники? ( или, если я правильно понимаю, это как раз одна из BQP задач?)

[akhrabrov]

Проверка того, что корень первообразный не очень сложна: 2016=25327, поэтому нужно лишь убедиться, что 102016/2, 102016/3 и 102016/7 не дают единицы по модулю 2017. Т.е. посчитать три конкретных остатка, сложность тут логарифмическая.

[dima_i]

Да, действительно. Спасибо.

[a_shen]

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

[papa_lyosha]

Достаточно 102016/3 не даёт 1, чтобы убедиться, что порядок 10 делится на 9.

[gaz_v_pol]

А почему достаточно?