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看，用“不可約數”這一名詞更為貼切，但為了符合習慣，下面我們將總用“素數”這一術語，且假定它是正的.關于這兩個名詞的意義的討論可參看附錄二.研究素數的性質是數論的核心問題之一，至今對這一問題還了解不多，我們將在第八章對素數的個數作初步的討論.