对素数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个(不同的)解.