2004 IMO Shortlist Problems/N3

From AoPSWiki

Problem

(Mohsen Jamali, Iran) A function $\displaystyle f$ from the set of positive integers $\mathbf{N}$ to itself is such that for all $m, n \in \mathbf{N}$ the number $\displaystyle (m^2 +n)^2$ is divisible by $\displaystyle f^2(m) + f(n)$ . Prove that $\displaystyle f(n) = n$ for each $n \in \mathbf{N}$ .

Comment by the proposer. A possible version of this question is:

Find all functions $f : \mathbf{N}\rightarrow \mathbf{N}$ such that for all $m,n \in \mathbf{N}$ , the number $\displaystyle (m^2 +n)^2$ is divisible by $\displaystyle f^2(m) + f(n)$ .

This alternative form was also Problem 3 of the 2005 5th Romanian TST, Problem 1 of the 3rd independent study of the 2005 3rd Taiwan TST, and Problem 3 of the 2005 French Mathematical Olympiad, Dossier 4.

Note: Although strictly speaking, $\displaystyle f^2(x)$ denotes $\displaystyle f(f(x))$ , in this context it is clear that it means $\displaystyle [f(x)]^2$ .

Solutions

Solution 1

Lemma 1. $\displaystyle f(1) = 1$ .

Proof. We must have $[f(1)]^2 + f(1) \mid (1^2+1)^2 = 4$ . But for any integer $\displaystyle y > 1$ , $y^2 + y \ge 6$ , so we must have $\displaystyle f(1) = 1$ . ∎

Lemma 2. For all natural $\displaystyle n$ , $f(n) \le n^2$ , with equality only when $\displaystyle n=1$ .

Proof. We note that $\displaystyle [f(n)]^2 + f(1) = [f(n)]^2 + 1$ divides $\displaystyle (n^2+1)^2$ . But if $f(n) \ge n^2+1$ , then $\displaystyle [f(n)]^2 + 1 > (n^2 + 1)^2$ , a contradiction. Now, if $\displaystyle n>1$ , then we must have $\displaystyle f(n) + 1 \mid (n+1)^2$ ; since $\displaystyle (n+1)^2/2 < n^2 + 1 < (n+1)^2$ , $n^2 +1 \nmid (n+1)^2$ , so we know that $\displaystyle f(n) \neq n^2$ . ∎

Lemma 3. For any prime $\displaystyle p$ , $\displaystyle f(p-1) = p-1$ .

Proof. We know $f(1) + f(p-1) = 1 + f(p-1) \mid p^2$ . Since $\displaystyle f(p-1)$ is positive, either $\displaystyle f(p-1) = p-1$ , or $\displaystyle f(p-1) = p^2 -1$ . But $\displaystyle p^2 -1 > (p-1)^2$ , so by Lemma 2, $\displaystyle f(p-1) = p-1$ . ∎

Now, for any natural number $\displaystyle n$ and any natural number $\displaystyle k$ that is one less than a prime, we have $[f(k)]^2 + f(n) = k^2 + f(n) \mid (k^2 + n)^2$ . But for some integer $\displaystyle A$ ,

$\displaystyle (k^2 + n)^2 = \{[k^2 + f(n]+[n-f(n)]\}^2 = A[k^2 + f(n)] + [n-f(n)]^2$ .

Hence $k^2 + f(n) \mid [n-f(n)]^2$ . This means that $\displaystyle [n-f(n)]^2$ has infinitely many divisors, i.e., it is equal to zero. Hence for all natural $\displaystyle n$ , $\displaystyle f(n) = n$ .

Solution 2

We use Lemmata 1–3 of the previous solution.

For natural $\displaystyle n$ , we define $\displaystyle \varpi(n)$ to be product of all primes less than or equal to $\displaystyle n$ .

Lemma 4. For all $n\ge 17$ , $\displaystyle \varpi(n) > n^4$ .

Proof. We will use strong induction. We note that $\displaystyle 2 \cdot 5 \cdot 7 \cdot 11 = 770 > 2\cdot 18^2$ , and $\displaystyle 3 \cdot 13 > 18$ , and $\displaystyle 17 > 18/2$ , so $\displaystyle \varpi(18) = \varpi(17) > 18^4 > 17^4$ . Now, for all integers $19 \le n \le 36$ , $\varpi(n) \ge 19 \cdot \varpi(17) > 2^4 \cdot \pi(17) > 2^4\cdot 18^4 = 36^4 \ge n^4$ .

This establishes our base case. Now, for $\displaystyle n > 36$ , suppose that the lemma holds for all integers $17 \le k \le n-1$ . By Bertrand's Postulate, there exists a prime $\displaystyle p_1$ greater than $\lceil n/2 \rceil$ and less than or equal to $\displaystyle n$ . Thus