Vtyjkyuk

Given a prime $p$ and a natural number $k$, such that $k$ is not divisible by $p - 1$, prove that $sum_i = 1^p - 1i^k equiv 0 pmod p$.

I split the proof into two cases: one where $k$ is odd and another where it is even.

The case where $k$ is odd can be proven as follows:

$$sum_i = 1^p - 1i^k equiv sum_i = 1^fracp - 12i^k + sum_i = 1^fracp - 12(-i)^k pmod p$$

Since $k$ is odd each $(-i)^k = -i^k$, and will cancel with the positive $i$ leaving a zero. Therefore,

$$sum_i = 1^p - 1i^k equiv 0 pmod p text if $k$ is odd. $$

I approached the case where $k$ is even in a similar fashion.

$$sum_i = 1^p - 1i^k equiv sum_i = 1^fracp - 12i^k + sum_i = 1^fracp - 12(-i)^k equiv 2(sum_i = 1^fracp - 12i^k) space pmod p$$

Since $p$ is prime, we just need to prove that $displaystylesum_i = 1^fracp - 12i^k equiv 0 pmod p$.

I was stumped after this, so I considered a counterexample, one where $k$ is divisible by $p - 1$. In that I considered a case where $p = 5, k = 8$:

$$1^8 + 2^8 + 3^8 + 4^8 equiv 1 + 1 + 1 + 1 space pmod p$$

This and a few other cases led to the conjecture that all the numbers below $p$ have a mod cycle $(mod space p)$ that is divisible by $p - 1$. I tested it with $p = 7$.

$2: 2, 4, colorred1$

$3: 3, 2, 6, 4, 5, colorred1$

$4: 4, 2, colorred1$

$5: 5, 4, 6, 2, 3, colorred1$

After this I was stuck. I couldn't see how this would help me solve the problem. And, more importantly, I couldn't prove my conjecture.

HINT:

As $i,1le ile p-1$ forms Reduced Residue System $pmod p,$

and so does $g^r,$ for $0le rle p-2$ where $g$ is a primitive root of $p$

$$textSo, sum_1le ile p-1i^kequivsum_0le rle p-2(g^r)^kpmod p$$

$$textNow, sum_0le rle p-2(g^r)^k=frac(g^k)^p-1-1g^k-1=frac(g^p-1)^k-1g^k-1$$

Using Fermat's Little Theorem, $g^p-1equiv1pmod pimplies (g^p-1)^kequiv1pmod piff (g^p-1)^k-1equiv0pmod p$

As $g$ is a primitive root of $p,textord_pg=p-1implies g^knotequiv1pmod p$ as $k$ is not divisible by $p-1$

$implies (g^k-1,p)=1implies frac(g^p-1)^k-1g^k-1equiv0pmod p$

$implies sum_1le ile p-1i^kequivsum_0le rle p-2(g^r)^kequiv frac(g^p-1)^k-1g^k-1equiv0pmod p$

Let $b$ be any number relatively prime to $p$. Recall that the numbers $b, 2b, 3b, 4b, dots, (p-1)b$ are a reduced residue class modulo $p$. This means that $b,2b,3b,dots, (p-1)b$ travel, modulo $p$, through $1,2,3,dots, p-1$ in some order.

It follows that
$$b^k+(2b)^k+(3b)^k+cdots +((p-1)b)^k equiv 1^k+2^k+3^k +cdots +(p-1)^kpmodptag1$$
But $(ib)^k=b^ki^k$, so we can rewrite (1) as
$$(b^k-1)left(1^k+2^k+3^k+cdots +(p-1)^kright)equiv 0pmodp.tag2$$

Let $b$ have order $p-1$ modulo $p$. So we are letting $b$ be a primitive root of $p$. Since $p-1$ does not divide $k$, we have $b^k notequiv 1pmodp$. Then it follows from (2) that $1^k+2^k+3^k+cdots +(p-1)^k equiv 0pmodp$.

All nonzero numbers less than p are roots of $x^p-1=1$ (mod p). Thus, all the elementary symmetric polynomials in these number of order less than p-1 are zero (mod p), so any symmetric polynomial in these numbers of order less than p-1 must be zero (mod p).