digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

In number theory, Proth's theorem is a primality test for Proth numbers.

It states that if p is a Proth number, of the form k2n + 1 with k odd and k < 2n, then if for some integer a,

$a^{(p-1)/2}\equiv -1 \mod{p}\,\!$

then p is prime (called a Proth prime). This is a practical test because if p is prime, any chosen a has about a 50 percent chance of working.

If a is a quadratic nonresidue modulo p then the converse is also true, and the test is conclusive. Such an a may be found by iterating a over small primes and computing the Jacobi symbol until:

$\left(\frac{a}{p}\right)=-1$

## Numerical examples

Examples of the theorem include:

• for p = 3, 21 + 1 = 3 is divisible by 3, so 3 is prime.
• for p = 5, 32 + 1 = 10 is divisible by 5, so 5 is prime.
• for p = 13, 56 + 1 = 15626 is divisible by 13, so 13 is prime.
• for p = 9, which is not prime, there is no a such that a4 + 1 is divisible by 9.

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

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

As of 2009, the largest known Proth prime is 19249 · 213018586 + 1, found by Seventeen or Bust. It has 3918990 digits and is the largest known prime which is not a Mersenne prime. [1]

## History

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

## References

 1 videos found
 Proth fora
 1 videos found

We're sorry, but there's no news about "Proth's theorem" right now.

 Limit to books that you can completely read online Include partial books (book previews) .gsc-branding { display:block; }

Oops, we seem to be having trouble contacting Twitter