質數有多少個？
阿恆
這是我在 GIMPS 香港羣組的網站上介紹質數的文章之一，這一篇分析質數的數量，前一篇是《質數——數學的原子》，下一篇是《甚麼是梅森質數？》。
10 之內的質數有 4 個：2, 3, 5, 7。
100 之內的質數有 25 個，100 之上當然還有很多質數，究竟質數有多少個？最大的質數是甚麼？
古希臘數學家歐幾里德 (Euclid) 用一個簡潔而漂亮的反證法，證明了質數有無限多個。
他首先假設質數的數量是有限的，姑且說這批質數就是 p1, p2, p3, …, pn，其餘數字都是合成數，歐幾里德跟着計算以下數字：
N = p1 x p2 x p3 x ...... x pn + 1
這個 N 比任何一個已知的質數都大，所以一定是一個合成數，即是說 N 一定可以被至少一個質數整除，但是 N 不論除以 p1, p2, ……. 乃至 pn，都得到餘數 1，換句話說，N 不能被任何一個已知的質數整除。N 既不能是質數（因為它比所有已知的質數都大），也不能是合成數（因為沒有一個質數能整除它），這時唯一的解釋，是開首的假設，即「質數的數量是有限的」有錯，結論是質數是無限的。