|
设 g是mod p意义下的一个原根。则 g^(p-1)=1 mod p且对于 k=1,2...p-2: g^k不=1 mod p接下来，当p不整除x时：可设x=g^ymod 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... |
