问题来源：https://tioj.ck.tp.edu.tw/problems/1324
问题：
底数与要除的数不互质时 a^k (mod n) = a^(k+phi(n)) (mod n)还成立吗？
还是我搞错解题方向了？
已有的想法：
用欧拉定理化简掉超大的指数
我的程式码（只拿了32分）
https://ideone.com/gYneXP

反例: a=2, k=0, n=4

k > 0 应该就对了, 所以你不能直接 % phi(n)

k=1 还是错啊，2^1 不同余于 2^(1+2) mod 4

看来我的方法不可行请问要如何解决不互质的情况呢？

总觉得这题是要用程式的方式找出循环节，不需要特别针对互质&不互质作讨论像 4^k = 4 (mod 6) for all k，这个事实不跑跑看怎么会知道呢？

谢谢alan大 我再想看看

或许你可以查查扩展欧拉定理，虽然这应该不是正确的学术名词，不过满多中国选手会用的w