Maths Olympiad Prep

Track / Stage 8 / 74 of 180 #2254 of 2444

Problem 2254

IMO Shortlist mid-range; USAMO P2/P5
Number theory Difficulty 8.3 Prove it China National Team Selection Test · China

For a positive integer nn, let φ(n)\varphi(n) represent the number of positive integers not exceeding nn and relatively prime to nn. Find all functions f:N+N+f:\mathbb{N}_+ \to \mathbb{N}_+ satisfying that for any positive integers m,nm, n with mnm \ge n,
f(mφ(n3))=f(m)φ(n3).f(m\varphi(n^3)) = f(m)\varphi(n^3).

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

The desired functions have the form
f(n)={c,n=1,dn,n2, f(n) = \begin{cases} c, & n = 1, \\ dn, & n \ge 2, \end{cases}
where c,dc, d are positive integers. It is straightforward to check that the problem conditions are met.
In the governing equation, taking n=2n = 2 leads to f(4m)=4f(m)f(4m) = 4f(m) for m2m \ge 2. By iterations, it follows that
f(4km)=4kf(m)1 f(4^k m) = 4^k f(m) \qquad \textcircled{1}
for all m2m \ge 2.
Claim For positive integers m,pm, p with m2m \ge 2, f(pm)=pf(m)f(pm) = p f(m).
Proof of claim Induct on pp: when p=1p = 1, the conclusion is trivial; assume p2p \ge 2 and the conclusion is valid for all positive integers less than pp. Now, if pp is composite, the conclusion is validated by the induction hypothesis. In the following, assume pp is a prime. Taking n=pn = p in the governing equation, we obtain
f(p2(p1)m)=p2(p1)f(m) f(p^2(p-1)m) = p^2(p-1)f(m)
for all mpm \ge p. By the induction hypothesis,
p2(p1)f(m)=f(p2(p1)m)=(p1)f(p2m), \begin{aligned} p^2(p-1)f(m) &= f(p^2(p-1)m) \\ &= (p-1)f(p^2m), \end{aligned}
and thus
f(p2m)=p2f(m)2 f(p^2m) = p^2f(m) \qquad \textcircled{2}
for all mpm \ge p.

Next, take n=p2n = p^2 in the governing equation to get
f(p5(p1)m)=p5(p1)f(m) f(p^5(p-1)m) = p^5(p-1)f(m)
for mp2m \ge p^2. In a similar manner, it follows by induction that
f(p5(p1)m)=(p1)f(p5m). f(p^5(p-1)m) = (p-1)f(p^5m).
Hence,
f(p5m)=p5f(m)3 f(p^5m) = p^5f(m) \qquad \textcircled{3}
for mp2m \ge p^2.
Based on the above argument, we take kk with 4kp24^k \ge p^2: for any m2m \ge 2,
4kp4f(pm)=24kf(p5m)=1f(4kp5m)=3p5f(4km)=1p54kf(m). 4^k p^4 f(p m) \stackrel{\textcircled{2}}{=} 4^k f(p^5 m) \stackrel{\textcircled{1}}{=} f(4^k p^5 m) \stackrel{\textcircled{3}}{=} p^5 f(4^k m) \stackrel{\textcircled{1}}{=} p^5 4^k f(m).
Therefore, f(pm)=pf(m)f(p m) = p f(m), and the induction is completed.
According to the claim, particularly for m2m \ge 2,
2f(m)=f(2m)=mf(2). 2f(m) = f(2m) = m f(2).
Taking m=3m = 3, we infer that f(2)f(2) is even. So for m2m \ge 2, f(m)=dmf(m) = d m, where d=f(2)2d = \frac{f(2)}{2} is an integer. \square

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