Здравствуйте, bill1091989!
В том, что функция a
n mod d - периодическая (впрочем, это не гарантирует, что период начнётся с первого значения функции - как в случае, когда с определённого значения n все остатки равны нулю) можно убедиться из того, что
a
n+1 mod d = ((a
n mod d)[$183$]a) mod d
то есть остаток следующего члена показательной последовательности зависит только от остатка предыдущего от деления на тот же делитель. А число возможных остатков не может превышать делитель.
Составив по этому принципу таблицу значений 11
n mod 62 (пока они не начнут повторяться), находим, что
11
30 mod 62 = 1 = 11
0 mod 62
11
31 mod 62 = 11 = 11
1 mod 62
то есть период равен 30 (и имеет место при n=1 и даже n=0)
11
n mod 62 = 11
n mod 30 mod 62
Здесь также можно отметить, что остаток a
n mod d не может принимать значения, делящиеся на простые делители числа d, не являющиеся делителями числа a (что отражено в упомянутой в предыдущем ответе формуле Эйлера). Функция 11
n mod 62 действительно принимает все 30 возможных значений, удовлетворяющих этому условию (как мы далее убедимся, это не всегда так).
Итак,
Теперь нужно найти 11
35 mod 30
Легко убедиться, что 11
n mod 30 принимает всего 2 значения (что на сей раз в 4 раза меньше, чем то, что даёт нам формула Эйлера):
11
2k-1 mod 30 = 11
1 mod 30 = 11
11
2k mod 30 = 11
2 mod 30 = 1
или
11
n mod 30 = 11
n mod 2 mod 30
Таким образом находим ответ (воспользовавшись ранее составленной таблицей остатков 11
n mod 62)