注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.8 进一步的应用 的旁注。

P107 在证明什么

第三章未完成的证明在 P77.

P107 证明是得到的值的 $d$ 份复制

$$
jn \equiv kn \pmod m \Leftrightarrow j(n/d) \equiv k(n/d) \pmod {m/d}
$$

$$
0 \leq k < \frac m d
$$

这个式子看起来很变扭，我们改写一下大家就能知道到底在说明什么了：

$$
jn \equiv kn \pmod m \Leftrightarrow (j+\frac m d)n \equiv kn \pmod m
$$

这样就好看多了，我们说明了每 $\displaystyle \frac m d$ 个数循环一次，也就是说复制了 $d$ 份。

P108 最后得到了什么结论

改写一下书上话的顺序：

$k=jn' \pmod m \in [0..m)$，可以使得 $kn \pmod m = j \in [0..m)$

也就是说，对于每个 $j \in [0..m)$，我们求出了唯一的 $k \in [0..m)$，使得 $kn \pmod m = j$