Question

Как найти остаток деления 5^48 на 6
как найти остаток деления 3^258 на 13


только не просто ответ, а хотя бы примерный алгоритм как все это находится

Answer 1

3 mod 13 = 3           первая степень
9 mod 13 = 9           вторая степень
27 mod 13 = 1         третья степень
81 mod 13 = 3         четвертая степень остаток как у первой степени
243 mod 13 = 9        пятая степень остаток как у второй степени
и так далее

у 258 степени остаток будет как у третьей, то есть 1