Singapore Mathematical Olympiad (SMO)

All congruences are taken modulo $p$. We count pairs $(a, b)$ taken modulo $p$ where $a \neq 0$ and the equation $x^n + ax \equiv b$ has a solution in $x$. Then $\sum_{a=1}^{p-1} |S_a|$ is the total number of such pairs.

First, consider all pairs $(a, b)$ where $a \neq 0$. Defined the relation $(a, b) \sim (a', b')$ if there exists $k \neq 0$ such that $a \equiv a'k^{n-1}$ and $b \equiv b'k^n$. It follows that if $(a, b) \sim (a', b')$ and $(a', b') \sim (a'', b'')$, then $(a, b) \sim (a'', b'')$. Also if $(a, b) \sim (a', b')$ then $(a', b') \sim (a, b)$. Hence this relation partitions our pairs into subsets, where each subset consists of pairs that are all related to each other. Let A be such a subset and $(a, b) \in A$. Then all other pairs may be described as $(ak^{n-1}, bk^n)$ where $x^n+ak^{n-1}x \equiv bk^n$ has a solution. But since $x^n+ax \equiv b$ has a solution, say $x_0$, one may check that $kx_0$ is a solution to $x^n+ak^{n-1}x \equiv bk^n$ for each non-zero $k$. Thus the pair $(ak^{n-1}, bk^n) \in A$. This gives us exactly $p-1$ distinct pairs in A since if $a, b \neq 0$,
$$ai^{n-1} \equiv aj^{n-1}, bi^n \equiv bj^n \Rightarrow i^{n-1} \equiv j^{n-1}, in \equiv j^n \Rightarrow i \equiv j.$$

Now when $b \equiv 0$, the equation $x^n + ax \equiv 0$ has a solution for all $a$. This gives us an additional $p-1$ pairs $(a, 0)$ as we want $a \neq 0$. Adding the sizes of the subsets up, we conclude that $\sum_{a=1}^{p-1} |S_a|$ is divisible by $p-1$ as desired.