Berkeley Math Circle Monthly Contest 8

Solution:

Let $n = a^2 + b^2$, where $a$ and $b$ are nonnegative integers. Suppose that each of the squares $a^2$ and $b^2$ is less than $4$ times the other, so
$$a < 2b \text{ and } b < 2a.$$
Since $a^2 + b^2$ is divisible by $5$, so is $a^2 + b^2 - 5b^2 = a^2 - 4b^2 = (a + 2b)(a - 2b)$. Thus $5$ divides either $a + 2b$ or $a - 2b$. If $5 \mid a - 2b$, then $5 \mid 2(a - 2b) + 5b = 2a + b$. Thus $5$ divides either $a + 2b$ or $2a + b$, and by switching the labels $a$ and $b$ we may assume that $5 \mid a + 2b$.

Then
$$5 \mid 4(a + 2b) - 5b = 4a + 3b$$
and
$$5 \mid 3(a + 2b) - 10b = 3a - 4b.$$
Note that
$$\begin{aligned} \left(\frac{4a + 3b}{5}\right)^2 + \left(\frac{3a - 4b}{5}\right)^2 &= \frac{16a^2 + 24ab + 9b^2 + 9a^2 - 24ab + 16b^2}{25} \\ &= \frac{25a^2 + 25b^2}{25} = a^2 + b^2 = n. \end{aligned}$$
We claim that
$$\left(\frac{4a + 3b}{5}\right)^2 \geq 4\left(\frac{3a - 4b}{5}\right)^2$$
which is equivalent to
$$4a + 3b \geq 2|3a - 4b|$$
which in turn is equivalent to the pair of inequalities
$$4a + 3b \geq 2(3a - 4b) \text{ and } 4a + 3b \geq -2(3a - 4b)$$
Simplifying the first inequality yields $11b \geq 2a$ which is true since $2b \geq a$. Simplifying the second inequality yields $10a \geq 5b$ which is true since $2a \geq b$.