MathLabs
第 7/7 步：具体算例:为什么 N 本身不必是素数
上一步下一步
通俗地说

一个非常常见的误区是以为欧几里得声称数 N=p1cdotspn+1N = p_1 \\cdots p_n + 1 总是素数。动手算一算前几个例子就能看清为什么这不对:取前五个素数时 N 确实都是素数,但取到第六个素数时,N = 30031 就会分解成 59 × 509——而 59 和 509 依然都是我们列表之外的全新素数!

2⋅3⋅5⋅7⋅11⋅13+1=30031=59×5092 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509
详细分析

让我们在前几个素数上检验一下欧几里得的构造。当 L={2}L = \{2\} 时,N=2+1=3N = 2 + 1 = 3（素数）;当 L={2,3}L = \{2, 3\} 时,N=2⋅3+1=7N = 2 \cdot 3 + 1 = 7（素数）;当 L={2,3,5}L = \{2, 3, 5\} 时,N=30+1=31N = 30 + 1 = 31（素数）;当 L={2,3,5,7}L = \{2, 3, 5, 7\} 时,N=210+1=211N = 210 + 1 = 211（素数）;当 L={2,3,5,7,11}L = \{2, 3, 5, 7, 11\} 时,N=2310+1=2311N = 2310 + 1 = 2311（素数）。前五个例子很容易诱使读者误以为 N=p1⋯pn+1N = p_1 \cdots p_n + 1 永远是素数。

然而,到了第六个素数 L={2,3,5,7,11,13}L = \{2, 3, 5, 7, 11, 13\} 时,我们算出 N=2⋅3⋅5⋅7⋅11⋅13+1=30030+1=30031N = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30030 + 1 = 30031,它是一个合数,因为 30031=59×50930031 = 59 \times 509（正如哈代与赖特的经典教材《数论导引》§1.2中所强调的那样）。请注意欧几里得在第九卷命题20中的证明是如何轻松应对这一点的:欧几里得明确区分了“EFEF 要么是素数,要么不是”这两种情形;当 N=30031N = 30031 是合数时,它的素因数 q=59q = 59 和 q=509q = 509 都位于 {2,3,5,7,11,13}\{2, 3, 5, 7, 11, 13\} 之外,不仅给出了一个,反而给出了两个新素数。

本步骤中的术语
欧几里得数
形如 En=p1p2cdotspn+1E_n = p_1 p_2 \\cdots p_n + 1 的整数,即前 n 个素数的乘积加 1;有些欧几里得数是素数（如3、7、31、211、2311）,另一些则是合数（如30031 = 59 × 509）。
本步骤用到的知识
质数整除、因数与倍数
常见错误. 在考试或证明中切勿写成“因此 N=p1p2⋯pn+1N = p_1 p_2 \cdots p_n + 1 是一个新素数”。例如 2⋅3⋅5⋅7⋅11⋅13+1=30031=59×5092 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509 是合数,甚至如果从不连续的列表 {3,5}\{3, 5\} 出发,会得到 3⋅5+1=16=243 \cdot 5 + 1 = 16 = 2^4,其唯一素因数是 q=2q = 2。务必表述为:NN 具有至少一个不在列表中的素因数 qq。