HMMT February, 2018

Solution:
We start with the equation
$$a^{3}+b^{3} \equiv a b \pmod{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}+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.$$
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.