, 2014

Let $S$ be the set of all sequences $(b_1, b_2, \dots, b_p)$ of numbers from the set $\{0, 1, 2, \dots, p-1\}$ such that $b_1 + b_2 + \dots + b_p$ is not divisible by $p$. We show that $|S| = p^p - p^{p-1}$. For let $b_1, b_2, \dots, b_{p-1}$ be an arbitrary sequence of numbers chosen from $\{0, 1, 2, \dots, p-1\}$. There are exactly $p-1$ choices for $b_p$ such that $b_1 + b_2 + \dots + b_{p-1} + b_p \not\equiv 0 \pmod{p}$, and therefore $|S| = p^{p-1}(p-1) = p^p - p^{p-1}$.

Now it will be shown that the number of good sequences in $S$ is $\frac{1}{p}|S|$. For a sequence $B = (b_1, b_2, \dots, b_p)$ in $S$, define the sequence $B_k = (a_1, a_2, \dots, a_p)$ by
$$a_i = b_i - b_1 + k \bmod p$$
for $1 \le i \le p$. Now note that $B$ in $S$ implies that
$$a_1 + a_2 + \dots + a_p \equiv (b_1 + b_2 + \dots + b_p) - pb_1 + pk \equiv (b_1 + b_2 + \dots + b_p) \not\equiv 0 \pmod{p}$$
and therefore $B_k$ is in $S$ for all non-negative $k$. Now note that $B_k$ has first element $k$ for all $0 \le k \le p-1$ and therefore the sequences $B_0, B_1, \dots, B_{p-1}$ are distinct.

Now define the cycle of $B$ as the set $\{B_0, B_1, \dots, B_{p-1}\}$. Note that $B$ is in its own cycle since $B = B_k$ where $k = b_1$. Now note that since every sequence in $S$ is in exactly one cycle, $S$ is the disjoint union of cycles.
Now it will be shown that exactly one sequence per cycle is good. Consider an arbitrary cycle $B_0, B_1, \dots, B_{p-1}$, and let $B_0 = (b_1, b_2, \dots, b_p)$ where $b_0 = 0$, and note that $B_k = (b_1 + k, b_2 + k, \dots, b_p + k)$ mod $p$. Let $u = b_1 + b_2 + \dots + b_p$, and $v = b_1b_2 + b_2b_3 + \dots + b_pb_1$ and note that $(b_1 + k)(b_2 + k) + (b_2 + k)(b_3 + k) + \dots + (b_p + k)(b_1 + k) = u + 2kv \pmod p$ for all $0 \le k \le p-1$. Since $2v$ is not divisible by $p$, there is exactly one value of $k$ with $0 \le k \le p-1$ such that $p$ divides $u + 2kv$ and it is exactly for this value of $k$ that $B_k$ is good. This shows that exactly one sequence per cycle is good and therefore that the number of good sequences in $S$ is $\frac{1}{p}|S|$, which is $p^{p-1} - p^{p-2}$.