普罗斯数

普罗斯数是如下形式的数：

P=k\,2^{n}+1

其中k是奇数，n是正数，且2ⁿ>k。

既是普罗斯数又是素数的整数，称为普罗斯素数。到2016年为止，已知最大的普罗斯素数是10223 · 2^31172165 + 1，由Szabolcs Peter发现，有9383761位。[1] （页面存档备份，存于互联网档案馆）

例子

最初的几个普罗斯数为：（OEIS数列A080075）

P₀ = 2¹ + 1 = 3

P₁ = 2² + 1 = 5

P₂ = 2³ + 1 = 9

P₃ = 3 × 2² + 1 = 13

P₄ = 2⁴ + 1 = 17

P₅ = 3 × 2³ + 1 = 25

P₆ = 2⁵ + 1 = 33

最初的几个普罗斯素数为：A080076

3，5，13，17，41，97，113，193，241，257，353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857

普罗斯定理

普罗斯定理是判断普罗斯数是否为素数的方法。如果p是普罗斯数，那么如果对于某个整数a，有

a^{(p-1)/2}\equiv -1{\pmod {p}}\,\!

则p是素数。这是一个有实际用途的方法，因为如果p是素数，任何选定的a都有百分之50的概率满足这个关系式。

参见

谢尔宾斯基数

外部链接

埃里克·韦斯坦因. 普罗斯数. MathWorld.