Сумма по делителям

[Ward]

Здравствуйте!

Чему равно такая сумма

$$\sum \limits_{d \mid n}\mu(d)\varphi\left(\frac{n}{d}\right)$$

Помогите пожалуйста

[ИСН]

Про Möbius Transform слышали когда-нибудь, например?

[Ward]

ИСН
Да слышал. Попытался, но ничего не вышло.
Пусть данная сумма равна $F(n)$, тогда из обращения Мебиуса имею, что $\varphi(n)=\sum \limits_{d\mid n}F(d)$

[ИСН]

Упс... Это в другую сторону оно хорошо, а в эту плохо.

[Sonic86]

Узнать, чему равна сумма, можно, спросив у суммы. Вычислите ее в нескольких точках. Чему равно $S(2), S(3), S(p), S(pq)$? ($p,q$ - простые)

[ИСН]

Короче, она выражается через разложение n на простые, примерно как сама фи, только чуть хитрее.

-- Пн, 2013-02-25, 21:01 --

Всё, что сказал Sonic86, сделайте сначала для нечётных. да.

[Руст]

Вообще такая сумма

$$\sum \limits_{d \mid n}\mu(d)\varphi\left(\frac{n}{d}\right)$$

есть свертка мультипликативных функций. Любая свертка мультипликативных функций сама является мультипликативной, т.е. достаточно их вычислить для значений $n=p^k$.

[Whitaker]

Можно наверное еще так:
Ваша сумма есть не что иное, как свертка Дирихле функций $\mu(n)$ и $\varphi(n)$. Ну пусть Ваша сумма есть $F(n)$, тогда она мультипликативна так как функции Мебиуса и Эйлера мультипликативны.
Очевидно, что $F(1)=1$ (из мультипликативности).
Пусть $n>1$ тогда $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$. Значит,

$$F(n)=F(p_1^{\alpha_1})F(p_2^{\alpha_2})\dots F(p_k^{\alpha_k})$$

Ну посчитаем для $\alpha>1$

$$F(p^{\alpha})=\sum \limits_{d \mid p^{\alpha}}\mu(d)\varphi\left(\frac{p^{\alpha}}{d}\right)=\mu(1)\varphi(p^{\alpha})+\mu(p)\varphi(p^{\alpha-1})+\dots+\mu(p^{\alpha})\varphi(1)=p^{\alpha-2}(p-1)^2$$

Нетрудно убедиться, что $F(p)=p-2$
Здесь я также пользуюсь тем, что $\mu(p^n)=0$ при $n\geqslant 2$
Осталось их перемножить и все

(Оффтоп)

Руст опередил меня