HMMT November

There are no such pairs when $b=57$, so we may only consider pairs with $1 \leq a<b \leq 56$. The key idea is that unless $a^{2} \bmod 57=b^{2} \bmod 57,(a, b)$ can be paired with $(57-b, 57-a)$ and exactly one of them satisfies $a^{2} \bmod 57<b^{2} \bmod 57$. Hence if $X$ is the number of pairs $(a, b)$ with $1 \leq a<b \leq 56$ and $a^{2} \equiv b^{2}(\bmod 57)$, then the answer is $\frac{1}{2}\left(\binom{56}{2}-X\right)$. To count $X$, let's first count the number of pairs $(a, b)$ with $1 \leq a, b \leq 57$ and $a^{2} \equiv b^{2}(\bmod 57)$. By the Chinese Remainder Theorem, the condition is equivalent to $(a-b)(a+b) \equiv 0(\bmod 3)$ and $(a-b)(a+b) \equiv 0(\bmod 19)$. There are $2 \cdot 3-1=5$ pairs of residues modulo 3 where $(a-b)(a+b) \equiv 0$ $(\bmod 3)$, namely $(0,0),(1,1),(2,2),(1,2),(2,1)$. Similarly, there are $2 \cdot 19-1=37$ pairs of residues modulo 19 where $(a-b)(a+b) \equiv 0(\bmod 19)$. By the Chinese Remainder Theorem, each choice of residues modulo 3 for $a$ and $b$ and residues modulo 19 for $a$ and $b$ corresponds to unique residues modulo 57 for $a$ and $b$. It follows that there are $5 \cdot 37=185$ such pairs. To get the value of $X$, we need to subtract the 57 pairs where $a=b$ and divide by 2 for the pairs with $a>b$, for a value of $X=\frac{1}{2}(185-57)=64$. Therefore the final answer is $\frac{1}{2}\left(\binom{56}{2}-64\right)=738$.