Revision 53138 of "素数公式" on zhwikibooks

素数，就是按照乘法性质把自然数分为三类。

一“自然数1”。

二，素数，就是除了1和自己以外没有任何数可以整除，例如2,3,5,7，。。。

三，合数。至少有两个素因子的乘积。

素数是自然数中最重要的概念，是自然数的基本粒子，两千年以来，数论学家最重要的任务就是寻找一个可以产生所有素数的公式。为此，人们耗尽了巨大心血，始终没有成功。现在人们是利用一种筛法创造的公式。
== 公式的来历 ==
公元前300年古希腊的埃拉托斯特尼创造了一种筛法，可以产生任意大的数以内的全部素数： 要得到不大于某个自然数n的所有素数，只要在2—n中将不大于<math>\sqrt{n}</math>素数的倍数全部划去即可。
=== 上述筛法可以总结为 ===
# 如果n是合数，则它有一个因子d满足1<d≤<math>\sqrt{n}</math>。
# 若自然数n不能被不大于<math>\sqrt{n}</math>任何素数整除，则n是一个素数。（这句话本身就是一个公式。这个公式可以一个不漏地产生所有素数，而不会混入一个合数）。

可以把2的汉字内容等价转换成为英语字母表示：

<math>n=p_{1}m_{1}+a_{1}=p_{2}m_{2}+a_{2}=\dots=p_{k}m_{k}+a_{k}.</math>(1)

其中 <math>p_{1},p_{2},\dots,p_{k}</math>表示顺序素数2，3，5，....。<math>a</math>≠0。

即n≠<math>2m_{1}+0</math>，<math>3m_{2}+0</math>，<math>5m_{3}+0</math>，...，<math>p_{k}m_{k}+0</math>形。若<math>n<P^{2}_{k+1}</math>,则n是一个素数。 

我们可以把（1）式内容等价转换同余式组表示：

<math>n \equiv a_1 \pmod{p_1}, n \equiv a_2 \pmod{p_2}, \dots, n \equiv a_k \pmod{p_k}</math>（2）

由于（2）的模<math>p_{1}</math>,<math>p_{2}</math>,...,<math>p_{k}</math> 两两互素，根据孙子定理(中国剩余定理）知，对于给定的<math>a_{1}</math>,<math>a_{2}</math>,...,<math>a_{k}</math>，（2）式在<math>p_{1}</math><math>p_{2}</math>...<math>p_{k}</math>范围内有唯一解。   
===範例===
例如：
k=1时，<math>n=2m_{1}+1</math>，解得n=3，5，7。求得了（3，3²）区间的全部素数。
   
k=2时，<math>n=2m_{1}+1=3m_{2}+1</math>，解得n=7，13，19；
 
       <math>n=2m_{1}+1=3m_{2}+2</math>，解得n=5，11，17，23。
求得了（5，5²）区间的全部素数。
   
  {| class="wikitable"
|-
! k=3时!!<math>5m_{3}+1</math>  !! <math>5m_{3}+2</math> !! <math>5m_{3}+3</math> !! <math>5m_{3}+4</math>
|-
| <math>n=2m_{1}+1=3m_{2}+1=</math> || 31 || 7,37 || 13,43 || 19
|-
| <math>n=2m_{1}+1=3m_{2}+2=</math> || 11,41 || 17,47 || 23 || 29
|}
求得了（7，7²）区间的全部素数。   
仿此下去可以一个不漏地求的给定数以内的全部素数。

'''数论中几乎所有重大问题都与埃拉托斯特尼筛法有关。'''

=== [[孪生质数]]的公式 ===
利用上述定理，可以得到以下的结论：“若[[自然数]]<math>z+1</math>与<math>z-1</math>都不能被任何不大于<math>\sqrt{z+1}</math>的质数
[[整除]]，则<math>z + 1</math>与<math>z - 1</math>都是质数”。
用数学的语言表示以上的结论，就是：
:存在一组自然数<math>b_{1}, b_{2} \cdot , b_{k}</math>，使得

:<math>z=p_{1}m_{1}+b_{1}=p_{2}m_{2}+b_{2}=\dots=p_{k}m_{k}+b_{k} \qquad \qquad \qquad \cdots \qquad (3)</math>

其中 <math>p_{1},p_{2},\dots,p_{k}</math>表示从小到大排列时的前''k''个质数：2，3，5，....。并且满足
:<math>\forall 1 \le i  \le k, \ \ 0 < b_{i} < p_{i}, \ b_{i} \neq 1, \ b_{i} \neq p_{i} - 1.</math>

这样解得的自然数<math>z</math>如果满足<math>z<p^{2}_{K+1}-1</math>,则<math>z + 1</math>与<math>z - 1</math>是一对孪生质数。
我们可以把（3）式的内容等价转换成为同余方程组表示：
:<math>z \equiv b_1 \pmod{p_1}, z \equiv b_2 \pmod{p_2}, \dots, z \equiv b_k \pmod{p_k} \qquad \qquad \qquad  \cdots \qquad (4)</math>

由于（4）的模<math>p_{1}</math>,<math>p_{2}</math>,...,<math>p_{k}</math>都是质数，因此两两互质，根据[[孙子定理]]（中国剩余定理）知，对于给定的<math>b_{1}, b_{2} \cdot , b_{k}</math>，（4）式有唯一一个小于<math>p_{1} p_{2} \cdots p_{k}</math>的正整数解。

例如k=1时，<math>z=2m_{1}+0</math>，解得<math>z=4, 6</math>。由于<math>6<3^2-1</math>，所以可知<math>4+1</math>与<math>4-1</math>、<math>6+1</math>与<math>6-1</math>都是孪生质数。这样就求得了[[区间]]<math>(3, 3^2)</math>里的全部孪生质数对。
 
又比如k=2时，列出方程<math>z=2m_{1}+0=3m_{2}+0</math>，解得<math>z=6, 12, 18</math>。由于<math>18</math><5²-1，所以<math>12+1</math>与<math>12-1</math>、<math>18+1</math>与<math>18-1</math>都是了孪生质数。由于这已经是所有可能的<math>b_{1}, b_{2} \cdot , b_{k}</math>值，所以这样就求得了区间<math>(5, 5^2)</math>的全部孪生质数对。

{| class="wikitable"
|-
! k=3时 !! <math>5m_{3}+0</math> !! <math>5m_{3}+2</math>  !! <math>5m_{3}+3</math> 
|-
| <math>z=2m_{1}+0=3m_{2}+0=</math> || 30 || 12,42 || 18
|}30±1和42±1都是[[孪生素数]].
由于这已经是所有可能的<math>b_{1}, b_{2} \cdot , b_{k}</math>值，所以这样就求得了区间<math>(7, 7^2)</math>的全部孪生质数对。
{| class="wikitable"
|-
! k=4时 !! <math>7m_{4}+0</math> !! <math>7m_{4}+2</math> !! <math>7m_{4}+3</math> !! <math>7m_{4}+4</math> !! <math>7m_{4}+5</math>
|-
| <math>z=2m_{1}+0=3m_{2}+0=5m_{3}+0</math>= || 210 || 30 || 150 || 60 || 180
|-
| <math>z=2m_{1}+0=3m_{2}+0=5m_{3}+2</math>= || 42 || 72 || 192 || 102 || 12
|-
| <math>z=2m_{1}+0=3m_{2}+0=5m_{3}+3</math>= || 168 || 198 || 108 || 18 || 138
|}
小于121-1的8个解z±1就是是[[孪生素数]].
由于这已经是所有可能的<math>b_{1}, b_{2} \cdot , b_{k}</math>值，所以这样就求得了区间<math>(11, 11^2)</math>的全部孪生质数对。

仿此下去可以一个不漏地求得任意大的数以内的全部孪生质数对。对于所有可能的<math>b_{1}, b_{2} \cdot , b_{k}</math>值，(3)和(4)式在<math>p_{1}</math><math>p_{2}</math>...<math>p_{k}</math>范围内，有
：（<math>p_{1}-1</math>）（<math>p_{2}-2</math>）(<math>p_{3}-2</math>)...（<math>p_{k}-2</math>）。（**）个解。
孪生质数猜想就是在k值任意大时（3）和（4）式都有小于<math>p^{2}_{k+1}-1</math>的解。实际上，孪生素数猜想已经转入初等数论的范围。（参见参考文献6）

=== [[黎曼猜想]]的[[素数公式]]与[[埃拉托斯特尼筛法]]关系 ===
参见《素数之恋》第100页德比希尔著。
<math>\zeta (s) = \sum^{\infin}_{n=1} { 1 \over {n^s}}</math>
: <math> \zeta(s) = \frac{1}{1^s} + \frac{1}{2^s} + \frac{1}{3^s} + \frac{1}{4^s} + \cdots </math> 。（5）
在等号两边乘以<math>\frac{1}{2^s}</math>，由幂运算规则得到。
<math>\frac{1}{2^s} \zeta(s) = \frac{1}{2^s} + \frac{1}{4^s} + \frac{1}{6^s} + \frac{1}{8^s} + \cdots </math>。（6）
  　　我们从第（6）式子减去第二个式子，在左边我有一个<math> \zeta(s)</math>. 
又有它的<math>\frac{1}{2^s}</math>,做减法得：
（<math>1-\frac{1}{2^s}</math>）<math> \zeta(s) =1+ \frac{1}{3^s} + \frac{1}{5^s} + \frac{1}{7^s} + \frac{1}{9^s} + \frac{1}{11^s} + \frac{1}{13^s} + \frac{1}{15^s}+\cdots </math>。（7）

 　这个减法从那个无穷和中去掉了所有偶数项。 
　　现在我们在等号两边乘以<math>\frac{1}{3^s}</math>,而3是右边第一个还没有去掉的数：

<math>\frac{1}{3^s}</math>（<math>1-\frac{1}{2^s} </math>）<math>\zeta(s) = \frac{1}{3^s} + \frac{1}{9^s} + \frac{1}{15^s} + \frac{1}{21^s} + \frac{1}{27^s} + \frac{1}{33^s} + \frac{1}{39^s} +\cdots </math>。（8）

 　　 　　我们再做减法得： 

（<math>1-\frac{1}{3^s}</math>）（<math>1-\frac{1}{2^s}</math>）<math> \zeta(s) =1+ \frac{1}{5^s} + \frac{1}{7^s} + \frac{1}{11^s} + \frac{1}{13^s} + \frac{1}{17^s} + \frac{1}{19^s} + \frac{1}{23^s}+\cdots </math>。（9）

　　　　3的所有倍数都从那个无穷和中消失了，右边还有第一个没有被去掉的数是5，如果我们两边都乘以<math>\frac{1}{5^s}</math>,结果是：

<math>\frac{1}{5^s}</math>（<math>1-\frac{1}{3^s}</math>）（<math>1-\frac{1}{2^s}</math>）<math> \zeta(s) = \frac{1}{5^s} + \frac{1}{25^s} + \frac{1}{35^s} + \frac{1}{55^s} + \frac{1}{65^s} + \frac{1}{85^s} + \frac{1}{95^s}+\cdots </math>。（10）

从前面那个式子减去这个式子得：

（<math>1-\frac{1}{5^s}</math>）（<math>1-\frac{1}{3^s}</math>）（<math>1-\frac{1}{2^s}</math>）<math> \zeta(s) = 1+\frac{1}{7^s} + \frac{1}{11^s} + \frac{1}{13^s} + \frac{1}{17^s} + \frac{1}{19^s} + \frac{1}{23^s} + \frac{1}{29^s}+\cdots </math>。（11）

　　我们继续下去，对于大于1的任意s，左边对每一个带括号的表达式，并向右边一直继续下去，对这个式子的两边都依次逐个除以这些括号，我们得到：

<math>\zeta(s) = \prod_{p} \frac{1}{1-p^{-s}}</math> =<math> \frac{1}{1-2^{-s}}\cdot\frac{1}{1-3^{-s}}\cdot\frac{1}{1-5^{-s}}\cdot\frac{1}{1-7^{-s}}\cdot\frac{1}{1-11^{-s}} \cdots \frac{1}{1-p^{-s}} \cdots.</math>。（12）

　即： 　　（5）式=（12）式 　

　'''这就是重复埃拉托塞尼筛法的过程'''。也就是说，[[黎曼猜想]]不是凭空出现的，而是有埃拉托斯特尼筛法作为基础的。

== 用途 ==
=== 哥德巴赫猜想的合理框架 ===
（参见参考文献5）
上面的孪生素数公式是z+1与z-1，与此相似：
怎样使得两个自然数相加和相减都成为素数，即N+X成为素数，N-X也是素数。
根据除法算式定理：“给定正整数a和b，b≠0，存在唯一整数q和r（0≤r＜b），使a=bq+r”。
再根据同余定理：“每一整数恰与0,1,2,3，...，m-1中一数同余（mod m）”。
所以，任给一个自然数N(N>4)，都可以唯一表示成为：

<math>N=p_{1}m_{1}+e_{1}=p_{2}m_{2}+e_{2}=\dots=p_{k}m_{k}+e_{k}.</math>(13)

其中 <math>p_{1},p_{2},\dots,p_{k}</math>表示顺序素数2，3，5，....。<math>e_{i}=0,1,2,...,P_{i}-1</math>。
<math>\frac{p^{2}_{k}}{2}</math> < N < <math>\frac{p^{2}_{k+1}}{2}</math>
现在问，是否存在X,

<math>X=p_{1}h_{1}+f_{1}=p_{2}h_{2}+f_{2}=\dots=p_{k}h_{k}+f_{k}.</math>（14）

<math>f_{i}</math>≠<math>e_{i}</math>，
<math>f_{i}</math>≠<math>p_{i}-e_{i}</math>。
如果X<N-2，则N+X与N-X都是素数，因为它们符合（1）（2）式。
=== 範例 ===
設N=20，<math>20=2m_{1}+0=3m_{2}+2=5m_{5}+0</math>；
<math>\frac{5^{2}}{2}</math> < 20 < <math>\frac{7^{2}}{2}</math>

 <math>e_{1}=0</math>,<math>e_{2}=2</math>,<math>e_{3}=0</math>.
{| class="wikitable"
|-
! 构造x !! <math>5h_{3}+1</math> !! <math>5h_{3}+2</math> !!<math>5h_{3}+3</math>  !! <math>5h_{3}+4</math>
|-
| <math>X=2h_{1}+1=3h_{2}+0=</math>  ||   21 ||   27 ||   3 ||   9
|-
|
<math>f_{i}</math>≠<math>e_{i}</math>，<math>f_{i}</math>≠<math>p_{i}-e_{i}</math>
 || <math>f_{1}=1</math>，<math>f_{2}=0</math>，<math>f_{3}=1</math>.
 || <math>f_{1}=1</math>，<math>f_{2}=0</math>，<math>f_{3}=2</math>.
 || <math>f_{1}=1</math>，<math>f_{2}=0</math>，<math>f_{3}=3</math>.
 || <math>f_{1}=1</math>，<math>f_{2}=0</math>，<math>f_{3}=4</math>.
|}
四个解是：21，27，3，9。小于N-2的X有3和9，我们得知，20+3与20-3是一对素数；20+9与20-9是一对素数。
这就是利用素数判定法则：最小剩余不为零，并且<math>N+X<P^{2}_{k+1}</math>,则N+X与N-X是一对素数。
因为'''（N+X）+（N-X）=2N。这就是著名的哥德巴赫猜想猜想'''，
'''我们需要证明（14）式必然有小于N-2的解，尽管我们现在不能证明它'''。
素数判定法则和埃拉托斯特尼筛法的普遍公式已经为哥德巴赫猜想提供了合理框架，并且把问题转入到初等数论范围。
==证明素数无穷多==
假如最大的素数是<math>p_{k}</math>，那么，对于下面式子
 
  <math>n=p_{1}m_{1}+a_{1}=p_{2}m_{2}+a_{2}=\dots=p_{k}m_{k}+a_{k}.</math>(15)   
<math>a</math>≠0。
n大于 <math>p_{1},p_{2},\dots,p_{k}</math>，并且与<math>p_{1},p_{2},\dots,p_{k}</math>互素，根据
假设<math>p_{k}</math>是最大素数，那么n一定是合数，但是，我们知道，不存在于所有素数互素的合数，所以，原来
假设<math>p_{k}</math>是最大素数是错误的。证明完毕。

== 参考 ==
# ''{{lang|el|Κοσκινον Ερατοσθενους}} or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers'', by the Rev. Samuel Horsley, F. R. S., Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.
# 《谈谈素（质）数表达式》【中等数学】1999年2期26页。
# 《关于一个寻找素数方法的理论依据》【中等数学】2001年4期14页。
# 《素数个数问题的三种新证法》【中等数学】2001年1期19页。
# 《从台尔曼公式谈起》【中等数学】2002年5期18页。
# 《孪生质数公式》【中等数学】2000年1期24页
# 《素数之恋》德比希尔著