Задача
NT-B2-M10-P013 Делимость \(\varphi(m)\mid\varphi(n)\)
#13
★★★★☆ Уровень 4 из 5
Докажите, что если \(m\mid n\), то \(\varphi(m)\mid\varphi(n)\).
1001 Problems in Classical Number Theory (method inspiration) · Задача 525
Сравните показатели простых в разложениях \(m\) и \(n\).
Пусть \(m=\prod p^{a_p}\), \(n=\prod p^{b_p}\), где \(0\le a_p\le b_p\). Для простого \(p\) вклад в \(\varphi(p^a)\) равен \(p^{a-1}(p-1)\) при \(a\ge 1\). Если \(a_p=0\), вклада нет. Если \(a_p\ge 1\), то соответствующий вклад в \(\varphi(n)\) содержит \(p^{b_p-1}(p-1)\), который делится на \(p^{a_p-1}(p-1)\). Перемножая по простым, получаем \(\varphi(m)\mid\varphi(n)\).
Хорошая задача на аккуратную работу с простыми степенями.