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 m≥nm \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,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

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.