普罗斯定理

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

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

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

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

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

举例

例如:

  • 对于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整数,所以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 · 213018586 + 1,是由十七或者破产所找到的,有3,918,990个数字,是已知不是梅森素数的素数中,数值最大的质数[1]

历史

法兰西斯·普罗斯英语François Proth(1852–1879)在1878年发表了这个证明。

相关条目

参考资料

外部链接