素?cái)?shù)有很多神奇的性質(zhì)。我寫(xiě)5個(gè)在下面供大家欣賞。

1. 素?cái)?shù)的個(gè)數(shù)無(wú)限多（不存在最大的素?cái)?shù)）
  證明：反證法，假設(shè)存在最大的素?cái)?shù)P，那么我們可以構(gòu)造一個(gè)新的數(shù)2 * 3 * 5 * 7 * … * P + 1（所有的素?cái)?shù)乘起來(lái)加1）。顯然這個(gè)數(shù)不能被任一素?cái)?shù)整除（所有素?cái)?shù)除它都余1），這說(shuō)明我們找到了一個(gè)更大的素?cái)?shù)。

2. 存在任意長(zhǎng)的一段連續(xù)數(shù)，其中的所有數(shù)都是合數(shù)（相鄰素?cái)?shù)之間的間隔任意大）
  證明：當(dāng)0<a<=n時(shí)，n!+a能被a整除。長(zhǎng)度為n-1的數(shù)列n!+2, n!+3, n!+4, …, n!+n中，所有的數(shù)都是合數(shù)。這個(gè)結(jié)論對(duì)所有大于1的整數(shù)n都成立，而n可以取到任意大。

3. 所有大于2的素?cái)?shù)都可以唯一地表示成兩個(gè)平方數(shù)之差。
   證明：大于2的素?cái)?shù)都是奇數(shù)。假設(shè)這個(gè)數(shù)是2n+1。由于(n+1)^2=n^2+2n+1，(n+1)^2和n^2就是我們要找的兩個(gè)平方數(shù)。下面證明這個(gè)方案是唯一的。如果素?cái)?shù)p能表示成a^2-b^2，則p=a^2-b^2=(a+b)(a-b)。由于p是素?cái)?shù)，那么只可能a+b=p且a-b=1，這給出了a和b的唯一解。

4. 當(dāng)n為大于2的整數(shù)時(shí)，2^n+1和2^n-1兩個(gè)數(shù)中，如果其中一個(gè)數(shù)是素?cái)?shù)，那么另一個(gè)數(shù)一定是合數(shù)。
  證明：2^n不能被3整除。如果它被3除余1，那么2^n-1就能被3整除；如果被3除余2，那么2^n+1就能被3整除。總之，2^n+1和2^n-1中至少有一個(gè)是合數(shù)。

5. 如果p是素?cái)?shù)，a是小于p的正整數(shù)，那么a^(p-1) mod p = 1。
  這個(gè)證明就有點(diǎn)麻煩了。
     首先我們證明這樣一個(gè)結(jié)論：如果p是一個(gè)素?cái)?shù)的話，那么對(duì)任意一個(gè)小于p的正整數(shù)a，a, 2a, 3a, …, (p-1)a除以p的余數(shù)正好是一個(gè)1到p-1的排列。例如，5是素?cái)?shù)，3, 6, 9, 12除以5的余數(shù)分別為3, 1, 4, 2，正好就是1到4這四個(gè)數(shù)。
    反證法，假如結(jié)論不成立的話，那么就是說(shuō)有兩個(gè)小于p的正整數(shù)m和n使得na和ma除以p的余數(shù)相同。不妨假設(shè)n>m，則p可以整除a(n-m)。但p是素?cái)?shù)，那么a和n-m中至少有一個(gè)含有因子p。這顯然是不可能的，因?yàn)閍和n-m都比p小。
    用同余式表述，我們證明了：
(p-1)! ≡ a * 2a * 3a * … * (p-1)a (mod p)
    也即：
(p-1)! ≡ (p-1)! * a^(p-1) (mod p)
    兩邊同時(shí)除以(p-1)!，就得到了我們的最終結(jié)論：
1 ≡ a^(p-1) (mod p)

     可惜最后這個(gè)定理最初不是我證明的。這是大數(shù)學(xué)家Fermat證明的，叫做Fermat小定理(Fermat's Little Theorem)。Euler對(duì)這個(gè)定理進(jìn)行了推廣，叫做Euler定理。Euler一生的定理太多了，為了和其它的“Euler定理”區(qū)別開(kāi)來(lái)，有些地方叫做Fermat小定理的Euler推廣。Euler定理中需要用一個(gè)函數(shù)f(m)，它表示小于m的正整數(shù)中有多少個(gè)數(shù)和m互素（兩個(gè)數(shù)只有公約數(shù)1稱為互素）。為了方便，我們通常用記號(hào)φ(m)來(lái)表示這個(gè)函數(shù)（稱作Euler函數(shù)）。Euler指出，如果a和m互素，那么a^φ(m) ≡ 1 (mod m)。可以看到，當(dāng)m為素?cái)?shù)時(shí)，φ(m)就等于m-1（所有小于m的正整數(shù)都與m互素），因此它是Fermat小定理的推廣。定理的證明和Fermat小定理幾乎相同，只是要考慮的式子變成了所有與m互素的數(shù)的乘積：m_1 * m_2 … m_φ(m) ≡ (a * m_1)(a * m_2) … (a * m_φ(m)) (mod m)。我為什么要順便說(shuō)一下Euler定理呢？因?yàn)橄旅嬉痪湓捒梢栽黾游揖W(wǎng)站的PV：這個(gè)定理出現(xiàn)在了The Hundred Greatest Theorems里。