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

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

第一行写了如下的话：

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

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

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

$$
\begin{aligned}
&M \bmod 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{aligned}
$$

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

P90 欧几里得数的补充

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

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

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

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