9. Let $p$ be an odd prime. Determine the number of tuples $\left(a_{1}, a_{2}, \ldots, a_{p}\right)$ of natural numbers with the following properties:
1) $1 \leq a_{i} \leq p$ for all $i=1, \ldots, p$.
2) $a_{1}+a_{2}+\cdots+a_{p}$ is not divisible by $p$.
3) $a_{1} a_{2}+a_{2} a_{3}+\ldots a_{p-1} a_{p}+a_{p} a_{1}$ is divisible by $p$.
Solution: For a tuple $t=\left(a_{1}, \ldots, a_{p}\right)$, in 1) we define $S(t)=a_{1}+\cdots+a_{p}$ and $P(t)=a_{1} a_{2}+a_{2} a_{3}+\cdots+a_{p} a_{1}$. We note

$$
\mid\left\{t \mid t \text { satisfies } 1 \text { and } 2 \mid=p^{p-1}(p-1)\right.
$$

since we can freely choose the first $p-1$ entries and then exactly one value for the last entry is forbidden.

We further define for $0 \leq k \leq p-1$ a new tuple $t_{k}=\left(a_{1}+k, a_{2}+k, \ldots, a_{p}+k\right)$, where if any entry is greater than $p$, we replace it with its remainder upon division by $p$.

It holds that $S\left(t_{k}\right) \equiv S(t)(\bmod p)$ and $P\left(t_{k}\right) \equiv P(t)+2 k S(t)(\bmod n)$. Let $t$ be a tuple that satisfies 1 and 2. Then $2 k S(t)$ for $0 \leq k \leq p-1$ runs through each residue class modulo $p$ exactly once, and thus exactly one of the tuples $t_{0}, t_{1}, \ldots, t_{p-1}$ additionally satisfies 3. Therefore, the desired number is

$$
\mid\{t \mid t \text { satisfies } 1 \text { and } 2\} \left\lvert\, p=\frac{p^{p-1}(p-1)}{p}=p^{p-2}(p-1)\right.
$$