2.2　素数与合数

上面已经看到，有的数（例如12）有非显然约数，而有的数（例如7）只有显然约数.因此，从约数，即从整除的观点来看，整数有不同的特性，可以由此来对整数分类.这样的分类在整数中有特别重要的作用.

定义2（注：历史上素数是在自然数集合中定义的，所以总是正的.这里为了方便起见在整数集合中定义.）设整数p≠0，±1.如果它除了显然约数±1，±p外没有其他的约数，那么p就称为不可约数，也叫做素数.若a≠0，±1且a不是不可约数，则a称为合数.

当p≠0，±1时，由于p和-p必同为不可约数或合数，所以，以后若没有特别说明，不可约数（素数）总是指正的.例如

2，3，5，7，11，13，17，19，23，29，31

都是不可约数.这样，全体整数就被分为四类：0，±1，素数（不可约数），合数.

由定义立即推出（读者自己证明）：

定理3（i）a＞1是合数的充分必要条件是

a=de，1＜d＜a，1＜e＜a；

（ii）若d＞1，q是不可约数且d|q，则d=q.

定理4若a是合数，则必有不可约数p|a.

证由定义知a必有除数d≥2.设集合T由a的所有除数d≥2组成.由最小自然数原理知集合T中必有最小的自然数，设为p.p一定是不可约数.若不然，p≥2是合数，由定理3（i）知p必有除数d′：2≤d′＜p.显然d′属于T，这和p的最小性矛盾.证毕.

一个整数的除数如果是不可约数（即素数），那么这个除数就称为不可约除（因）数或素除（因）数.

关于合数与不可约数的关系有以下结论.

定理5设整数a≥2，那么a一定可表示为不可约数的乘积（包括a本身是不可约数），即

a=p₁p₂…p_s，

其中p_j（1≤j≤s）是不可约数.

证我们用反证法和最小自然数原理来证.假设结论不成立，则存在正整数≥2，它不可表示为不可约数的乘积.设所有这种正整数组成的集合为T，它是非空的.设n₀是T中的最小正整数.显见，n₀一定是合数（为什么），所以必有n₀=n₁n₂，2≤n₁，n₂＜n₀.由假设及n₀的最小性知，n₁，n₂不属于集合T，所以都可表示为不可约数的乘积：

n₁=p₁₁…p_1s，n₂=p₂₁…p_2r.

这样，就把n₀表示为不可约数的乘积：n₀=n₁n₂=p₁₁…p_1sp₂₁…p_2r.

这与假设矛盾.证毕.

当然，我们也可以用第二种数学归纳法来证明本定理，请读者自证.

例如，1260的不相同的不可约除数有2，3，5，7，共四个.

1260=2·2·3·3·5·7=2²·3²·5·7，

所以，1260共有6个不可约除数（包括相同的）.一个立刻会想到的问题是：定理5中的表示式在不计p_j（1≤j≤s）次序的意义下是否是唯一的.回答是肯定的，这就是著名的算术基本定理（见5定理2）.

从定理5容易推出（证明留给读者）：

推论6设整数a≥2.

（i）若a是合数，则必有不可约数p|a，p≤a^1/2；

（ii）若a有定理5中的表示式，则必有不可约数pa，p≤a^1/s.

例如，当a=1260时，s=6.它的不可约除数2就满足

2＜（1260）^1/6≈3.28….

推论6（i）给出了一个寻找不可约数的有效算法.例如，为了求出不超过100（或任给的正整数N）的所有不可约数，只要把1，及不超过100（或N）的所有正合数都删去.由推论6知，不超过100（或N）的正合数a必有一个不可约除数p≤a^1/2≤100^1/2=10（或N^1/2），因而，只要先求出不超过10（或N^1/2）的全部不可约数2，3，5，7（或p₁，p₂，…，p_s），然后，依次把不超过100（或N）的正整数中的除了2，3，5，7（或p₁，…，p_s）以外的2的倍数、3的倍数、5的倍数、7的倍数（或p₁的倍数，…，p_s的倍数）全部删去，就删去了不超过100（或N）的全部正合数，剩下的正好就是不超过100（或N）的全部不可约数.具体做法见下表，取N=100：

由上表可以看出，没有删去的数是

2，3，5，7，11，13，17，19，23，29，31，37，41，43，

47，53，59，61，67，71，73，79，83，89，97，

共有25个，它们就是不超过100的全部不可约数（素数）.从这不超过100的25个素数出发，重复上面的做法，就可找出不超过100²=10000的全部素数.这种寻找不可约数的方法，通常叫做Eratosthenes筛法.

数学中的一个著名的定理是：

定理7不可约数（素数）有无穷多个.

证用反证法.假设只有有限个不可约数（注意：已约定不可约数一定是正的），它们是q₁，…，q_k.考虑a=q₁q₂…q_k+1.显见，a＞2及a>q_i，1≤i≤k.由假设知a为合数.由定理4知必有不可约数pa.由假设知p必等于某个q_j，因而p=q_j一定整除a-q₁q₂…q_k=1，但不可约数q_j≥2，这是不可能的，矛盾.因此，假设是错误的，即不可约数必有无穷多个.证毕.

设q₁=2，q₂=3，q₃=5，q₄，q₅，…是全体不可约数（素数）按大小顺序排成的序列以及

Q_k=q₁q₂…q_k+1.

由直接计算得（q_j已在上面求出）：

Q₁=3，Q₂=7，Q₃=31，Q₄=211，Q₅=2311，Q₆=59·509，Q₇=19·97·277，Q₈=347·27953，Q₉=317·703763，Q₁₀=331·571·34231，

这里前五个是不可约数，后五个是合数，但Q_k的不可约除数都比q_k更大.至今还不知道是否有无穷多个k使Q_k是不可约数，也不知道是否有无穷多个k使Q_k是合数.

在初等数论书中，大多用“素数”这一术语而不用“不可约数”.虽然，从给出的定义2看，用“不可约数”这一名词更为贴切，但为了符合习惯，下面我们将总用“素数”这一术语，且假定它是正的.关于这两个名词的意义的讨论可参看附录二.研究素数的性质是数论的核心问题之一，至今对这一问题还了解不多，我们将在第八章对素数的个数作初步的讨论.