查看“︁素数公式”︁的源代码

{{noteTA|G1=Math}}
'''-{zh-cn:质数公式;zh-tw:質數公式}-'''，又称'''-{zh-cn:素数公式;zh-tw:素數公式}-'''，在数学领域中，表示一种能够僅产生[[质数]]的公式。即是说，这个公式能够一个不漏地产生所有的质数，并且对每个输入的值，此公式产生的结果都是质数。由于质数的个数是[[可數集|可数]]的，因此一般假设输入的值是[[自然数]]集（或[[整数]]集及其它可数集）。迄今为止，人们尚未找到'''易于计算'''且符合上述條件的质数公式，但对于质数公式应该具备的性质已经有了大量的研究。

==多项式形式的素数公式==

可以证明，一个整系數[[多项式]]''P''(''n'')，如果不是[[常數函數]]的话，不会是一个素数公式。证明很简单：假设这样的一个多项式''P''(''n'')存在。那么''P''(1)将是一个素数''p''。接下来考虑<math>P(1+kp)</math>的值。由于<math>P(1) \equiv 0 \pmod p</math>，對于任意整數''k''，我们有<math>P(1+kp) \equiv 0 \pmod p </math>，從而<math>P(1+kp)</math>是''p''的倍数，但已然假设<math>P</math>是素数公式，所以<math>P(1+kn)</math>必须是素数，于是它就只能等于<math>p</math>。也就是說，对于任意的''k''，<math>1 + kp</math>都是多项式''P''(''n'') - ''p''的一個[[根 (數學)|根]]。但根據[[代數基本定理]]，一個非零的整系數多項式不可能有[[無窮]]多個根。故此，''P''(''n'')只能是常数函數。

应用[[代数数]]理论，可以证明更强的结果：不存在能够对[[几乎所有]]自然数输入，都能产生素数的非常数的多项式''P''(''n'')。

[[欧拉]]在1772年发现，对于小于40的所有自然数，多项式
:<math>f(n)=n^{2}+n+41</math>
的值都是素数。对于前几个自然数''n'' = 0, 1, 2, 3...，多项式的值是41, 43, 47, 53, 61, 71...。当''n''等于40时，多项式的值是1681=41×41，是一个合数。实际上，当''n''能被41整除的时候，''P''(''n'')也能被41整除，因而是合数。这个公式和所谓的[[质数螺旋]]有关，也和[[黑格納數]]<math>163=4\cdot 41-1</math>有關。若<math>p=2, 3, 5, 11, 17</math>時，其對應的多項式也有類似的性質，而<math>4\cdot p -1</math>也是黑格納數。
 
[[狄利克雷定理]]证明了，对于[[互素]]的''a''和''b''， [[線性函數]]<math>L(n) = an + b</math>能产生无穷多个质数（尽管不是对于所有的自然数n）。至于是否存在次数大于等于2的多项式，满足对无穷多个整数，都能取到素数值，目前还没有结论。

此外，[[格林-陶定理]]证明了另一结论：对于每个正整数''k''，都存在着整数对''a'', ''b''，使得对于每个0与''k''−1之间的''n''，<math>L(n) = an+b</math>都是素数。然而，对于比较大的''k''，找出''a''和''b''是很困难的。目前最好的结果是对于''k'' = 26<ref>{{cite web|title=PrimeGrid’s AP26 Search|url=http://www.primegrid.com/download/AP26.pdf|accessdate=2015-03-07|archive-date=2020-09-21|archive-url=https://web.archive.org/web/20200921204816/https://www.primegrid.com/download/AP26.pdf|dead-url=no}}</ref>，
:''P''(''n'') = 5283234035979900''n'' + 43142746595714191（{{oeis|A204189 }}）

==丢番图方程形式的素数公式==

一个很著名的素数公式是以下的有26个未知数的由14个方程组成的[[丢番图方程]]组Jones et al.（1976）：

:<math>0 = wz + h + j - q</math>
:<math>0 = (gk + 2g + k + 1)(h + j) + h - z</math>
:<math>0 = 16(k + 1)^3(k + 2)(n + 1)^2 + 1 - f^2</math>
:<math>0 = 2n + p + q + z - e</math>
:<math>0 = e^3(e + 2)(a + 1)^2 + 1 - o^2</math>
:<math>0 = (a^2 - 1)y^2 + 1 - x^2</math>
:<math>0 = 16r^2y^4(a^2 - 1) + 1 - u^2</math>
:<math>0 = n + l + v - y</math>
:<math>0 = (a^2 - 1)l^2 + 1 - m^2</math>
:<math>0 = ai + k + 1 - l - i</math>
:<math>0 = ((a + u^2(u^2 - a))^2 - 1)(n + 4dy)^2 + 1 - (x + cu)^2</math>
:<math>0 = p + l(a - n - 1) + b(2an + 2a - n^2 - 2n - 2) - m</math>
:<math>0 = q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x</math>
:<math>0 = z + pl(a - p) + t(2ap - p^2 - 1) - pm.</math>

对于这个方程组的所有正整数解：(a,b,...,z)，''k''&nbsp;+&nbsp;2都是素数。可以把这个公式改写成多项式的形式：将14个等式记作p<sub>1</sub>，p<sub>2</sub>，……，p<sub>14</sub>，那么可以说，多项式<math> (k+2)(1-p_1^2-p_2^2-\cdots- p_{14}^2) </math>的输入值(a,b,...,z)是正整数时，其值域的正值部分就是所有素数。

根据[[尤里·马季亚谢维奇]]的一个定理，如果一个集合能够被定义成一个[[丢番图方程]]的解集，那么就可以被定义为一个只有9个未知数的[[丢番图方程]]的解集。于是，素数集合可以被定义为一个只含10个变元的多项式的正值解集。然而，这个多项式的次数极大（在10<sup>45</sup>数量级），另一方面，也存在次数不超过4的多项式，未知数个数是58个。

== 带高斯符號的素数公式 ==

利用[[高斯符號]]<math>[x]</math>，可以建立一些第''n''个素数的表达式：

=== Mills公式 ===

第一个带高斯函数的素数公式由W. H. Mills在1947年构造。他证明了存在[[实数]]''A''使得数列

:<math>[ A^{3^{n}}\;]</math>

中的每个数都是素数。最小的''A''称为[[米爾斯常數]]，如果[[黎曼猜想]]成立，它的值大約為：<math> A \approx 1.30637788386308069046\ldots</math>（{{oeis|A051021}}）。
这个素数公式并没有什么实际价值，因为人们对''A''的性质所知甚少，甚至不知道''A''是否為有理数。而且，除了用素数值逼近外，没有其他计算''A''的方法。

===威尔逊定理的利用===

使用[[威尔逊定理]]，可以建立一些其他的素数公式。以下的公式也没有什么实际价值，大多数的[[素性测试]]都比它远为有效。

我们定义
:<math>\pi(m) = \sum_{j=2}^m \frac { \sin^2 ( {\pi \over j} (j-1)!^2 ) }
{   \sin^2( {\pi \over j} ) }
</math>

或者
:<math>\pi(m) = \sum_{j=2}^m \left[ {(j-1)! + 1 \over j} - \left[ {(j-1)! \over j}\right] \right]. </math>

这两种定义是等价的。π（''m''）就是小于''m''的素数个数。于是，我们可以定义第''n''个素数如下：

:<math>p_n = 1 + \sum_{m=1}^{2^n}  \left \lbrack \left \lbrack { n \over 1 + \pi(m) } \right\rbrack^{1 \over n} \right\rbrack.</math>

===另一个用高斯函数的例子===

这个例子没有用到[[阶乘]]和[[威尔逊定理]]，但也大量应用了高斯函数（S. M. Ruiz 2000）。首先定义：
:<math>\pi(k) = k - 1 + \sum_{j=2}^k \left\lbrack {2 \over j} \left(1 +  \sum_{s=1}^{\left\lbrack\sqrt{j}\right\rbrack} \left(\left\lbrack{ j-1 \over s}\right\rbrack - \left\lbrack{j \over s}\right\rbrack\right) \right)\right\rbrack </math> 

然后就有第''n''个素数的表达式：
:<math>p_n = 1 + \sum_{k=1}^{2(\lbrack n \ln(n)\rbrack+1)} \left(1 - \left\lbrack{\pi(k) \over n} \right\rbrack\right). </math>

==递推关系==
另外一个素数公式由以下[[递推关系]]組成的數列，其前後項的差來定义：
:<math> a_n = a_{n-1} + \operatorname{gcd}(n,a_{n-1}), \quad a_1 = 7, </math>
其中gcd(''x'', ''y'')表示''x''和''y''的[[最大公因數]]。这个数列的开始几项a<sub>n+1</sub> - a<sub>n</sub>是1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1 {{OEIS|id=A132199}}。{{harvtxt|Rowlands|2008}}证明了这个数列只含有一和素数。

==其他公式==
=== [[威尔逊定理]]衍生公式 ===
:<math>f(n) = 2 + (2n! \; \pmod{n+1})</math>

其中，素数2出现无限多次，其余的素数恰好出现一次。实际上，当''n+1''是素数''p''的时候，由[[威尔逊定理]]，<math>2n! \; \pmod{n+1}</math>等于''p-2''，于是<math>f(n) = p</math>，当''n+1''是合数的时候，<math>2n! \pmod{n+1}</math>等于0，于是得到2。

==參考資料==
{{reflist}}

==参见==
*[[素数]]
*[[質數定理]]
*[[哥德巴赫猜想]]
*[[双生质数]]
*[[埃拉托斯特尼筛法]]
*[[费马数]]<math>F_{n} = 2^{2^n} + 1</math>
*[[X²+1素数]]

{{質數}}
[[Category:素数]]
[[Category:趣味數學]]
[[Category:数学公式]]