Difference between revisions 50778 and 50779 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是一个素数。（这句话本身就是一个公式。这个公式可以一个不漏地产生所有素数，而不会混入一个合数）。
⏎
⏎
可以把3的汉字内容等价转换成为英语字母表示：
⏎
⏎
<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，....。a≠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²）区间的全部素数。   ⏎
{| class="wikitable"
|-
! k=4时 !!<math>7m_{4}+1</math>  !! <math>7m_{4}+2</math>  !! <math>7m_{4}+3</math>  !! <math>7m_{4}+4</math>  !! <math>7m_{4}+5</math>  !! <math>7m_{4}+6</math> 
|-
| <math>n=2m_{1}+1=3m_{2}+1=5m_{3}+1</math> || 1 || 121 || 31 || 151 || 61 || 181
|-
| <math>n=2m_{1}+1=3m_{2}+1=5m_{3}+2</math> || 127 || 37 || 157 || 67 || 187 || 97
|-
| <math>n=2m_{1}+1=3m_{2}+1=5m_{3}+3</math> || 43 || 163 || 73 || 193 || 103 || 13
|-
| <math>n=2m_{1}+1=3m_{2}+1=5m_{3}+4</math> || 169 || 79 || 199 || 109 || 19 || 139
|-
| <math>n=2m_{1}+1=3m_{2}+2=5m_{3}+1</math> || 71 || 191 || 101 || 11 || 131 || 41
|-
| <math>n=2m_{1}+1=3m_{2}+2=5m_{3}+2</math> || 197 || 107 || 17 || 137 || 47 || 167
|-
| <math>n=2m_{1}+1=3m_{2}+2=5m_{3}+3</math> || 113 || 23 || 143 || 53 || 173 || 83
|-
| <math>n=2m_{1}+1=3m_{2}+2=5m_{3}+4</math> || 29 || 149 || 59 || 179 || 89 || 209
|}
　求得了（11,11²）区间的全部素数（小于121的26个数，除了1以外全部是素数）。 　 　　
   仿此下去可以求得任意大的数以内的全部素数。并且一个不漏地求得。由孙子定理知，对于所有可能的
<math>a_{1}, a_{2} \cdot , a_{k}</math>值，(1)和(2)式在<math>p_{1}</math><math>p_{2}</math>...<math>p_{k}</math>
范围内，有（<math>p_{1}-1</math>）（<math>p_{2}-1</math>）(<math>p_{3}-1</math>)...（<math>p_{k}-1</math>）个解.
两式的本质是从<math>p_{1}</math>,<math>p_{2}</math>,...,<math>p_{k}</math> 中剔除掉<math>p_{i}m_{i}</math>（m≥1)
的合数，这一点与埃拉托塞筛法不同，埃氏筛是用<math>p_{1}</math>,<math>p_{2}</math>,...,<math>p_{k}</math> 去筛<math>p^{2}_{k+1}</math>以内的合数，剩下的就是<math>p^{2}_{k+1}</math>以内的素数了。例如用2，3，5，去筛49以内的
合数，剩下的就是（7，7²）区间的素数了。但是，（1）（2）式连同<math>p_{1}</math>,<math>p_{2}</math>,...,<math>p_{k}</math>也筛掉了。
切比雪夫证明了“<math>p^{2}_{k+1}</math><<math>p_{1}</math><math>p_{2}</math>...<math>p_{k}</math>由k>3都是正确的，
即5²>2×3，7²>2×3×5，而11²<2×3×5×7。从11开始都是这样了。
（参见[数学欣赏]汉斯拉德海著220页“数30的一个性质”北京出版社1981.6）所以，若K≥4时，（1）（2）式的计算结果只能取<math>p^{2}_{k+1}</math>以内的值才是素数。还要减去不是素数也不是合数的“1”。
将k=4时的表格总结，设：<math> \pi(x)</math> 表示不大于x的素数个数，那么：
 <math> \pi(121)</math> =[ <math>\frac {2-1}{2}</math>  *  <math>\frac {3-1}{3}</math>  *  <math>\frac {5-1}{5}</math>  *  <math>\frac {7-1}{7}</math> × 121 +4-1]=30
就是说121以内有30个素数。这个总结计算素数个数十分精确
或者：
<math> \pi(p^{2}_{k+1})</math>  =[ <math>\frac {p_{1}-1}{p_{1}}</math> * <math>\frac {p_{2}-1}{p_{2}}</math> * <math>\frac {p_{3}-1}{p_{3}}</math> * * * <math>\frac {p_{k}-1}{p_{k}}</math> × <math>p^{2}_{k+1}+k-1</math> ]

'''数论中几乎所有重大问题都与埃拉托斯特尼筛法有关。⏎
⏎
'''
⏎
⏎
=== [[孪生质数]]的公式 ===
利用上述定理，可以得到以下的结论：“若[[自然数]]<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<5^2-1</math>，所以<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>c_{1}, c_{2} \cdot , c_{k}</math>值，所以这样就求得了区间<math>(7, 7^2)</math>的全部孪生质数对。
{| class="wikitable"
(contracted; show full)

 　这个减法从那个无穷和中去掉了所有偶数项。 
　　现在我们在等号两边乘以<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)，都可以唯一表示成为：
(contracted; show full)== 参考 ==
# ''{{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页
# 《素数之恋》德比希尔著