设n是正整数,p是素数,(n,p−1）=k,证明同余方程x^n≡1(mod p)有k个解.

对素数p,存在原根g。即g^i ≡ 1 (mod p),当且仅当i是p-1的倍数。由此,对i = 0,1,2,。。。,p-2,g^i (mod p)两两不同余,即mod p恰好取遍1,2,。。。,p-1。显然,x = 0不是x^n ≡ 1 (mod p )的解。对x = 1,2,。。。,p-1,存在i = 0,1,2,。。。,p-2,使x ≡ g^i (mod p)。于是x^n ≡ g^(ni) (mod p)。x^n ≡ 1 (mod p)当且仅当g^(ni) ≡ 1 (mod p),当且仅当ni是p-1的倍数,当且仅当i是(p-1)/k的倍数(这里用到k = (n,p-1))。而在0,1,2,。。。,p-2中,(p-1)/k的倍数恰有k个,即0,(p-1)/k,2(p-1)/k,。。。,(k-1)(p-1)/k。这就对应x^n ≡ 1 (mod p)的k个(不同的)解。