Maths Olympiad Prep

Library / /22 of 55

, 2016

Algebra Difficulty 8.6 Shortlist Prove it IMO

Denote by N\mathbb{N} the set of all positive integers. Find all functions f:NNf: \mathbb{N} \rightarrow \mathbb{N} such that for all positive integers mm and nn, the integer f(m)+f(n)mnf(m)+f(n)-m n is nonzero and divides mf(m)+nf(n)m f(m)+n f(n).

Solution

It is given that
f(m)+f(n)mnmf(m)+nf(n).(1) f(m)+f(n)-m n \mid m f(m)+n f(n) . \tag{1}
Taking m=n=1m=n=1 in (1), we have 2f(1)12f(1)2 f(1)-1 \mid 2 f(1). Then 2f(1)12f(1)(2f(1)1)=12 f(1)-1 \mid 2 f(1)-(2 f(1)-1)=1 and hence f(1)=1f(1)=1.
Let p7p \geqslant 7 be a prime. Taking m=pm=p and n=1n=1 in (1), we have f(p)p+1pf(p)+1f(p)-p+1 \mid p f(p)+1 and hence
f(p)p+1pf(p)+1p(f(p)p+1)=p2p+1 f(p)-p+1 \mid p f(p)+1-p(f(p)-p+1)=p^{2}-p+1
If f(p)p+1=p2p+1f(p)-p+1=p^{2}-p+1, then f(p)=p2f(p)=p^{2}. If f(p)p+1p2p+1f(p)-p+1 \neq p^{2}-p+1, as p2p+1p^{2}-p+1 is an odd positive integer, we have p2p+13(f(p)p+1)p^{2}-p+1 \geqslant 3(f(p)-p+1), that is,
f(p)13(p2+2p2) \begin{equation*} f(p) \leqslant \frac{1}{3}\left(p^{2}+2 p-2\right) \tag{2} \end{equation*}
Taking m=n=pm=n=p in (1), we have 2f(p)p22pf(p)2 f(p)-p^{2} \mid 2 p f(p). This implies
2f(p)p22pf(p)p(2f(p)p2)=p3. 2 f(p)-p^{2} \mid 2 p f(p)-p\left(2 f(p)-p^{2}\right)=p^{3} .
By (2) and f(p)1f(p) \geqslant 1, we get
p2<2f(p)p223(p2+2p2)p2<p -p^{2}<2 f(p)-p^{2} \leqslant \frac{2}{3}\left(p^{2}+2 p-2\right)-p^{2}<-p
since p7p \geqslant 7. This contradicts the fact that 2f(p)p22 f(p)-p^{2} is a factor of p3p^{3}. Thus we have proved that f(p)=p2f(p)=p^{2} for all primes p7p \geqslant 7.
Let nn be a fixed positive integer. Choose a sufficiently large prime pp. Consider m=pm=p in (1). We obtain
f(p)+f(n)pnpf(p)+nf(n)n(f(p)+f(n)pn)=pf(p)nf(p)+pn2. f(p)+f(n)-p n \mid p f(p)+n f(n)-n(f(p)+f(n)-p n)=p f(p)-n f(p)+p n^{2} .
As f(p)=p2f(p)=p^{2}, this implies p2pn+f(n)p(p2pn+n2)p^{2}-p n+f(n) \mid p\left(p^{2}-p n+n^{2}\right). As pp is sufficiently large and nn is fixed, pp cannot divide f(n)f(n), and so (p,p2pn+f(n))=1\left(p, p^{2}-p n+f(n)\right)=1. It follows that p2pn+f(n)p2pn+n2p^{2}-p n+f(n) \mid p^{2}-p n+n^{2} and hence
p2pn+f(n)(p2pn+n2)(p2pn+f(n))=n2f(n). p^{2}-p n+f(n) \mid\left(p^{2}-p n+n^{2}\right)-\left(p^{2}-p n+f(n)\right)=n^{2}-f(n) .
Note that n2f(n)n^{2}-f(n) is fixed while p2pn+f(n)p^{2}-p n+f(n) is chosen to be sufficiently large. Therefore, we must have n2f(n)=0n^{2}-f(n)=0 so that f(n)=n2f(n)=n^{2} for any positive integer nn.
Finally, we check that when f(n)=n2f(n)=n^{2} for any positive integer nn, then
f(m)+f(n)mn=m2+n2mn f(m)+f(n)-m n=m^{2}+n^{2}-m n
and
mf(m)+nf(n)=m3+n3=(m+n)(m2+n2mn). m f(m)+n f(n)=m^{3}+n^{3}=(m+n)\left(m^{2}+n^{2}-m n\right) .
The latter expression is divisible by the former for any positive integers m,nm, n. This shows f(n)=n2f(n)=n^{2} is the only solution.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.