Здравствуйте, bill1091989!

Я бы решал задачу так.

По формуле Эйлера

Тогда по теореме Эйлера


Аналогично



С учётом свойств сравнений получим







Значит, остаток от деления числа 11^{11^35} на 62 равен 55.

С уважением.

Здравствуйте, bill1091989!
В том, что функция aⁿ mod d - периодическая (впрочем, это не гарантирует, что период начнётся с первого значения функции - как в случае, когда с определённого значения n все остатки равны нулю) можно убедиться из того, что
aⁿ⁺¹ mod d = ((aⁿ mod d)[$183$]a) mod d
то есть остаток следующего члена показательной последовательности зависит только от остатка предыдущего от деления на тот же делитель. А число возможных остатков не может превышать делитель.

Составив по этому принципу таблицу значений 11ⁿ mod 62 (пока они не начнут повторяться), находим, что
11³⁰ mod 62 = 1 = 11⁰ mod 62
11³¹ mod 62 = 11 = 11¹ mod 62
то есть период равен 30 (и имеет место при n=1 и даже n=0)
11ⁿ mod 62 = 11^{n mod 30} mod 62

Здесь также можно отметить, что остаток aⁿ mod d не может принимать значения, делящиеся на простые делители числа d, не являющиеся делителями числа a (что отражено в упомянутой в предыдущем ответе формуле Эйлера). Функция 11ⁿ mod 62 действительно принимает все 30 возможных значений, удовлетворяющих этому условию (как мы далее убедимся, это не всегда так).

Итак,


Теперь нужно найти 11³⁵ mod 30
Легко убедиться, что 11ⁿ mod 30 принимает всего 2 значения (что на сей раз в 4 раза меньше, чем то, что даёт нам формула Эйлера):
11^2k-1 mod 30 = 11¹ mod 30 = 11
11^2k mod 30 = 11² mod 30 = 1
или
11ⁿ mod 30 = 11^{n mod 2} mod 30

Таким образом находим ответ (воспользовавшись ранее составленной таблицей остатков 11ⁿ mod 62)