Maths Olympiad Prep

Track / Stage 6 / 143 of 400 #1143 of 1964

Problem 1143

National olympiad, first round
Number theory Difficulty 6.2 Prove it

(Shortlist 2004, problem N3) Determine all functions f:NNf: \mathbb{N}^{*} \rightarrow \mathbb{N}^{*} such that, for all m,nNm, n \in \mathbb{N}^{*}, we have

f(m)2+f(n)(m2+n)2 f(m)^{2}+f(n) \mid\left(m^{2}+n\right)^{2}

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

By taking m=n=1m=n=1, we find f(1)2+f(1)4f(1)^{2}+f(1) \mid 4, so f(1)=1f(1)=1. By taking m=1m=1, we then obtain

1+f(n)(n+1)2 1+f(n) \mid (n+1)^{2}

To minimize the number of divisors as much as possible, let's choose n=p1n=p-1 with pp being a prime. Then 1+f(p1)p21+f(p-1) \mid p^{2}, so f(p1)f(p-1) can only be p1p-1 or p21p^{2}-1. In the latter case, by taking n=1n=1 and m=p1m=p-1 in the initial equation, we get

1+(p21)2((p1)2+1)2 1+(p^{2}-1)^{2} \mid ((p-1)^{2}+1)^{2}

Expanding this, it becomes p42p2+2p44p3+6p28p+4p^{4}-2 p^{2}+2 \leqslant p^{4}-4 p^{3}+6 p^{2}-8 p+4, which is impossible for pp large enough. Therefore, we get f(p1)=p1f(p-1)=p-1 for pp a large enough prime.

Finally, let nNn \in \mathbb{N}^{*}. For a large enough prime pp, we have

(p1)2+f(n)((p1)2+n)2 (p-1)^{2}+f(n) \mid ((p-1)^{2}+n)^{2}

We aim to put this in a more convenient form: we have (p1)2f(n)(mod(p1)2+f(n))(p-1)^{2} \equiv -f(n) \pmod{(p-1)^{2}+f(n)}, so the last equation becomes

(p1)2+f(n)((f(n)+n)2 (p-1)^{2}+f(n) \mid ((-f(n)+n)^{2}

and this for any large enough prime pp. The number (f(n)n)2(f(n)-n)^{2} thus has an infinite number of divisors, so f(n)=nf(n)=n.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.