普罗斯定理是數論的一個定理，可以判斷普罗斯数是否是質數。
如果p是普罗斯数，也就是滿足k2n + 1形式的數，其中k為奇數，且k n，那么如果对于某个整数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，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不是素数。
頭幾個普罗斯質數是:
:3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….
，已知最大的普罗斯質數是19249 · 213018586 + 1，是由十七或者破產所找到的，有3,918,990個數字，是已知不是梅森素数的素数中，數值最大的質數。
歷史
（1852–1879）在1878年發表了這個證明。
相關條目
：普罗斯定理質數測試中，k = 1，a* = 3的特例
*谢尔宾斯基数
參考資料
外部連結
*
评论 (0)