Maths Olympiad Prep

Library / /16 of 48

Number theory Difficulty 8.3 Shortlist Prove it 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).

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

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 reproduced verbatim; metadata (topic, difficulty) added by this project.