Number theory proof mod p
(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.