Let p be a prime and k be a positive integer, not divisible by (p - 1).
Show that
1^k +2^k + 3^k + . . . + (p - 1)^k
is divisible by p.
Please avoid using advance number theory tools if this can be proved by elementary means.
top of page
bottom of page
Note that every prime has a primitive root such that there is an x and considering the set [x^1, x^2, … x^(p-1)] modulo p is equivalent to [1,2…(p-1)] modulo p.
So 1^k + 2^k +…(p-1)^k = x^k + x^(2k) + x^(3k)… x^((p-1)k) mod p
Now
x^k + x^(2k) + x^(3k)… x^((p-1)k) mod p
= (x^k)(1-x^((p-1)k))/(1-(x^k)) mod p; (Summing the geometric series and noting that (1-(x^k)) ≠ 0 mod p for k ≠ p -1)
Note that (1-x^((p-1)k)) = 0 mod p by fermat's little theorem.
So this is
(x^k)(0)/(1-(x^k)) mod p
= 0 mod p
As required.
-The key idea here is to recognize the existence of the primitive root (read a number theory book for existence)
-Use geometric series formula
-Apply Fermat's little theorem