注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.3 素数的例子 的旁注。

P90 证明素数有无穷多个的补充

第一行写了如下的话：

这 $k$ 个素数没有一个能整除 $M$，因为他们都整除 $M-1$

这个理由看起来不怎么好理解，我们这么看见就好了：

$$M=2\times 3\times 5\times \cdots \times P_k+1$$

$$\begin{array}{rl}& Mmod{p}_i\\ =& M-p_i\lfloor M/p_i\rfloor \\ =& M-p_i\lfloor p_1\times \cdots \times p_{i-1}\times p_{i+1}\times \cdots \times p_k+\frac{1}{p_i}\rfloor \\ =& M-p_i\times p_1\times \cdots \times p_{i-1}\times p_{i+1}\times \cdots \times p_k\\ =& 1\end{array}$$

也就是 $M$ 模任何一个数都为 $1$。而最小的素数为 $2$，即不能被任何素数整除。

P90 欧几里得数的补充

为什么欧几里得数都互素？

因为每个数都是通过前面所有数所构造的，通过欧几里得算法寻找最大公约数，可以保证某个数和其前面的任何一个数都互素。

这句话等价于因为每个数会在构造后面的数中被用到，所以每个数和其之后的每一个数都互素，所以每个数和其余每个数都互素。

这其实就是一个逻辑游戏。