United States — Team Selection Test, 2009

Solution 1 (Based on the work of John Berman). The answer is $(m, n) = (2, 2)$ or $(m, n) = (t^2 \pm 2t + 2, t^2 + 1)$ for some $t \ge 0$.
We first check that these pairs work: $2 \cdot 2 - 1 = 3 \mid 3^2 = (2^2 - 2 + 1)^2$ and
$$(t^2 \pm 2t + 2)(t^2 + 1) - 1 = (t^2 \pm t + 1)^2 \mid (t^4 + t^2 + 1)^2 = ((t^2 + 1)^2 - (t^2 + 1) + 1)^2.$$
We now wish to show that these are the only solutions. First, notice that if $n = 1$ or $n = 2$, we have $m - 1 \mid 1$ or $2m - 1 \mid 9$, respectively, so it is easy to verify that the only solutions are of the claimed form. From now on, we assume that $n \ge 2$. Suppose that $(m, n)$ is a solution. Then, notice that
$$m^2(n^2 - n + 1)^2 - n^2(m^2 - m + 1)^2 = (mn^2 - m^2n + m - n)(mn^2 + m^2n - 2mn + m + n) \\ = (mn - 1)(n - m)(mn^2 + m^2n - 2mn + m + n)$$
is divisible by $mn - 1$, meaning that $(mn - 1) \mid n^2(m^2 - m + 1)^2$. But $mn - 1$ and $n^2$ are relatively prime, so in fact $(mn - 1) \mid (m^2 - m + 1)^2$. This means that $(m, n)$ is a solution if and only if $(n, m)$ is.
Suppose now for the sake of contradiction that there existed a solution $(m, n)$ that was not of the stated form. Choose such a solution so that $m + n$ is minimal among such solutions and so that $m \ge n$, which we may do by the previous paragraph. Now, notice that $(n^2 - n + 1)^2 \equiv 1 \pmod{n}$ and $mn - 1 \equiv -1 \pmod{n}$, meaning that $\frac{(n^2 - n + 1)^2}{mn - 1} \equiv -1 \pmod{n}$. Write $\frac{(n^2 - n + 1)^2}{mn - 1} = kn - 1$ for some integer $k$. Notice that $(k, n)$ is another solution and that
$$kn - 1 \le \frac{(n^2 - n + 1)^2}{n^2 - 1} < \frac{(n^2 - 1)^2}{n^2 - 1} = n^2 - 1,$$
because $m \ge n$ and $n \ge 2$. Hence, we see that $k < n \le m$, so we find $k + n < m + n$. Because $m + n$ was minimal among solutions not of the claimed form, we have either that $(k, n) = (2, 2)$ or $(k, n) = ((t - 1)^2 + 1, t^2 + 1)$ for some $t$. In the first case, we see that $mn - 1 = \frac{(n^2 - n + 1)^2}{kn - 1} = 3$, so $(m, n) = (2, 2)$. In the second case, we find that $mn - 1 = \frac{(n^2 - n + 1)^2}{kn - 1} = ((t + 1)^2 + 1)n - 1$, so $(m, n) = ((t + 1)^2 + 1, t^2 + 1)$. Therefore, $(m, n)$ is a solution of the claimed form, a contradiction. Hence, we have found all possible solutions.

Solution 2 (By Zuming Feng with assistance from Sherry Gong and Palmer Mebane). We apply Fermat's infinite descent method. Suppose that $(m, n)$ is a pair of positive integers satisfying the given conditions. By the given condition, we have
$$0 \equiv (n^2 - n + 1)^2 \equiv m^2(n^2 - n + 1)^2 \equiv (mn^2 - mn + 1)^2 \equiv (n + m - 1)^2 \pmod{mn - 1};$$
that is, $mn - 1$ divides $(m + n - 1)^2$. Assume that
$$\frac{(m + n - 1)^2}{mn - 1} = q \quad \text{or} \quad (m + n - 1)^2 - q(mn - 1) = 0. \qquad (1)$$
Notice that the above relation is symmetric with respect to $m$ and $n$.
Now, suppose that $(m, n)$ is a solution of the equation such that $m \ge n \ge 0$ and so that $m + n$ is minimal among all solutions $(m', n')$ of (1) for a fixed $q$. Consider the quadratic equation
$$f(x) = (x + n - 1)^2 - q(xn - 1) = x^2 + (2n - 2 - qn)x + (n - 1)^2 + q. \qquad (2)$$
One of the roots of $f(x)$ is $x_1 = m$; let the other be $x_2$. Then $x_1 + x_2 = qn + 2 - 2n$ (implying that $x_2$ is an integer) and $x_1x_2 = (n-1)^2 + q$ (implying that $x_2$ is positive). Thus, $(x_2, n)$ is another pair of positive integers satisfying (1). By our minimality assumption on $(m, n)$, we must have $x_2 \ge m$. Thus, either $n = m$ or point $(n, 0)$ lies to the left of the two roots of $f(x)$, from which it follows that
$$0 \le f(n) = (2n - 1)^2 - q(n^2 - 1) = (4 - q)n^2 - 4n + q + 1;$$
that is, we have
$$0 \ge (q-4)n^2 + 4n - (q+1) = (q-4)n^2 + 5n - (q+1) - n = [(q-4)n + (q-1)](n-1) - n. \quad (3)$$
Now we consider all the possible values of $n$ and $q$. If $n = 1$, (1) becomes $m^2 = q(m - 1)$, which is impossible for integer $m > 2$ because $\text{gcd}(m, m-1) = 1$ for $m \ge 3$. Thus the only possible solution in this case is $(m, n) = (2, 1)$ and $q = 4$. For $n = 2$, we can write (1) as
$$4q = \frac{4(m+1)^2}{2m-1} = 2m + 5 + \frac{9}{2m-1},$$
giving only the solution $(m, n) = (2, 2)$ with $q = 3$. For $n \ge 3$, (3) becomes
$$0 \ge [(q-4)n + (q-1)](n-1) - n \ge 2(q-4)n - n = (2q-9)n,$$
which is true only if $q \le 4$. Also, by the AM-GM inequality, (1) leads to $q(mn - 1) = (m + n - 1)^2 \ge 4n(m - 1) = 4mn - 4n$. If $q \le 3$, then $3mn - 3 \le 4mn - 4n$ or $mn \le 4n + 3$. Therefore, we can conclude that either $q = 4$ or $q = 3$ and $3 \le m \le 4$; it is easy to check that neither case leads to any solutions. Thus, the only minimal solutions are $(m, n) = (2, 2)$ with $q = 3$ and $(m, n) = (2, 1)$ with $q = 4$.
Suppose now for the sake of contradiction that for some $q$ there existed a solution $(m, n)$ that was not of the claimed form. Choose such a solution with $m+n$ minimal and so that $m \ge n$. Then, write $m_2 = qn + 2 - 2n - m$ for the root of $f(x) = (x+n-1)^2 - q(xn-1)$ other than $m$. If $m_2 < m$, then $m_2 + n < m + n$, meaning that either $(m_2, n) = (2, 2)$ or $(m_2, n) = (t^2 \pm 2t + 2, t^2 + 1)$; in the first case, we see that $(m, n) = (2, 2)$ and in the second we see that $(m, n) = (t^2 \mp 2t + 2, t^2 + 1)$, which are both in the claimed form, a contradiction. Otherwise, we have $qn + 2 - 2n - m = m_2 \ge m$, so we find that $\frac{q-2}{2}n + 1 \ge m \ge n$. For $q = 3$, this implies that $n \le 2$, so we may check that $(m, n) = (2, 2)$, a contradiction. For $q = 4$, we see that $n + 1 \ge m \ge n$; if $m = n$, (1) reduces to $5 - 4n = 0$, which is impossible, and if $m = n + 1$, (1) gives $4 - 4n = 0$, so $(m, n) = (2, 1)$, a contradiction. Therefore, all solutions are of the claimed form.