例子

普罗斯定理

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

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

既是普罗斯数又是素数的整数，称为普罗斯素数。到2007年为止，已知最大的普罗斯素数是19249 · 2 + 1，由Seventeen or Bust发现，有3918990位。

例子

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

P0 = 21 + 1 = 3P1 = 22 + 1 = 5P2 = 23 + 1 = 9P3 = 3 × 22 + 1 = 13P4 = 24 + 1 = 17P5 = 3 × 23 + 1 = 25P6 = 25 + 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，有

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

例如：

对于p = 3，21 + 1 = 3能被3整除，所以3是素数。对于p = 5，32 + 1 = 10能被5整除，所以5是素数。对于p = 13，56 + 1 = 15626 能被整除，所以13是素数。对于p = 9，不存在a使得a4 + 1能被9整数。