素数公式

素数公式，在数学领域中，表示一种能够僅产生素数的公式。即是说，这个公式能够一个不漏地产生所有的素数，并且对每个输入的值，此公式产生的结果都是素数。由于素数的个数是可数的，因此一般假设输入的值是自然数集（或整数集及其它可数集）。迄今为止，人们尚未掌握任何一个易于计算的素数公式，但人们对于素数公式应该具备的性质已经有了大量的了解。

多项式形式的素数公式

可以证明，一个多项式P(n)，如果不是常数的话，不会是一个素数公式。证明很简单：假设这样的一个多项式P(n)存在，那么P(1)将是一个素数p。接下来考虑 $P(1+kp)$ 的值。由于 $P(1)\equiv 0{\pmod {p}}$ ，我们有 $P(1+kp)\equiv 0{\pmod {p}}$ 。于是 $P(1+kp)$ 是p的倍数。为了使它是素数， $P(1+kp)$ 只能等于p。要使得这对任意的k都成立，P(n)只能是常数。

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

欧拉在1772年发现，对于小于40的所有自然数，多项式

P(n) = n² + n + 41

的值都是素数。对于前几个自然数n = 0, 1, 2, 3……，多项式的值是41, 43, 47, 53, 61, 71……。当n等于40时，多项式的值是1681=41×41，是一个合数。实际上，当n能被41整除的时候，P(n)也能被41整除，因而是合数。这个公式和所谓的质数螺旋（en:Ulam spiral）有关。

狄利克雷定理证明了，对于互素的a和b，线性多项式方程 $L(n)=an+b$ 能产生无穷多个质数（尽管不是对于所有的自然数n）。此外，格林-陶定理（en:Green-Tao theorem）证明了更强的结论：对于每个正整数k，都存在着整数对a、b，使得对于每个0与 k−1之间的n， $L(n)=an+b$ 都是素数。然而，对于比较大的k，找出a和b是很困难的。最好的结果是对于k=24，

P(n) = 45872132836530n + 468395662504823; [1]

至于是否存在次数大于等于2的多项式，满足对无穷多个整数，都能取到素数值，目前还没有结论。

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

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

0=wz+h+j-q

0=(gk+2g+k+1)(h+j)+h-z

0=16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}

0=2n+p+q+z-e

0=e^{3}(e+2)(a+1)^{2}+1-o^{2}

0=(a^{2}-1)y^{2}+1-x^{2}

0=16r^{2}y^{4}(a^{2}-1)+1-u^{2}

0=n+l+v-y

0=(a^{2}-1)l^{2}+1-m^{2}

0=ai+k+1-l-i

0=((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}

0=p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m

0=q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x

0=z+pl(a-p)+t(2ap-p^{2}-1)-pm.

对于这个方程组的所有正整数解：（a,b,...,z），k + 2都是素数。可以把这个公式改写成多项式的形式：将14个等式的右边记作p₁，p₂，……，p₁₄，那么可以说，多项式 $(k+2)(1-p_{1}^{2}-p_{2}^{2}-\cdots -p_{14}^{2})$ 的输入值（a,b,...,z）是正整数时，其值域的正值部分就是所有素数。

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