普罗斯定理

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

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

若a是是模p的二次非剩余，则上述定理的逆定理也成立，因此有一种可以找a的方式，就是在最小的质数中依序找a，计算雅可比符号，直到下式成立为止 (a/p)=-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不是素数。

头几个普罗斯质数是（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个数字，是已知不是梅森素数的素数中，数值最大的质数。

历史

法兰西斯·普罗斯（1852–1879）在1878年发表了这个证明。

In number theory, Proth's theorem is a theorem which forms the basis of a primality test for Proth numbers known as Proth's test. Proth numbers, sometimes called Proth Numbers of the First Kind, are those integers p which take the form p = k2n + 1 with an odd k where k < 2n. For Proth Numbers of the Second Kind, see related topic Riesel numbers. The theorem is also named after the French mathematician and original publisher of the theorem, François Proth.

The theorem states that for any Proth number (of the first kind), p, p is prime if there exists an integer a for which Euler's criterion yields –1, that is, （公式略）.

In this case, p is called a Proth prime.

Proth's Test

Only one such value of a need be found for the test to deterministically confirm primality, provided that p is a Proth number. Verifying that p is a Proth number is a triviality.

This is a practical test because, if p is prime, then any chosen a has about a 50 percent chance of working, and if p is not prime, then no chosen a will work. Furthermore, since the calculation is modulo p, only values of a smaller than p have to be considered.

Systematic naïve variant

If p is Proth composite, then no base a will work to bear witness of primality. If any one base a bears witness, then primality is confirmed. If none do, then compositeness is confirmed.

Numerical examples

Examples of the theorem include:

for p = 3 = 1(21) + 1, we have that 2(3−1)/2 + 1 = 3 is divisible by 3, so 3 is prime.

for p = 5 = 1(22) + 1, we have that 3(5−1)/2 + 1 = 10 is divisible by 5, so 5 is prime.

for p = 13 = 3(22) + 1, we have that 5(13−1)/2 + 1 = 15626 is divisible by 13, so 13 is prime.

for p = 9, which is not prime, there is no a such that a(9−1)/2 + 1 is divisible by 9.

The fact that p = 9 is not prime can be deterministically verified by checking that no such a (in mod 9) exists. This may be done by systematically checking each value of a from 2 to 8 (a = 0 and a = 1 will never work for any p).

Alternative Testing Results

Euler's criterion provides additional insights to a number p, which are not necessarily components of Proth's theorem. These are secondary facts largely attributed to other theorems, which are trivially evaluated during any implementation of Proth's test. The number p need not be a Proth number for the criterion to be useful. Given an integer p, let us choose an arbitrary a value. Evaluate Euler's criterion: （公式略）

There are generally five distinct outcomes. Some of these results do not rely on p being a Proth number, and are therefore valid for any form of prime candidate.

Primality of p:

Proth Certificate

A Proth Certificate is a primality certificate associated with Proth numbers and Proth's test, specifically. It is a document or digital proof of verification of any conditions proving primality (or compositeness). It typically contains the values k and n that comprises the Proth number, p, thus proving that it is a Proth number, as well as the a-value that proves primality. It may also prove compositeness, if appropriate. The certificate often shows the work of proof, including evidence that a is a quadratic nonresidue, etc., if necessary.

Prime Search

The first Proth primes are (sequence A080076 in the OEIS):

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

The largest known Proth prime as of 2016 is 10223 × 231172165 + 1, and is 9,383,761 digits long. It was found by Peter Szabolcs in the PrimeGrid volunteer computing project, which announced it on 6 November 2016. It is the 11th-largest known prime number as of January 2024, it was the largest known non-Mersenne prime until being surpassed in 2023, and is the largest Colbert number. The second-largest known Proth prime is 202705 × 221320516 + 1, found by PrimeGrid.

Proof

The proof for this theorem uses the Pocklington-Lehmer primality test. It is a relatively simple special case to prove Proth's theorem from it. It also closely resembles the proof of Pépin's test. The proof can be found on page 52 of.

Generalization

When k = n, the Proth number takes the form of p = n2n + 1. If we relax the condition requiring that k (or n) is odd, these are known as Cullen numbers, with corresponding Cullen primes. Though Proth's test works when n is odd, Cullen numbers have their own primality tests for arbitrary n.

Furthermore, Cullen's primality tests may be generalized to numbers of the form p = ncn + 1, for arbitrary bases c.

History

François Proth (1852–1879) published the theorem in 1878.