In number theory

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, Proth's theorem is a primality test

Primality test

A primality test is an algorithm for determining whether an input number is prime. Amongst other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not...

 for Proth numbers.

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

Integer

The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...

 a,


then p is prime

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

 (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 p is a quadratic nonresidue modulo a 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

Jacobi symbol

The Jacobi symbol is a generalization of the Legendre symbol. Introduced by Jacobi in 1837, it is of theoretical interest in modular arithmetic and other branches of number theory, but its main use is in computational number theory, especially primality testing and integer factorization; these in...

 until:

Numerical examples

Examples of the theorem include:

• for p = 3, 2¹ + 1 = 3 is divisible by 3, so 3 is prime.
• for p = 5, 3² + 1 = 10 is divisible by 5, so 5 is prime.
• for p = 13, 5⁶ + 1 = 15626 is divisible by 13, so 13 is prime.
• for p = 9, which is not prime, there is no a such that a⁴ + 1 is divisible by 9.

The first Proth primes are :

3, 5, 13, 17, 41

41 (number)

41 is the natural number following 40 and preceding 42.-In mathematics:Forty-one is the 13th smallest prime number. The next is forty-three, with which it comprises a twin prime...

, 97

97 (number)

97 is the natural number following 96 and preceding 98.-In mathematics:97 is the 25th prime number , following 89 and preceding 101. 97 is a Proth prime as it is 3 × 25 + 1.The numbers 97, 907, 9007, 90007 and 900007 are happy primes...

, 113

113 (number)

113 is the natural number following 112 and preceding 114.-In mathematics:One hundred [and] thirteen is the 30th prime number, following 109 and preceding 127, a Sophie Germain prime, a Chen prime and a Proth prime as it is a prime number of the form 7 × 24 + 1...

, 193

193 (number)

193 is the natural number following 192 and preceding 194.-In mathematics:* 193 is an odd number* 193 is a centered 32-gonal number* 193 is a deficient number, as 1 is less than 193* 193 is a happy number* 193 is a lucky number...

, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ….

, the largest known Proth prime is 19249 · 2^13018586 + 1, found by Seventeen or Bust

Seventeen or Bust

Seventeen or Bust is a distributed computing project started in March 2002 to solve the last seventeen cases in the Sierpinski problem.-Goals:...

. It has 3918990 digits and is the largest known prime which is not a Mersenne prime

Mersenne prime

In mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...

.