Maths Olympiad Prep

Library / Croatian Mathematical Olympiad /16 of 37

Croatian Mathematical Olympiad

Number theory Difficulty 6.2 National Olympiad Prove it Croatia

Let f:N→Nf: \mathbb{N} \to \mathbb{N} be a function such that for all positive integers aa and bb,
f(a)+f(b)−ab∣af(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)−ab∣af(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)−1∣2f(1)2f(1) - 1 \mid 2f(1). Then 2f(1)−1∣2f(1)−(2f(1)−1)=12f(1) - 1 \mid 2f(1) - (2f(1) - 1) = 1 and hence f(1)=1f(1) = 1.

Let p≥7p \ge 7 be a prime. Taking a=pa = p and b=1b = 1 in (3), we have f(p)−p+1∣pf(p)+1f(p) - p + 1 \mid pf(p) + 1 and hence
f(p)−p+1∣pf(p)+1−p(f(p)−p+1)=p2−p+1. f(p) - p + 1 \mid pf(p) + 1 - p(f(p) - p + 1) = p^2 - p + 1.
If f(p)−p+1=p2−p+1f(p) - p + 1 = p^2 - p + 1, then f(p)=p2f(p) = p^2. If f(p)−p+1≠p2−p+1f(p) - p + 1 \ne p^2 - p + 1, as p2−p+1p^2 - p + 1 is an odd positive integer, we have p2−p+1≥3(f(p)−p+1)p^2 - p + 1 \ge 3(f(p) - p + 1), i.e.
f(p)≤13(p2+2p−2).(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)−p2∣2pf(p)2f(p) - p^2 \mid 2pf(p). This implies
2f(p)−p2∣2pf(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)−p2≤23(p2+2p−2)−p2<−p, -p^2 < 2f(p) - p^2 \le \frac{2}{3}(p^2 + 2p - 2) - p^2 < -p,
since p≥7p \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 p≥7p \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)+p2−pa∣af(a)+p3=a(f(a)+p2−pa)+p3−p2a+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)+p2−pa∣p(p2−pa+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)+p2−paf(a) + p^2 - pa and pp are relatively prime. It follows that
f(a)+p2−pa∣p2−pa+a2=(f(a)+p2−pa)+a2−f(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)+p2−pa∣a2−f(a). f(a) + p^2 - pa \mid a^2 - f(a).
Note that a2−f(a)a^2 - f(a) is fixed while f(a)+p2−paf(a) + p^2 - pa is chosen to be sufficiently large. Therefore, we must have a2−f(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+b2−ab f(a) + f(b) - ab = a^2 + b^2 - ab
and
af(a)+bf(b)=a3+b3=(a+b)(a2+b2−ab). 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.