普羅斯定理

簡介

普羅斯定理是數論的一個定理，可以判斷普羅斯數是否是質數。

如果p是普羅斯數，也就是滿足k2+ 1形式的數，其中k為奇數，且k< 2，那么如果對於某個整數a，有

則p是素數。此時p稱為普羅斯質數。這是一個有實際用途的方法，因為如果p是素數，任何選定的a都有百分之50的機會滿足這個關係式。

若a是是模p的二次非剩餘，則上述定理的逆定理也成立，因此有一種可以找a的方式，就是在最小的質數中依序找a，計算雅可比符號，直到下式成立為止

。

蒙地卡羅算法的素性測試是亂數算法，可能會產生偽陽性的結果（不是素數的數卻通過素性測試），根據普羅斯定理的算法是拉斯維加斯算法，其答案都是對的，但要找到答案的時間則是隨機變化。

例如：

頭幾個普羅斯質數是（OEIS中的數列A080076）:

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

截至2009年，已知最大的普羅斯質數是19249 · 2+ 1，是由十七或者破產所找到的，有3,918,990個數字，是已知不是梅森素數的素數中，數值最大的質數。

法蘭西斯·普羅斯（1852–1879）在1878年發表了這個證明。