Maths Olympiad Prep

Library / Taiwan IMO Selection Camp /33 of 359

Taiwan IMO Selection Camp

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:N→Zf: N \to Z satisfying: nn divides f(m)f(m) if and only if mm divides ∑d∣nf(d)\sum_{d|n} f(d), for all positive integers nn and mm.

Solution

Answer: f(n)=0,∀n∈Nf(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 1∣∑d∣nf(d)1|\sum_{d|n} f(d), so n∣f(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
m∣∑d∣2t−1f(d)m|\sum_{d|2^{t-1}} f(d) but mm does not divide ∑d∣2tf(d)\sum_{d|2^t} f(d),
that is, 2t−1∣f(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 p2∣f(2t)p^2|f(2^t), but 0<∣f(2t)∣<p<p20 < |f(2^t)| < p < p^2, a contradiction.
Therefore f(2k)=0,∀k∈Nf(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))⇒2k∣f(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,604 problems in a working order, from Junior Challenge 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.