Singapore Mathematical Olympiad (SMO)

All congruences are taken modulo $p$. We count pairs $(a,b)$ taken modulo $p$ where $a\ne 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\ne 0$. Defined the relation $(a,b)\sim (a^{\prime },b^{\prime })$ if there exists $k\ne 0$ such that $a\equiv a^{\prime }{k}^{n-1}$ and $b\equiv b^{\prime }{k}^n$. It follows that if $(a,b)\sim (a^{\prime },b^{\prime })$ and $(a^{\prime },b^{\prime })\sim (a^{\prime \prime },b^{\prime \prime })$, then $(a,b)\sim (a^{\prime \prime },b^{\prime \prime })$. Also if $(a,b)\sim (a^{\prime },b^{\prime })$ then $(a^{\prime },b^{\prime })\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 $(a{k}^{n-1},b{k}^n)$ where $x^n+a{k}^{n-1}x\equiv b{k}^n$ has a solution. But since $x^n+ax\equiv b$ has a solution, say $x_0$, one may check that $k{x}_0$ is a solution to $x^n+a{k}^{n-1}x\equiv b{k}^n$ for each non-zero $k$. Thus the pair $(a{k}^{n-1},b{k}^n)\in A$. This gives us exactly $p-1$ distinct pairs in A since if $a,b\ne 0$, $$a{i}^{n-1}\equiv a{j}^{n-1},b{i}^n\equiv b{j}^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\ne 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.