取p的一个原根g.
x^k=g^(kindx)(modp)
当x遍历p的简化剩余系时,indx遍历p-1的完全剩余系.所以,
∑{x=1->p-1}x^k
=∑{n=0->p-2}g^(kn)
={g^[(p-1)k]-1}/(g^k-1)(modp)
因为g^[(p-1)k]-1=0(modp)并且g^k-1≠0(modp)(这是因为1≤k≤p-2)
所以{g^[(p-1)k]-1}/(g^k-1)=0(modp)
即原式得证.