素数有很多神奇的性质。我写5个在下面供大家欣赏。

1. 素数的个数无限多（不存在最大的素数）
  证明：反证法，假设存在最大的素数P，那么我们可以构造一个新的数2 * 3 * 5 * 7 * … * P + 1（所有的素数乘起来加1）。显然这个数不能被任一素数整除（所有素数除它都余1），这说明我们找到了一个更大的素数。

2. 存在任意长的一段连续数，其中的所有数都是合数（相邻素数之间的间隔任意大）
  证明：当0<a<=n时，n!+a能被a整除。长度为n-1的数列n!+2, n!+3, n!+4, …, n!+n中，所有的数都是合数。这个结论对所有大于1的整数n都成立，而n可以取到任意大。

3. 所有大于2的素数都可以唯一地表示成两个平方数之差。
   证明：大于2的素数都是奇数。假设这个数是2n+1。由于(n+1)^2=n^2+2n+1，(n+1)^2和n^2就是我们要找的两个平方数。下面证明这个方案是唯一的。如果素数p能表示成a^2-b^2，则p=a^2-b^2=(a+b)(a-b)。由于p是素数，那么只可能a+b=p且a-b=1，这给出了a和b的唯一解。

4. 当n为大于2的整数时，2^n+1和2^n-1两个数中，如果其中一个数是素数，那么另一个数一定是合数。
  证明：2^n不能被3整除。如果它被3除余1，那么2^n-1就能被3整除；如果被3除余2，那么2^n+1就能被3整除。总之，2^n+1和2^n-1中至少有一个是合数。

5. 如果p是素数，a是小于p的正整数，那么a^(p-1) mod p = 1。
  这个证明就有点麻烦了。
     首先我们证明这样一个结论：如果p是一个素数的话，那么对任意一个小于p的正整数a，a, 2a, 3a, …, (p-1)a除以p的余数正好是一个1到p-1的排列。例如，5是素数，3, 6, 9, 12除以5的余数分别为3, 1, 4, 2，正好就是1到4这四个数。
    反证法，假如结论不成立的话，那么就是说有两个小于p的正整数m和n使得na和ma除以p的余数相同。不妨假设n>m，则p可以整除a(n-m)。但p是素数，那么a和n-m中至少有一个含有因子p。这显然是不可能的，因为a和n-m都比p小。
    用同余式表述，我们证明了：
(p-1)! ≡ a * 2a * 3a * … * (p-1)a (mod p)
    也即：
(p-1)! ≡ (p-1)! * a^(p-1) (mod p)
    两边同时除以(p-1)!，就得到了我们的最终结论：
1 ≡ a^(p-1) (mod p)

     可惜最后这个定理最初不是我证明的。这是大数学家Fermat证明的，叫做Fermat小定理(Fermat's Little Theorem)。Euler对这个定理进行了推广，叫做Euler定理。Euler一生的定理太多了，为了和其它的“Euler定理”区别开来，有些地方叫做Fermat小定理的Euler推广。Euler定理中需要用一个函数f(m)，它表示小于m的正整数中有多少个数和m互素（两个数只有公约数1称为互素）。为了方便，我们通常用记号φ(m)来表示这个函数（称作Euler函数）。Euler指出，如果a和m互素，那么a^φ(m) ≡ 1 (mod m)。可以看到，当m为素数时，φ(m)就等于m-1（所有小于m的正整数都与m互素），因此它是Fermat小定理的推广。定理的证明和Fermat小定理几乎相同，只是要考虑的式子变成了所有与m互素的数的乘积：m_1 * m_2 … m_φ(m) ≡ (a * m_1)(a * m_2) … (a * m_φ(m)) (mod m)。我为什么要顺便说一下Euler定理呢？因为下面一句话可以增加我网站的PV：这个定理出现在了The Hundred Greatest Theorems里。