普罗斯数

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

$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.