Делимость

[xmaister]

Дали задачу, что-то не могу сообразить. Как показать, что $n|\sum\limits_{d|n}\varphi (n)2^{\frac{n}{d}}$,$n\in\mathbb{N}$?

-- 11.09.2012, 15:05 --

Вообще сумма смахивает на число орбит, если считать по формуле Бернсайда. Проблема в том, что я не могу найти хорошую группу и ей на хорошее множество подействовать...

[nnosipov]

xmaister в сообщении #617391 писал(а):

Как показать, что $n|\sum\limits_{d|n}\varphi (n)2^{\frac{n}{d}}$

У Вас опечатка: речь идёт о сумме $S(n)=\sum_{d|n}\varphi(d)2^{n/d}$. Поскольку $S(n)$ мультипликативна (надеюсь), достаточно доказать делимость в случае $n=p^\alpha$, где $p$ --- простое число. А здесь индукция по $\alpha$ должна помочь (ну, или теорема Эйлера) --- уж как-нибудь доказать получится.

Хотя с чего ей быть мультипликативной? Нет, тут что-то другое имеется в виду.

Мультипликативна как свёртка двух мультипликативных функций.

[xmaister]

nnosipov в сообщении #617408 писал(а):

речь идёт о сумме $S(n)=\sum_{d|n}\varphi(d)2^{n/d}$

Да, спасибо.

Нашел вот что. Там внизу очень похожая формула получается. Т.е. получается так: действуем группой вращений $G \cong\mathbb{Z}_n$ на множество $X$, такое что $|X|=n!$. Но я не понимаю, какое должно выбираться множество, сколько элементов оно содержит? Просто я не так близко знаком с языком действий, поэтому туплю...