如果 p 有一个原根 g的话，a 表示为 g^t 的形式。原方程变为 (g^s)^s ≡ g^t (mod p)，其中 s = k(p-1) + r

不知道有没有简单点的做法，用另外一个结论可以做出来
对任意整数a和正整数m，存在正整数r使m整除a^r+r
(在这个贴子有出得很好的一道题 )
由于a与n互素，总存在b≡a(mod n)且b与φ(n)互素
然后对于b和φ(φ(n))，设正整数r使得φ(φ(n))整除r+b^r
这样b^r* b^b^r≡1(mod φ(n))
b^(b^r* b^b^r)≡b≡a(mod n)，也就是(b^b^r)^(b^b^r)≡a(mod n)，取x=b^b^r就可以

当模是素数幂时的特殊情况, 是2017年北大金秋营的第3题, 搬运过来一种挺简便的解答, 过程中对模的幂次进行归纳
一开始模为素数的时候就是2楼讨论的情况, 这里用的是原根~(模2的原根是任意奇数)

补充一种完整的做法, 把模是素数幂时的结论加强, 然后对一般情况的结论加强归纳