IMO 2004 SL N3

Origin: IRN | Category: Number Theory

Problem

A function f from the set of positive integers N into itself is such that for all m, n \inN the number (m2 + n)2 is divisible by f 2(m) + f(n). Prove that f(n) = n for each n \inN.

Solution

For m = n = 1 we obtain that f(1)2 + f(1) divides (12 + 1)2 = 4, from which we find that f(1) = 1. Next, we show that f(p−1) = p−1 for each prime p. By the hypothesis for m = 1 and n = p−1, f(p−1)+1 divides p2, so f(p−1) equals either p−1 or p2 −1. If f(p−1) = p2 −1, then f(1)+f(p−1)2 = p4 −2p2 + 2 divides (1+(p−1)2)2 < p4−2p2+2, giving a contradiction. Hence f(p−1) = p−1. Let us now consider an arbitrary n \inN. By the hypothesis for m = p −1, A = f(n) + (p −1)2 divides (n + (p −1)2)2 \equiv(n −f(n))2 (mod A), and hence A divides (n−f(n))2 for any prime p. Taking p large enough, we can obtain A to be greater than (n−f(n))2, which implies that (n−f(n))2 = 0, i.e., f(n) = n for every n.