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.

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