注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 节中的项链问题的旁注。
P116 $mN(m,n)$
$$
m N(m, n)=\sum_{a_{0}, \ldots, a_{m-1} \in S_{n}} \sum_{0 \leqslant k<m}\left[a_{0} \ldots a_{m-1}=a_{k} \ldots a_{m-1} a_{0} \ldots a_{k-1}\right]
$$
这个式子没有问题。注意 $k$ 的下标，$k$ 包含了 $0$，所以不支持循环位移的数也会被计入。
我们来考察一下这个和式到底计入了那些值：
- $k=0$，不考虑循环位移产生的影响，完全对 $S_n$ 进行枚举，贡献为 $n^m$
- $0<k<m$，考虑循环位移产生的影响，贡献为 $mN(m,n)-n^m$
P116 引理回顾
这页的下半部分在阐述循环位移的等价情况。这里我们回顾一下 4.8 节证明的引理。
对于 $\bmod m$ 来说，$0 \bmod m, k \bmod m, 2k \bmod m, \cdots, (m-1)k\bmod m$ 为 $0, d, 2d, \cdots, m-d$ 的排列的 $d$ 次循环。
P117 $N(m,n)$ 推导补充
$$
\begin{aligned}
{N}({m}, {n})
&=\frac 1 m\sum_{0 \leqslant {k}<{m}} n^{\gcd(m,k)} \\
&=\frac 1 m\sum_{0 \leqslant {k}<{m}}\sum_{d\backslash m} n^{d}[d=\gcd(m,k)] \\
&=\frac 1 m\sum_{d\backslash m} \sum_{0 \leqslant {k}<{m}}n^{d}[d=\gcd(m,k)] \\
&=\frac{1}{{m}} \sum_{{d} \backslash {m}} {n}^{{d}} \sum_{0 \leqslant {k}<{m}}[{d}=\operatorname{gcd}({k}, {m})] \\
&=\frac{1}{{m}} \sum_{{d} \backslash {m}} n^{{d}} \sum_{0 \leqslant {k}<{m}}[{k} / {d} \perp {m} / {d}] \\
&=\frac{1}{{m}} \sum_{{d} \backslash {m}} n^{{d}} \sum_{0 \leqslant {k}<{m} / {d}}[{k} \perp {m} / {d}]
\end{aligned}
$$
P119 归纳证明的补充
我们还需要证明当 $m=p^k$ 时，
$$
\sum_{d\backslash m} \varphi(d) n^{m/d} \equiv 0 \pmod m
$$
证明：
$$
\begin{aligned}
\sum_{d\backslash m} \varphi(d) n^{m/d} &= n^{p^k} + \varphi(p) n^{p^{k-1}} + \cdots + \varphi(p^{k-1})n^p + \varphi(p^k)n \\
&=n^{p^k} + (p^2-p)n^{p^{k-1}} + \cdots + (p^{k-2}-p^{k-1})n^p + (p^k-p^{k-1})n \\
&=(n^{p^k}-n^{p^{k-1}}) + p(n^{p^{k-1}}-n^{p^{k-2}}) + \cdots + p^{k-1}(n^p-n) + p^k
\end{aligned}
$$
（上面的每一步都可以用归纳法证得）
接下来，我们将要证明：
$$
n^{p^k}-n^{p^{k-1}} \equiv 0 \pmod {p^k}
$$
$$
n^{p^{k-1}}-n^{p^{k-2}} \equiv 0 \pmod {p^{k-1}}
$$
$$
\cdots
$$
$$
n^p - n \equiv 0 \pmod {p^{k}}
$$
为了证明这个，我们可以用归纳的方式以及二项式展开证明下面这个结论：
$$
n^{p^k} = n^{p^{k-1}} + p^k \mathfrak{O}, \mathfrak O \in \mathbb Z
$$
P119 为什么内和对 $m_2$ 同余于 $0$?
考察和式
$$
\sum_{d_1\backslash m_1} \varphi(d_1) \left ( \sum_{d_2 \backslash m_2} \varphi(d_2) (n^{m_1/d_1}) ^ {m_2/d_2} \right)
$$
这里有
$$
N(m_2, n^{m_1 / d_1}) = \sum_{d_2 \backslash m_2} \varphi(d_2) (n^{m_1/d_1}) ^ {m_2/d_2}
$$
根据假设
$$
N(m_2, n') \equiv 0 \pmod {m_2}, n'\in\mathbb Z
$$
故内和对 $m_2$ 同余于 $0$.
