Посчитать сумму

[Highwind]

Вспомнил какую-то задачку. Вроде она несложная, но решение я сам плохо помню.

Пусть $\zeta = \exp \frac{{2\pi i}}{n}$, $S_n = \sum\limits_{\left( {k,\,n} \right) = 1} {\zeta ^k } $. Вычислить $S_{70}$

[Brukvalub]

чисел, взаимно простых с 70, бесконечно много, то есть Вы предлагаете просуммировать ряд, общий член которого имеет равный единице модуль, и, поэтому, не стремится к нулю. В каком же тогда смысле нужно понимать суммирование?

[Юстас]

Видимо имелось ввиду сумма по $k\leqslant n$. Тогда нужно заметить, что $\sum\limits_{k=1}^{k=n}\zeta^k=0$, и тогда искомая сумма $S_n=-(S(2)+S(5)+S(7)-S(10)-S(14)-S(35)+S(70)$, где $S(i))$ - сумма слагаемых исходной суммы, таких что $k$ кратно $i$. Каждая из этих сумм есть геометрическая програссия и легко считается.

[Highwind]

Юстас писал(а):

Видимо имелось ввиду сумма по $k\leqslant n$

Да, я прошу меня простить, именно это и имелось в виду.

[maxal]

Используя принцип включения-исключения, получаем формулу

$$\sum_{k=1\atop (k,n)=1}^n \zeta^k = \sum_{d\mid rad(n)} \mu(d) \sum_{k=1}^{n/d} \zeta^{kd},$$

где $rad(n)$ - это произведение различных простых делящих $n,$ $\mu$ - функция Мёбиуса.
Нетрудно видеть, что внутренняя сумма равна 0 всегда, за исключением случая $d=n$, когда она равна 1.

Поэтому $S_n = \mu(n),$ ну и $S_{70} = \mu(70) = -1.$