题目

证明 x^b = x mod p 的解的个数是 gcd(b-1,p-1).
如题

提问时间：2021-03-21

答案

设 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)个是指非零的