Problem 1621

Prove that when $n \equiv 1(\bmod k)$, for any $\chi \bmod k$ we have $\chi(n)=1$, so the left side of equation (37) is the number of characters modulo $k$. By Theorem 5, this number is $\varphi(k)$. This proves the first part of equation (37).

When $n \not\equiv 1(\bmod k)$, we must have $k>1$. If $(n, k)>1$, then the second part of equation (37) is clearly true. If $(n, k)=1$, by equation (33) we know that

there must be an $h(-1 \leqslant h \leqslant s)$ such that $0<\gamma^{(h)}(n)<c_{h}$, hence
$$\sum_{0 \leqslant S_{h}<c_{h}} \mathrm{e}^{2 \pi i_{h} \gamma^{(h)}(n) / c_{h}}=0 .$$

From the above two equations, we can deduce that the second part of equation (37) also holds in this case. Proof complete.
$$\begin{array}{l} \sum_{\chi \bmod k} \chi(n)=\sum_{0<l_{-1}<c_{-1}} \cdots \sum_{0 \leq l_{s}<c_{s}} \prod_{j=-1}^{s} \mathrm{e}^{2 \pi i_{j} \gamma^{(j)}(n) / c_{j}} \\ =\left\{\sum_{0 \leq l_{1}<c_{-1}} \mathrm{e}^{2 \pi i l_{-1} \gamma^{(-1)}(n) / c_{-1}}\right\} \cdots\left\{\sum_{0 \leq l_{s}<c_{s}} \mathrm{e}^{2 \pi i l_{l} \gamma^{(0)}(n) / c_{s}}\right\} . \end{array}$$