Maths Olympiad Prep

Library / /16 of 39

Number theory Difficulty 6.2 National Olympiad Prove it Croatia

Let f:NNf: \mathbb{N} \to \mathbb{N} be a function such that for all positive integers aa and bb,
f(a)+f(b)abaf(a)+bf(b). f(a) + f(b) - ab \mid af(a) + bf(b).
Find all such functions ff.

Solution

It is given that
f(a)+f(b)abaf(a)+bf(b).(3) f(a) + f(b) - ab \mid af(a) + bf(b). \qquad (3)
Taking a=b=1a = b = 1 in (3), we have 2f(1)12f(1)2f(1) - 1 \mid 2f(1). Then 2f(1)12f(1)(2f(1)1)=12f(1) - 1 \mid 2f(1) - (2f(1) - 1) = 1 and hence f(1)=1f(1) = 1.

Let p7p \ge 7 be a prime. Taking a=pa = p and b=1b = 1 in (3), we have f(p)p+1pf(p)+1f(p) - p + 1 \mid pf(p) + 1 and hence
f(p)p+1pf(p)+1p(f(p)p+1)=p2p+1. f(p) - p + 1 \mid pf(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 \ne 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 \ge 3(f(p) - p + 1), i.e.
f(p)13(p2+2p2).(4) f(p) \le \frac{1}{3}(p^2 + 2p - 2). \qquad (4)
Taking a=b=pa = b = p in (3), we have 2f(p)p22pf(p)2f(p) - p^2 \mid 2pf(p). This implies
2f(p)p22pf(p)p(2f(p)p2)=p3. 2f(p) - p^2 \mid 2pf(p) - p(2f(p) - p^2) = p^3.
By (4) and f(p)1f(p) \ge 1 we get
p2<2f(p)p223(p2+2p2)p2<p, -p^2 < 2f(p) - p^2 \le \frac{2}{3}(p^2 + 2p - 2) - p^2 < -p,
since p7p \ge 7. This contradicts the fact that 2f(p)p22f(p) - p^2 is a factor of p3p^3. Thus we have proved that f(p)=p2f(p) = p^2 for all primes p7p \ge 7.

Let aa be a fixed positive integer. Choose a sufficiently large prime pp. Consider b=pb = p in (3). We obtain
f(a)+p2paaf(a)+p3=a(f(a)+p2pa)+p3p2a+pa2, f(a) + p^2 - pa \mid af(a) + p^3 = a(f(a) + p^2 - pa) + p^3 - p^2a + pa^2,
i.e.
f(a)+p2pap(p2pa+a2). f(a) + p^2 - pa \mid p(p^2 - pa + a^2).
As pp is sufficiently large and aa is fixed, pp cannot divide f(a)f(a), and so numbers f(a)+p2paf(a) + p^2 - pa and pp are relatively prime. It follows that
f(a)+p2pap2pa+a2=(f(a)+p2pa)+a2f(a), f(a) + p^2 - pa \mid p^2 - pa + a^2 = (f(a) + p^2 - pa) + a^2 - f(a),
i.e.
f(a)+p2paa2f(a). f(a) + p^2 - pa \mid a^2 - f(a).
Note that a2f(a)a^2 - f(a) is fixed while f(a)+p2paf(a) + p^2 - pa is chosen to be sufficiently large. Therefore, we must have a2f(a)=0a^2 - f(a) = 0, so that f(a)=a2f(a) = a^2 for any positive integer aa.

Finally, we check that when f(a)=a2f(a) = a^2 for any positive integer aa, then
f(a)+f(b)ab=a2+b2ab f(a) + f(b) - ab = a^2 + b^2 - ab
and
af(a)+bf(b)=a3+b3=(a+b)(a2+b2ab). af(a) + bf(b) = a^3 + b^3 = (a + b)(a^2 + b^2 - ab).
The latter expression is divisible by the former for any positive integers aa and bb. This shows that f(a)=a2f(a) = a^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 reproduced verbatim; metadata (topic, difficulty) added by this project.