Sophie Germain prime

A prime number p is called a Sophie Germain prime or Germainsche prime if 2p 1 is a prime number. These are prime numbers after the mathematician Sophie Germain (1776-1831) named, which dealt with the Fermat's theorem and proved that the first case the assumption is correct for all Sophie Germain primes.

Examples

P = 2 is a Sophie Germain prime because 2p 1 = 5 is prime. The same is true for 3, 5, 11

P = 7 is not a Sophie Germain prime, since 2p 1 = 15 is not prime.

Between 1 and 10,000, there are 190 Sophie Germain primes:

See also: ( sequence A005384 in OEIS )

Large -known Sophie Germain primes are

• Currently the largest known: 18,543,637,900,515 · 2666,667 - 1, a number with 200 701 points, discovered in 2012
• 648.621.027.630.345 · 2253.824 - 1, a number with 76 424 points, discovered in November 2009
• 620.366.307.356.565 · 2253.824 - 1, a number with 76 424 points, discovered in November 2009
• 607 095 · 2176.311 - 1, a number with 53 081 sites discovered in September 2009
• 48.047.305.725 · 2172.403 - 1, a number with 51 910 points, discovered in January 2007
• 137.211.941.292.195 · 2171.960 - 1, a number with 51 780 places discovered on 3 May 2006
• 7068555 · 2121,301 - 1, a number with 36 523 points, discovered in 2005
• · 109433307 266452-1, a number of 20,013 points which Underbakke 2001 (and others) has been found.
• 92 305 · 216 998 1, a number with 5,117 points, which was found in 1998 by Hoffmann.

Importance

Properties

A Sophie Germain prime number in the decimal system may never have the final digit 7.

Proof: Let p be a prime number with last digit 7 Then one can represent p as p = 10k 7 Then: 2p 1 = 20k 14 1 = 20k 15 = 5 (4k 3). That is, 2p 1 is divisible by 5, but greater than 14, not a prime.

Multiplying a Sophie Germain prime, with the prime 2p 1, we obtain the product a triangular number:

However, every natural number has this property. In the above proof, finally, nowhere is the primality of p or of 2p 1 was used.

All Sophie Germain primes greater than 3 the thing of the residue class r ≡ 5 (mod 6).

All figures of the residue classes r ≡ 0 (mod 6), r ≡ 2 (mod 6 ) and r ≡ 4 (mod 6) are straight and therefore divisible by 2. All figures of the residue classes r ≡ 0 (mod 6 ) and r ≡ 3 (mod 6) are divisible by 3.

Although there are primes in the residue class r ≡ 1 (mod 6) - However, results in 2 * (6n 1) 1 = 12n 3 = 3 * (4n 1) - and 3 * (4n 1) is divisible by 3.

As the only six- residue class for Sophie Germain primes is only 2 * (6n 5) 1 = 12n 11 ≡ 5 (mod 6) left.

Related to the Mersenne numbers

The following property was proved by Leonhard Euler and Joseph -Louis Lagrange:

Example: p = 11 is a Sophie Germain prime because 2p 1 = 23 is prime. Next is 11 ≡ 3 (mod 4), because 11 divided by 4 gives a remainder 3 The 11th Mersenne number M ( 11) = 211-1 = 2047 is therefore not prime, but by 2p 1 = 23 divisible; concrete is M ( 11) = 23 · 89

Frequency of Sophie Germain primes

Published in 1922, Godfrey Harold Hardy and John Edensor Littlewood her assumption regarding the frequency of Sophie Germain primes:

The total number of Sophie Germain primes below a limit N is approximately

With C2 = 0.6601618158 (see twin prime constant). This formula can confirm quite well with the known Sophie Germain primes. For N = 104, the prediction provides 156 Sophie Germain primes, which means an error of 18% for the exact number of 190. For N = 107 provides the prediction of 50822, which is already removed only 9 % from the exact value 56032. A numerical approximation of the integral still provides better results, about 195 for N = 104 (error only 2.6 %) and 56128 for N = 107 (error is almost negligible at 0.17 %).

The density of Sophie Germain primes falls in the order of ln ( N) times stronger than that of the primes itself It is used for a more accurate duration estimate for the AKS primality test, which can detect the Primeigenschaft in polynomial time.

Cunningham chain

With a Cunningham chain of the first kind it is, except for the last number to a sequence of Sophie Germain primes. An example of such a chain is the result of 2, 5, 11, 23, 47

Open Questions

It is believed that there are infinitely many Sophie Germain primes, but proof was not found until today.