Алгоритм Евклида

Подсказка 1

Сложно анализировать число только из единиц, т.к. сложно разобрать даже его делители...тогда было бы по хорошему его как-то преобразовать в более приятный вид. И подумаем над вопросом: "А откуда тут вообще 41? Почему не 42, например?"

Подсказка 2

Число, состоящее из единиц, можно записать как (10^n - 1)/9. А использовать 41 хочется только как простое число... Выходит, что (10^n - 1)/9 должно делиться на 41. Когда это возможно?

Подсказка 3

Когда 10^n - 1 делится на 41. Хмм, 41 простое... Какая известная теорема может помочь нам в нахождении хотя бы одного n, удовлетворяющему предыдущему предложению?

Подсказка 4

Малая теорема Ферма утверждает, что при n = 40 10^40 - 1 делится на 41. Теперь хочется как-то найти k из условия... а на что должно делиться n, чтобы 10^n - 1 делилось на 41? Мы не можем найти все такие случаи, но может попробовать найти хотя бы одного такое k и доказать, что утверждение работает в обе стороны.

Подсказка 5

Рассмотрим все такие d, что 10^d - 1 делится на 41 и выберем среди них наименьшее m. Докажем, что если n делится на m, то 10^n - 1 делится на 10^m - 1, а, значит, и на 41. Если это получится, то у нас найдено k, но условие "тогда и только тогда" пока не доказано. Теперь попробуем доказать, что если 10^n - 1 кратно 41, то n кратно m.

Подсказка 6

Мы взяли m наименьшим, т.к. обычно это помогает в поиске противоречий. Для того чтобы доказать утверждение из подсказки 5, попробуем найти НОД(10^n - 1, 10^m - 1).

Подсказка 7

В процессе поиска c помощью алгоритма Евклида можно заметить, что у нас в конце концов появится 10^(НОД(m, n)) - 1. Предположим, что n не делится на m, тогда НОД(n, m) < m. Осталось лишь найти противоречие с тем, что m - наименьшее взятое число из набора.