|
设 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个，g... |
