1  2  3  4  5  6  7  8  Contents

質數 (Prime Number)

        兩個自然數m, n，若m可整除n（記為m|n）則m稱為n之因數。
例如：6的因數有1, 2, 3, 6。

        大家應該熟悉下面有關自然數的整除性質：

性質1. 1|m, m|m，這裡m是任何整數。
性質2. 如果m|n, n|m，那麼m = n。
性質3.（整數的傳遞性）如果m|n, n|k，則m|k。
性質4. 如果m|p, m|q，那麼m|pq。
性質5. 如果m|p，則m|np, n是任何整數。

        一個大於1的自然數，如果除了1和它本身之外，再也沒有其他因數，我們就稱它為質數（prime number）。例如：小於10的質數有2, 3, 5, 7。另外，我們知道除了2之外，所有的質數均為奇數。

 

如何判斷一個自然數是否為質數？

        因為如果n不是質數，就可以表示成兩個小於n的數a, b的乘積，假設ab，則 a² ab = n，於是可得到a。所以，如果n不是質數，那麼n一定有一個小於等於的因數。換句話說，如果n沒有任何小於等於的因數，那麼必定是質數。其實，我們只要確定n沒有任何小於等於的質因數（為質數的因數），就可以斷定n為質數。為什麼呢？

       在歐幾里得的《幾何原本》一書中，介紹了質數的概念，並證明了：
「整數的算術基本定理」

任何一個大於1的自然數 n，我們都可以分解 n成質因數乘積的形式。也就是說

n = ，其中p₁, p₂, … , p_k為n的質因數

而且，如果不考慮因數的次序，那麼這個分解是唯一的；
這就是n的標準分解式。
 

例如： 24 = 2 × 2 × 2 × 3 = 2³ × 3
            12345 = 3 × 5 × 823

        因此，要判斷一個大於1的自然數 n是否為質數，我們只要判斷n是否有質因數即可。綜合之前的討論，我們只要確定n沒有任何小於等於的質因數，就可以斷定n為質數。

       在《幾何原本》中，歐幾里得還證明了自然數中有無窮多個質數：

假設自然數中的質數為有限個，則其中一定有一個最大質數p。

<證明>

若令 n = 2 × 3 × 5 × 7 × 11 × 13 × … × p + 1
即n是所有的質數乘積加上1，則n一定大於p，因此若n是質數，就與假設p為最大質數矛盾。
然而，任何一個質數除n以後都會剩下1，即任何質數都無法整除n。也就是說，n沒有任何質因數，所以n是質數。
這表示一開始的假設錯誤，質數的個數不是有限個，而是無窮多個。

  

如何找出n的所有因數？

        若n為一自然數，將n寫成標準分解式n = ，其中p₁, p₂, … , p_k為n的質因數，我們可以利用這個式子找出n的所有因數。讓我們先看一個例子：

n = 72 = 2³ × 3²，
而72的因數是：1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72，
這些因數都是，其中b₁可以是0, 1, 2或3，b₂可以是0, 1或2，

例如：
        1 = 1 × 1 = 2⁰ × 3⁰，
        8 = 8 × 1 = 2³ × 3⁰，
       12 = 4 × 3 = 2² × 3¹，
       18 = 2 × 9 = 2¹ × 3²。
因此，若n = ，則n的因數為，b₁可以是0, 1,…, a₁中的任何數，而b₂可以是0, 1, … , a₂中的任何數；以此類推，b_k可以是0, 1, … , a_k中的任何數。

        前面我們找出72的所有因數，得知72共有12個因數。有沒有什麼方法可以不用找出所有因數，就能知道因數個數？

        若n = ，任選一組 (b₁, b₂, … , b_k) ，, … ,，就可以得到一個n的因數，而b₁有0, 1,…,等個選擇，b₂有個選擇，…， b_k有個選擇。所以n的因數個數為。