Number theory proof mod p

For a given prime $p$ and integer $k$, $k∈<1, p-1>$ $S(k)$ is defined as a sum of remainders of $k, k^2, k^3, ..., k^{p-1}$ when divided by $p$. Prove that $S(k)=\frac{1}{2}p(p-1)$ is true for an odd number of different k.

I managed to prove that $S(p-1)=\frac{1}{2}p(p-1)$ but can't see how to do it further.

(Fill in the gaps as needed. If you're stuck, show your work and explain what stumps you.)

Hint: Prove that $S(k) = \frac{1}{2} p (p-1)$ iff there exists an $a$ such that $ k^a \equiv -1 \pmod{p}$.

Corollary: Hence, if $p -1 = 2^m \times n, $ where $n$ is odd, then the number of solutions is $ (2^m-1) \times n $, which is odd.

Proof of hint without using primitive elements.

If there exists $ k^ a \equiv -1 \pmod{p}$:
(Proof by algebraic manipulation) Show that $$ 2 \sum_{i=1}^{p-1} ( k^i \pmod{p}) = \sum_{i=1}^{p-1} (k^i + k^{i+a} \pmod{p} ) = \sum_{j=1}^{p-1} p = (p-1)p. $$
Hence $ \sum_{i=1}^{p-1} (k^i \pmod{p}) = \frac{p-1}{2} \times p$.

If no such $a$ exists, then consider $ v = ord_p (k)$.
(Proof by contradiction) Show that $ v$ is odd, and a factor of $ p-1$.
(Proof by algebraic manipulation) Show that $$ \sum_{i=1}^{p-1} ( k^i \pmod{p} = \sum_{j=0}^{\frac{p-1}{v}-1} \sum_{i=1}^v (k^{jv + i} \pmod{p} = \frac{p-1}{v} \times \sum_{i=1}^v (x^i \pmod{p}).$$
Observe that if $ p-1 = 2^m \times n$ with $n$ odd, then $ 2^m \mid \frac{p-1}{v} \mid \sum_{i=1}^{p-1} (k^i \pmod{p})$, but $ 2^m \not \mid \frac{1}{2} (p-1)p$, so these 2 values can never be equal.

Hint using primitive elements. This was originally the easier way to approach. However, now that I've written out the steps which could be followed via algebraic manipulation, you should just review the above.

Consider a primitive element $g$.
Let $ k = g^b$.
Let $ p-1 = 2^m \times n$, where $n$ is odd.
Then $k$ satisfies the conditions iff $ 2^m \not \mid b$.

If $2^m \not \mid b$, then there exists $a$ such that $ ba = \frac{p-1}{2} \times o$, where $o$ is odd. This $a$ satisfies $k^a \equiv -1 \pmod{p}$, and the above pairing argument works.

If $ 2^m \mid b$, show that $2^m \mid S(k)$ while $ 2^m \not \mid \frac{1}{2} p (p-1)$, in a similar manner to the above. Hence these terms are not equal.

The description of the solution set as powers of $g$ that were not multiples of $2^m$, felt hard to motivate directly. (E.g. how can we tell that if $g^b$ doesn't work, then neither does $g^{2b}, g^{3b}, \ldots$?)

Whereas finding the $k^a \equiv -1 \pmod{p}$ condition was quite direct especially after considering small cases. Hence, that was my initial hint.

If $S(n)=\tfrac12p(p-1)$ then also $S(n^{-1})=\tfrac12p(p-1)$, where $n^{-1}$ denotes the inverse of $n$ mod $p$. This shows that solutions come in pairs, except those for which $n=n^{-1}$. Of course $n=n^{-1}$ holds only for $n=\pm1$, and a quick check shows that $S(1)=p-1$ and $S(-1)=\tfrac12p(p-1)$.