一个简单的数论证明

设 g是mod p意义下的一个原根。

则 g^(p-1)=1 mod p

且对于 k=1,2...p-2: g^k不=1 mod p

接下来，当p不整除x时：

可设x=g^y mod p
原方程化为 by=y mod (p-1) (y=1,2...p-1)

即 (b-1)y=0 mod (p-1)
即 (b-1)/gcd(b-1,p-1) ·y=0 mod (p-1)/gcd(b-1,p-1)
即 y=0 mod (p-1)/gcd(b-1,p-1)
这个方程在y=1,2...p-1下恰有gcd(b-1,p-1)个解

所以x^b=x mod p 的解应该有gcd(b-1,p-1)+1个，gcd(b-1,p-1)个是指非零的

taijizhao：你真是GRD，CNM简单？简单自己做出来就行了，问什么？

taijizhao：你真是GRD，CNM简单？简单自己做出来就行了，问什么？

你的问题很有深度也很有难度，可惜我不会阿