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

$\varpi(n) \ge p_1 \cdot \varpi(\lceil n/2 \rceil) > p_1 \cdot (\lceil n/2 \rceil)^4 \ge p_1 \cdot (n/2)^4 > n/2 \cdot (n/2)^4 > 16 \cdot (n/2)^4 = n^4$ .

Thus our lemma holds by strong induction. ∎

We will now prove that for all natural $\displaystyle n$ , $\displaystyle f(n) = n$ .

If this is not true, then there is a least $\displaystyle n_0$ for which this is not true.

Lemma 5. If $\displaystyle n_0$ exists, then it is not prime.

Proof. Suppose the contrary. One of the numbers $[f(n_0)]^2, [f(n_0)]^2 + 1, \ldots, [f(n_0)]^2 + n_0 -1$ must be divisible by $\displaystyle n_0$ . But since $[f(n_0)]^2 +1 ,\ldots, [f(n_0)]^2 + n_0-1$ must divide ${} (n_0^2+1)^2, \ldots, (n_0^2+n_0-1)^2$ , none of which can be divisible by $\displaystyle n_0$ , we conclude that $n_0 \mid [f(n_0)]^2$ and hence $n_0 \mid f(n_0)$ . Furthermore, for any prime $\displaystyle p< n_0$ , $\displaystyle [f(n_0)]^2+p$ cannot be divisible by $\displaystyle p$ , since it is a divisor of $\displaystyle (n_0^2+p)^2$ , which is not divisible by $\displaystyle p$ , so $p \nmid f(n_0)$ . Since $\displaystyle f(n_0) < n_0^2$ , it follows that $\displaystyle n_0$ is the only prime divisor of $\displaystyle f(n_0)$ and again since $\displaystyle f(n_0) < n_0^2$ , $\displaystyle f(n_0) = n_0$ , a contradiction. ∎

Lemma 6. If $\displaystyle n_0$ exists, then none of the numbers $n_0^2+1, \ldots, n_0^2 + n_0 -1$ is prime.

Proof. Suppose, on the contrary, that $\displaystyle n_0^2 + k$ is prime, for some integer $1 \le k \le n_0-1$ . We know $[f(n_0)]^2 + k \mid p^2$ . But since $\displaystyle 1< [f(n_0)]^2 +k < n_0^4 + k < (n_0^2+k)^2 = p^2$ , we must have $\displaystyle [f(n_0)]^2 +k = n_0^2 + k$ , which implies $\displaystyle f(n_0) = n_0$ , a contradiction. ∎

We now claim that $\displaystyle n_0$ does not exist. Since neither $\displaystyle n_0$ nor $\displaystyle n_0+1$ may be prime (by Lemmata 5 and 3), the only possibilities for $\displaystyle n_0 < 17$ are 8, 9, 14, and 15. But $\displaystyle 8^2 + 3 = 67$ , $\displaystyle 9^2 + 8 = 89$ , $\displaystyle 14^2+1 = 197$ , and $\displaystyle 15^2 +2 = 227$ are all prime, by Lemma 6, we conclude that $n\ge 17$ . But for each prime $\displaystyle p$ less than $\displaystyle n_0$ , one of the numbers

$[f(n_0)]^2+1, \ldots, [f(n_0)]^2 + p$

must be divisible by $\displaystyle p$ . Since these divide $(n_0^2 + 1)^2, \ldots, (n_0^2 + p)^2$ , the only one of these which can be divisible by $\displaystyle p$ is $\displaystyle [f(n_0)]^2 + k$ , where $\displaystyle k$ is the integer between 1 and $\displaystyle p$ such that $k \equiv -n_0^2 \pmod{p}$ . It follows that for all primes $\displaystyle p$ less than $\displaystyle n$ ,

$[f(n_0)]^2 \equiv n_0^2 \pmod{p}$ .

By the Chinese Remainder Theorem, then,

$[f(n_0)]^2 \equiv n_0^2 \pmod{\varpi(n_0)}$ .

But by Lemma 4, the only solutions to this congruence other than $\displaystyle [f(n_0)]^2 = n_0^2$ are negative numbers (which are clearly impossible), and solutions which imply $\displaystyle [f(n_0)^2] > n^2 + n^4$ . But by Lemma 2, this implies $\displaystyle n^4 > [f(n_0)]^2 > n^2 + n^4$ , a contradiction. Thus $\displaystyle n_0$ does not exist, so there is no integer $\displaystyle n$ such that $\displaystyle f(n) \neq n$ . Q.E.D.