Maths Olympiad Prep

Library / /34 of 397

Algebra Difficulty 4.9 AIME Prove it Taiwan

Let NN and ZZ denote the set of all positive integers and the set of all integers, respectively. Find all functions f:NZf: N \to Z satisfying: nn divides f(m)f(m) if and only if mm divides dnf(d)\sum_{d|n} f(d), for all positive integers nn and mm.

Solution

Answer: f(n)=0,nNf(n) = 0, \forall n \in N

If f(1)0f(1) \neq 0, then take m=1,n=f(1)+1m = 1, n = |f(1)| + 1, since 1dnf(d)1|\sum_{d|n} f(d), so nf(1)n|f(1) but 0<f(1)<n0 < |f(1)| < n, a contradiction. Hence f(1)=0f(1) = 0.

Below we prove that for all positive integers kk, f(2k)=0f(2^k) = 0.
By contradiction, suppose there exists a positive integer kk such that f(2k)0f(2^k) \neq 0, and suppose tt is the smallest such one, then for all m>f(2t)m > |f(2^t)| we have
md2t1f(d)m|\sum_{d|2^{t-1}} f(d) but mm does not divide d2tf(d)\sum_{d|2^t} f(d),
that is, 2t1f(m)2^{t-1}|f(m) but 2t2^t does not divide f(m)f(m).
Take a prime p>f(2t)p > |f(2^t)|, and substitute n=p2,m=2tn = p^2, m = 2^t, we get
2t(f(1)+f(p)+f(p2)), 2^t|(f(1)+f(p)+f(p^2)),
so p2f(2t)p^2|f(2^t), but 0<f(2t)<p<p20 < |f(2^t)| < p < p^2, a contradiction.
Therefore f(2k)=0,kNf(2^k) = 0, \forall k \in N.

For any positive integer mm, take a sufficiently large n=2kn = 2^k, then
m(f(1)++f(2k))2kf(m), m|(f(1)+\cdots+f(2^k)) \Rightarrow 2^k|f(m),
since kk can be arbitrarily large, therefore only f(m)=0f(m) = 0. Q.E.D.!

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 translated into English from zh; metadata (topic, difficulty) added by this project.