普罗斯数

维基百科,自由的百科全书
跳转至: 导航搜索

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

P=k\, 2^n+1

其中k是奇数,n是正数,且2n>k

既是普罗斯数又是素数的整数,称为普罗斯素数。到2007年为止,已知最大的普罗斯素数是19249 · 213018586 + 1,由Konstantin Agafonov发现,有3918990位。[1]

例子[编辑]

最初的几个普罗斯数为:(OEIS中的数列A080075

P0 = 21 + 1 = 3
P1 = 22 + 1 = 5
P2 = 23 + 1 = 9
P3 = 3 × 22 + 1 = 13
P4 = 24 + 1 = 17
P5 = 3 × 23 + 1 = 25
P6 = 25 + 1 = 33

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

3513174197113193241257,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的概率满足这个关系式。

例如:

  • 对于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整数。

参见[编辑]

外部链接[编辑]