CGMO, 2024

Proof. Let $m^2 + r = 2^k$ and $n^2 + r = 2^l$ with $k, l \in \mathbb{Z}_{>0}$.
First, we analyze the 2-adic valuations:
* Since $v_2(m^2) = v_2(2^k - r) = v_2(r)$, we conclude $v_2(r)$ must be even.
* Let $v_2(r) = 2t$ where $t \in \mathbb{Z}_{\ge 0}$, and write $r = 2^{2t}r_1$, $m = 2^t m_1$.
* Similarly, $v_2(n^2) = v_2(r)$, so let $n = 2^t n_1$.
Define $k_1 = k - 2t$ and $l_1 = l - 2t$, which gives the reduced system:
$$m_1^2 + r_1 = 2^{k_1},$$
$$n_1^2 + r_1 = 2^{l_1}.$$
Claim: $r_1 \ge 7$.
* Since $r_1$ is odd, both $m_1$ and $n_1$ must be odd.
* As $n_1 \ge 3$ (because $n > m \ge 1$), we have $l_1 > 3$.
* Thus $n_1^2 + r_1 \equiv 1 + r_1 \equiv 0 \pmod 8$, implying $r_1 \equiv 7 \pmod 8$.
* Therefore $r_1 \ge 7$.
This also shows $k_1 \ge 3$. Now consider the difference:
$$2^{l_1} - 2^{k_1} = (n_1 - m_1)(n_1 + m_1).$$
Since $2^{k_1}$ divides the product $(n_1 - m_1)(n_1 + m_1)$, and both factors are even but cannot both be divisible by $4$ (which would imply $m_1$ and $n_1$ are both even), we have:
$$2^{k_1-1} \mid (n_1 - m_1) \quad \text{or} \quad 2^{k_1-1} \mid (n_1 + m_1).$$
This leads to the lower bound:
$$\begin{align*} n_1 &\ge 2^{k_1-1} - m_1 = \frac{1}{2}(m_1^2 + r_1) - m_1 \\ &= \frac{3m_1^2}{7} + \left( \frac{m_1^2}{14} + \frac{r_1}{2} - m_1 \right) \\ &\ge \frac{3m_1^2}{r_1} + \left( \frac{m_1^2}{14} + \frac{7}{2} - m_1 \right) \quad (\text{since } r_1 \ge 7) \\ &= \frac{3m_1^2}{r_1} + \frac{1}{14}(m_1 - 7)^2 \\ &\ge \frac{3m_1^2}{r_1} = \frac{3m^2}{r}. \end{align*}$$

$$n = 2^t n_1 \ge n_1 \ge \frac{3m^2}{r} > \frac{2m^2}{r},$$