Задача
NT-B2-M10-P019 Степень двойки в \(\varphi(n)\)
#19
★★★★★ Уровень 5 из 5
Пусть \(n>1\), а \(\omega(n)\) — число различных простых делителей \(n\). Докажите, что \(2^{\omega(n)-1}\mid \varphi(n)\).
1001 Problems in Classical Number Theory (method inspiration) · Задача 532
Запишите \(\varphi(n)=\prod p^{a-1}(p-1)\) и посчитайте чётные множители \(p-1\).
Пусть \(n=\prod_{i=1}^{r}p_i^{a_i}\), где \(r=\omega(n)\). Тогда \(\varphi(n)=\prod_{i=1}^{r}p_i^{a_i-1}(p_i-1)\). Если среди \(p_i\) нет числа \(2\), то все \(p_i\) нечётны, и каждый множитель \(p_i-1\) чётен; значит \(2^r\mid\varphi(n)\), тем более \(2^{r-1}\mid\varphi(n)\). Если \(2\mid n\), то среди остальных \(r-1\) простых все нечётны, и их множители \(p_i-1\) дают делимость на \(2^{r-1}\). Утверждение доказано.
Сильная, но чистая задача на структуру формулы Эйлера.