30. [17] Find the number of unordered pairs $\{a, b\}$, where $a, b \in\{0,1,2, \ldots, 108\}$ such that 109 divides $a^{3}+b^{3}-a b$.
Answer: 54
We start with the equation
$$
a^{3}+b^{3} \equiv a b \quad(\bmod 109) .
$$

If either $a$ or $b$ are 0 , then we get $a^{3} \equiv 0$, implying that both are 0 . Thus, $\{0,0\}$ is a pair. For the rest of the problem, let's assume that neither $a$ nor $b$ are 0 . Multiplying both sides by $a^{-1} b^{-2}$ yields
$$
\left(a b^{-1}\right)^{2}+a^{-1} b \equiv b^{-1}
$$
from which we make the substitution
$$
\begin{aligned}
a & =x y^{-1} \\
b & =y^{-1}
\end{aligned}
$$
to get the equation
$$
y \equiv x^{2}+x^{-1} .
$$

Plugging this value back into $(a, b)$, we get that all solutions must be of the form
$$
(a, b)=\left(\left(x+x^{-2}\right)^{-1},\left(x^{2}+x^{-1}\right)^{-1}\right),
$$
where $1 \leq x \leq 108$. It now suffices to find all nonzero unordered pairs $\{m, n\}$ of the form $\left\{x+x^{-2}, x^{2}+\right.$ $\left.x^{-1}\right\}$, where $1 \leq x \leq 108$. There are four values of $x$ for which $x+x^{-2} \equiv x^{2}+x^{-1}$, and of these values, three of them give $x+x^{-2} \equiv 0$. This is because we can re-arrange the equation at hand to get
$$
x^{4}-x^{3}+x-1 \equiv 0,
$$
which factors into
$$
(x-1)\left(x^{3}+1\right) \equiv 0 \text {. }
$$

If $x=1$, then $\{m, n\}=\{2,2\}$, and if $x^{3}+1 \equiv 0$ (which has three solutions: 46,64 and 108), then
$$
\{m, n\}=\left\{x^{-1}\left(x^{3}+1\right), x^{-2}\left(x^{3}+1\right)\right\}=\{0,0\} .
$$

Therefore, we keep $x=1$ and discard $x=46,64,108$. Of the remaining 104 values of $x, m \neq n$, and neither are 0 . We have to worry about collisions between distinct values of $x$. There are two ways a collision can occur: if there exists $x \neq y$ such that
$$
\left(x+x^{-2}, x^{2}+x^{-1}\right)=\left(y+y^{-2}, y^{2}+y^{-1}\right),
$$
or if there exists $x \neq y$ such that
$$
\left(x+x^{-2}, x^{2}+x^{-1}\right)=\left(y^{2}+y^{-1}, y+y^{-2}\right) .
$$

The first case cannot occur: if $x+x^{-2} \equiv y+y^{-2}$, we have that $x^{2}+x^{-1}=x\left(x+x^{-2}\right) \neq y\left(x+x^{-2}\right)=$ $y\left(y+y^{-2}\right)=y^{2}+y^{-1}$. As a consequence of this, the second case only occurs if $y=x^{-1}$. Therefore, the remaining 104 values of $x$ can be partitioned into 52 pairs of $\left(x, x^{-1}\right.$ ), which ends up producing 52 distinct unordered pairs $\{m, n\}$. Adding this to the $x=1$ case and $\{0,0\}$, we get a total of
$$
52+1+1=54
$$
unordered pairs.