Problem
NT-B2-M10-P013 Divisibility \(\varphi(m)\mid\varphi(n)\)
#13
★★★★☆ Level 4 of 5
Prove that if \(m\mid n\), then \(\varphi(m)\mid\varphi(n)\).
1001 Problems in Classical Number Theory (method inspiration) · Problem 525
Compare prime exponents in the factorisations of \(m\) and \(n\).
Let \(m=\prod p^{a_p}\), \(n=\prod p^{b_p}\), where \(0\le a_p\le b_p\). For a prime \(p\), the contribution to \(\varphi(p^a)\) is \(p^{a-1}(p-1)\) for \(a\ge 1\). If \(a_p=0\), there is no contribution. If \(a_p\ge 1\), the corresponding contribution in \(\varphi(n)\) contains \(p^{b_p-1}(p-1)\), divisible by \(p^{a_p-1}(p-1)\). Multiplying over all primes gives \(\varphi(m)\mid\varphi(n)\).
A good problem for careful work with prime powers.