注:本节内容为《具体数学》(原书第二版) 第四章 数论 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$,所以不支持循环位移的数也会被计入。

我们来考察一下这个和式到底计入了那些值:

  1. $k=0$,不考虑循环位移产生的影响,完全对 $S_n$ 进行枚举,贡献为 $n^m$
  2. $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$.

最后修改:2022 年 03 月 13 日 02 : 12 PM
真的不买杯奶茶嘛....qwq