Maths Olympiad Prep

Track / Stage 8 / 74 of 180 #2414 of 2604

Problem 2414

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 m≥nm \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,n≥2, 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 m≥2m \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 m≥2m \ge 2.
Claim For positive integers m,pm, p with m≥2m \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 p≥2p \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(p−1)m)=p2(p−1)f(m) f(p^2(p-1)m) = p^2(p-1)f(m)
for all m≥pm \ge p. By the induction hypothesis,
p2(p−1)f(m)=f(p2(p−1)m)=(p−1)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 m≥pm \ge p.

Next, take n=p2n = p^2 in the governing equation to get
f(p5(p−1)m)=p5(p−1)f(m) f(p^5(p-1)m) = p^5(p-1)f(m)
for m≥p2m \ge p^2. In a similar manner, it follows by induction that
f(p5(p−1)m)=(p−1)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 m≥p2m \ge p^2.
Based on the above argument, we take kk with 4k≥p24^k \ge p^2: for any m≥2m \ge 2,
4kp4f(pm)=2◯4kf(p5m)=1◯f(4kp5m)=3◯p5f(4km)=1◯p54kf(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 m≥2m \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 m≥2m \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.