Sophie Germain Prime

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, and 47 is also a prime number. 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 this has not been proven.

List of unsolved problems in mathematics
Are there infinitely many Sophie Germain primes?

The first few Sophie Germain primes are:

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, …... (sequence A005384 in OEIS).

The largest known Sophie Germain prime as of April 2012 is 18543637900515 × 2666667−1. It has 200701 decimal digits and was found in April 2012 by Philipp Bliedung in a distributed PrimeGrid search using the programs TwinGen and LLR. The previous record was 183027 × 2265440−1 with 79911 digits, found in March 2010 by Tom Wu using LLR. Before that the two largest were 648621027630345 × 2253824−1 and 620366307356565 × 2253824−1. They both have 76424 digits and were found in November 2009 by Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza and Antal Járai. The previous record was set 6 weeks earlier, 607095 × 2176311−1 with 53081 digits, found by Tom Wu. Before that the record was 48047305725 × 2172403−1 with 51910 digits, found by David Underbakke in January 2007 using TwinGen and LLR. 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. As of April 2012 the above are still the seven 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 one 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.

Read more about Sophie Germain Prime:  Application in (pseudo-)random Number Generation, In Popular Culture

Other articles related to "sophie germain prime, germain, sophie, sophie germain, prime":

Sophie Germain Prime - In Popular Culture
... Sophie Germain primes are mentioned in the stage play Proof and the subsequent film. ...
List Of Schools In France - Lycées
... La Martiniere Lyon, Lyon Lycée Henri-IV, Paris Lycée International de Saint Germain-en-Laye, Saint-Germain-en-Laye Lycée Louis-le-Grand, Paris ... Jean-Baptiste Dumas, Ales Lycée Jean-Baptiste Poquelin, Saint-Germain-en-Laye Lycée Jean Bart, Dunkirk Lycée Jean Calvin, Noyon Lycée Jean Dautet, La Rochelle Lycée Jean de La Fontaine, Château-Thie ... Le Puy-en-Velay Lycée Simone Weil, Dijon Lycée Sophie Barat, Châtenay-Malabry Lycée Sophie Berthelot, Calais Lycée Sophie Germain, Paris Lycée Suzanne Valadon, Limoges Lycée ...
1909 (number) - Selected Numbers in The Thousands (1001–1999) - 1750–1999
1753 – balanced prime 1756 – centered pentagonal number 1764 – 1770 – triangular number, hexagonal number, Town of Seventeen Seventy in Australia 1771 ... according to Leporello's tally 1801 – cuban prime 1806 – pronic number, product of first four terms of Sylvester's sequence, primary pseudoperfect number 1807 – fifth term of Sylvester's sequence 1811 ...
9000 (number) - Selected Numbers in The Range 9000–9999
... cube number 9025 – 952, centered octagonal number 9029 – Sophie Germain prime 9045 – triangular number 9059 – Sophie Germain prime 9072 – decagonal number 9077. 9870 – triangular number 9871 – balanced prime 9880 – tetrahedral number 9887 – safe prime 9899 – ISO 9899 standard for C programming language 9901 – unique prime 9923 – probably smallest ...

Famous quotes containing the word prime:

    No woman in my time will be Prime Minister or Chancellor or Foreign Secretary—not the top jobs. Anyway I wouldn’t want to be Prime Minister. You have to give yourself 100%.
    Margaret Thatcher (b. 1925)