Sophie Germain prime

related topics
{math, number, function}
{woman, child, man}
{film, series, show}

In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime. For example, 23 is a Sophie Germain prime because it is a prime and 2 × 23 + 1 = 47, also prime. These numbers are named after French mathematician Marie-Sophie Germain.

A Sophie Germain prime p > 3 is of the form 6k−1 or, equivalently, p ≡ 5 (mod 6) — as is its matching safe prime 2p+1. We note that the other form for a prime p > 3 is 6k + 1 or, equivalently, p ≡ 1 (mod 6), and that 3|(2p + 1) — thus excluding such p from the Sophie Germain prime domain. This is trivially proven using modular arithmetic.

It is conjectured that there are infinitely many Sophie Germain primes, but like the twin prime conjecture, this has not been proven.

The first few Sophie Germain primes are:

The largest known Sophie Germain prime as of March 2010 is 183027 × 2265440−1. It has 79911 decimal digits and was found in March 2010 by Tom Wu using the program LLR.[1] Before that the two largest were 648621027630345 × 2253824−1 and 620366307356565 × 2253824−1. They both have 76424 decimal digits and were found in November 2009 by Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza and Antal Járai.[2][3] The previous record was set 6 weeks earlier, 607095 × 2176311−1 with 53081 digits, found by Tom Wu.[4] Before that the record was 48047305725 × 2172403−1 with 51910 digits, found by David Underbakke in January 2007 using the programs TwinGen and LLR.[5] And before that, the record was held by the same team as the November 2009 records, 137211941292195 × 2171960−1 with 51780 digits, found in May 2006.[6] As of March 2010 the above are still the six largest known Sophie Germain primes.

A heuristic estimate (due to G. H. Hardy and J. E. Littlewood) for the number of Sophie Germain primes less than n is 2C2 n / (ln n)2 where C2 is the twin prime constant, approximately 0.660161. For n = 104, this estimate predicts 156 Sophie Germain primes, which has a 20% error compared to the exact value of 190. For n = 107, the estimate predicts 50822, which is still 10% off from the exact value of 56032.

A sequence {p, 2p + 1, 2(2p + 1) + 1, ...} of 1 or more Sophie Germain primes, ending with a prime which does not have to be a Sophie Germain, is called a Cunningham chain of the first kind. Every term of such a sequence except the first and last is both a Sophie Germain prime and a safe prime.

If a Sophie Germain prime p is congruent to 3 (mod 4), then its matching safe prime 2p + 1 will be a divisor of the Mersenne number 2p − 1.

Full article ▸

related documents
Axiom of union
Baire category theorem
RP (complexity)
Zero divisor
Normal morphism
Mutual recursion
Characteristic subgroup
Blum Blum Shub
Contraction mapping
Complete measure
LALR parser
Hamiltonian path problem
Nearest neighbour algorithm
Complete category
Category of sets
Best-first search
Up to
Lyapunov fractal
Elias delta coding
Brun's constant
AVL tree
Product of rings
Abelian category
Column vector
Sum rule in differentiation
Double precision
Group homomorphism
Composite number