查看“︁普罗斯定理”︁的源代码

'''普罗斯定理'''是[[數論]]的一個定理，可以判斷[[普罗斯数]]是否是[[質數]]。

如果''p''是普罗斯数，也就是滿足''k''2<sup>''n''</sup> + 1形式的數，其中''k''為奇數，且''k'' < 2<sup>''n''</sup>，那么如果对于某个[[整数]]''a''，有

:<math>a^{(p-1)/2}\equiv -1 \pmod{p}\,\!</math>

则''p''是[[素数]]。此時''p''稱為'''普罗斯質數'''。这是一个有实际用途的方法，因为如果''p''是素数，任何选定的''a''都有百分之50的機會滿足這個關係式。

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

:: <math>\left(\frac{a}{p}\right)=-1</math>

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

==舉例==
例如：

* 对于''p'' = 3，2<sup>1</sup> + 1 = 3能被3整除，所以3是素数。
* 对于''p'' = 5，3<sup>2</sup> + 1 = 10能被5整除，所以5是素数。
* 对于''p'' = 13，5<sup>6</sup> + 1 = 15626 能被整除，所以13是素数。
* 对于''p'' = 9，不存在''a''使得''a''<sup>4</sup> + 1能被9整数，所以9不是素数。

頭幾個普罗斯質數是{{OEIS|id=A080076}}:
:3, 5, 13, 17, [[41]], [[97]], [[113]], [[193]], 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

{{As of|2009}}，已知最大的普罗斯質數是19249 · 2<sup>13018586</sup> + 1，是由[[十七或者破產]]所找到的，有3,918,990個數字，是已知不是[[梅森素数]]的素数中，數值最大的質數<ref>[http://primes.utm.edu/top20/page.php?id=3 Largest Known Primes] {{Wayback|url=http://primes.utm.edu/top20/page.php?id=3 |date=20120716181435 }}</ref>。

==歷史==

{{le|法蘭西斯·普羅斯|François Proth}}（1852–1879）在1878年發表了這個證明。

==相關條目==
*{{le|貝潘測試|Pépin's test}}：普罗斯定理質數測試中，''k''&nbsp;=&nbsp;1，''a''&nbsp;=&nbsp;3的特例
*[[谢尔宾斯基数]]

==參考資料==
{{reflist}}

==外部連結==
*{{MathWorld|urlname=ProthsTheorem|title=Proth's Theorem}}

{{数论算法}}

[[Category:素性测试]]
[[Category:素数定理]]