普罗斯定理

普罗斯定理是数论的一个定理，可以判断普罗斯数是否是质数。

如果p是普罗斯数，也就是满足k2ⁿ + 1形式的数，其中k为奇数，且k < 2ⁿ，那么如果对于某个整数a，有

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

则p是素数。此时p称为普罗斯质数。这是一个有实际用途的方法，因为如果p是素数，任何选定的a都有百分之50的机会满足这个关系式。

若a是是模p的二次非剩余，则上述定理的逆定理也成立，因此有一种可以找a的方式，就是在最小的质数中依序找a，计算雅可比符号，直到下式成立为止

$\left({\frac {a}{p}}\right)=-1$

蒙地卡罗演算法的素性测试是乱数演算法，可能会产生伪阳性的结果（不是素数的数却通过素性测试），根据普罗斯定理的演算法是拉斯维加斯算法，其答案都是对的，但要找到答案的时间则是随机变化。

举例

例如：

• 对于p = 3，2¹ + 1 = 3能被3整除，所以3是素数。
• 对于p = 5，3² + 1 = 10能被5整除，所以5是素数。
• 对于p = 13，5⁶ + 1 = 15626 能被整除，所以13是素数。
• 对于p = 9，不存在a使得a⁴ + 1能被9整数，所以9不是素数。

头几个普罗斯质数是（OEIS数列A080076）:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

截至2009年 (2009-Missing required parameter 1=month!)，已知最大的普罗斯质数是19249 · 2^13018586 + 1，是由十七或者破产所找到的，有3,918,990个数字，是已知不是梅森素数的素数中，数值最大的质数。

历史

法兰西斯·普罗斯（1852–1879）在1878年发表了这个证明。

相关条目

• 贝潘测试：普罗斯定理质数测试中，k = 1，a = 3的特例
• 谢尔宾斯基数

外部链接

• 埃里克·韦斯坦因. Proth's Theorem. MathWorld.