IMO 2010 · Problem 3

Let \(\mathbb{N}\) be the set of positive integers. Determine all functions \(g:\mathbb{N}\to\mathbb{N}\) such that \[ (g(m)+n)(m+g(n)) \] is a perfect square for all \(m,n\in\mathbb{N}\).

Official text of the problem. Official problem paper (PDF)

Answer

Exactly the functions \[ \boxed{g(n)=n+c\quad\text{for all }n\in\mathbb{N},\qquad c\in\mathbb{Z}_{\ge0}.} \]

Solution

For a prime \(p\) and a positive integer \(x\), let \(v_p(x)\) denote the exponent of \(p\) in the prime factorization of \(x\). A perfect square has even \(v_p\) for every prime \(p\).

We first prove that, for every prime \(p\) and all positive integers \(a,b\), \[ p\mid g(a)-g(b)\quad\Longrightarrow\quad p\mid a-b. \tag{1} \]

Suppose \(p\mid g(a)-g(b)\), and write \(A=g(a)\), \(B=g(b)\). We can choose a positive integer \(n\) such that both \(v_p(A+n)\) and \(v_p(B+n)\) are odd:

  • If \(A\equiv B\pmod{p^2}\), choose \[ n\equiv p-A\pmod{p^2}. \] Then both valuations equal \(1\).

  • Otherwise, \(p\mid B-A\) but \(p^2\nmid B-A\). Choose \[ n\equiv p^3-A\pmod{p^4}. \] Then \(v_p(A+n)=3\), while \(v_p(B+n)=1\).

Each congruence has positive integer solutions. By the hypothesis, both \[ (A+n)(a+g(n)) \quad\text{and}\quad (B+n)(b+g(n)) \] are perfect squares. Since their first factors have odd \(p\)-adic valuations, their second factors must also have odd \(p\)-adic valuations. In particular, \[ p\mid a+g(n),\qquad p\mid b+g(n). \] Subtracting proves (1).

Next, \(g\) is injective. Indeed, if \(g(a)=g(b)\) with \(a\ne b\), choose a prime divisor \(p\) of \(|a-b|+1\). Then (1) gives \(p\mid a-b\), which is impossible because \(p\) also divides \(|a-b|+1\).

For every \(n\), injectivity gives \(g(n+1)-g(n)\ne0\). If its absolute value were greater than \(1\), it would have a prime divisor \(p\), and (1) would imply \(p\mid(n+1)-n=1\), a contradiction. Therefore \[ g(n+1)-g(n)\in\{-1,1\}\qquad(n\in\mathbb{N}). \tag{2} \]

Two successive differences in (2) cannot have opposite signs, since that would give \(g(n+2)=g(n)\), contradicting injectivity. Thus all the differences have the same sign. They cannot all equal \(-1\), since then \[ g\bigl(g(1)+1\bigr)=0, \] contrary to the positive-integer codomain. Hence every difference equals \(1\), and \[ g(n)=g(1)+n-1=n+c, \qquad c=g(1)-1\ge0. \]

Conversely, for any nonnegative integer \(c\), the function \(g(n)=n+c\) maps \(\mathbb{N}\) to itself and satisfies \[ (g(m)+n)(m+g(n))=(m+n+c)^2. \] Thus every listed function satisfies the condition.

The solution was checked against the official IMO shortlist solutions.