Equal number of $n$th roots of unity within character values $f_1(a), \dots, f_m(a)$. (Apostol exercise 6.12 Intro to ANT) This problem is taken from Exercise 6.12 from Apostol's "Introduction to Analytic Number Theory".
Verbatim, the problem states

Let $f_1, \dots, f_m$ be the characters of a finite group $G$ of order $m$, and let $a$ be an element of $G$ of order $n$. Theorem 6.7 shows that each number $f_r(a)$ is an $n$th root of unity. Prove that every $n$th root of unity occurs equally often among the numbers $f_1(a), f_2(a), \dots, f_m(a)$.

Theorem 6.7 above simply states that every $f_r(a)$ is an $n$th root of unity.
The case of $n = 1$ is trivial, I'll assume $n > 1$ throughout the rest of this question. Apostol gives as a hint that evaluation of the sum
$$\sum_{r=1}^m \sum_{k=1}^n f_r(a^k) e^{-2\pi ik/n}$$
in "two different ways" shows how many $f_r(a) = e^{2\pi i/n}$. The sum above evaluates to $m$, since
$$S = \sum_{r=1}^m \sum_{k=1}^n f_r(a^k) e^{-2\pi ik/n} = \sum_{k=1}^n e^{-2\pi ik/n} \sum_{r=1}^m f_r(a^k), $$
and, by Theorem 6.13,
$$\sum_{r=1}^m f_r(a^k) = \begin{cases}
m & k = n \\
0 & \text{otherwise}.
\end{cases}$$
Therefore, $S$ vanishes for $k = 1, 2, \dots, n-1$, which implies $S = me^{-2\pi i} = m$.
The "second way" to evaluate $S$ is to notice that the sum
$$\sum_{k=1}^n [f_r(a)e^{-2\pi i/n}]^k$$
equals $n$ only when $f_r(a) = e^{2\pi i/n}$, otherwise, $f_r(a)e^{-2\pi i/n}$ is some non-one $n$th root of unity $\omega$ and the sum above equals
$$\sum_{k=1}^n \omega^k = 0$$
by properties of roots of unity. Thus, since $S = m$, if $\alpha$ represents the number of $f_r(a) = e^{2\pi i/n}$, then $m = \alpha n$, or $\alpha  =m/n$.
However, what would lead one to consider the sum $S$ in the first place? Where did it come from? It seems almost as if $S$ appeared out of "thin air". Is there another way to prove this statement without the evaluation of $S$?
Thanks in advance!
 A: Here is a proof, using only facts from Chapter 6 of Apostol, and using its notation. Let $a\in G$ have order $n$.
The characters form a group under multiplication. Therefore, if $f_1,\dots,f_r$ are the characters, then multiplying by $f_i$ simply permutes the characters. In particular, for any fixed $a\in G$, it permutes the values in the set
$$X=\{f_j(a)\mid 1\leq j\leq r\}.$$
This is the set we wish to prove is simply each $n$th root of unity appearing $r/n$ times. Suppose that $f_i(a)$ is a primitive $n$th root of unity. Then multiplying by $f_i$ has the effect of multiplying all elements in the set $X$ by $f_i(a)$, a primitive $n$th root of unity. The only way such a multiplication can preserve $X$ is if $X$ is uniform.
Thus we must check that there is such an element $f_i$. If not, then all of the $f_j(a)$ (since it is closed under multiplication as the $f_i$ form a group) must be all $m$th roots of unity for some $m$ strictly dividing $n$ (as they are already $n$th roots of unity).
But now, $a^{n/m}$ is a non-trivial element, and $f_i(a^{n/m})=1$ for all $1\leq i\leq r$. By Theorem 6.10 from Apostol (column orthogonality relation), $a^{n/m}$ is the identity, a contradiction.
A: I think I found a means to build up to the sum Apostol hints at without changing the method of proof wildly or without mentioning techniques beyond that of a pre calculus level.
Consider the sequence $g_r = f_r(a)e^{-2\pi i /n}$. Note that $g_r = 1$ only when $f_r(a) = e^{2\pi i /n}$. Otherwise, since $f_r(a)$ is some $n$th root of unity, $g_r$ would be some root of unity not equal to $1$. In a way, $g_r$ represents a sort of indicator function. However, we cannot really distinguish between the roots of unity (that is, we can't really do much with only $g_r$, I think).
In order to make $g_r$ more applicable to the problem, sum over its $n$ powers:
$$G_r = \sum_{k=1}^n g_r^k$$
in order to utilize the property that
$$\sum_{k=1}^n \omega^k = \begin{cases}
n & \omega = 1 \\
0 & \omega \neq 1,
\end{cases}$$
where $\omega$ is an $n$th root of unity.
The newly defined $G_r$ is more revealing in terms of the value of $g_r$, and since $g_r$ is an $n$th root of unity,
$$G_r = \begin{cases}
n & g_r = 1 \\
0 & g_r \neq 1,
\end{cases}$$
from which it can be ascertained that
$$G_r = \begin{cases}
n & f_r(a) = e^{2\pi i/n} \\
0 & f_r(a) \neq e^{2\pi i/n}.
\end{cases}$$
Summing $G_r$ over $1 \leq r \leq m$ yields that
$$\sum_{r=1}^m G_r = n\alpha,$$
where $\alpha$ is the number of times $f_r(a) = e^{2\pi i /n}$. In fact, the sum above is $S$ as defined in my post.
I personally think that this is intuitive enough without more intense jargon and concepts that I haven't learned yet. However, I think such a line of reasoning may have been the initial intuition of the final sum (although I personally think the sum Apostol gives may have been too revealing, I wanna have fun struggling!!)
To complete the proof, generalize $g_r(t) = f_r(a)e^{-2\pi i t/n}$ and define everything that follows similarly to show that the number of $f_r(a) = e^{2\pi i t/n}$ equals $\alpha(t)$, where
$$S(t) = m = n\alpha(t).$$
