View source for Sophie Germain prime

{{prime number property}}

==Definition==

A '''Sophie Germain prime''' is a [[prime number]] <math>p</math> such that <math>2p + 1</math> is also prime. The corresponding prime <math>2p + 1</math> is termed a [[safe prime]].

==Occurrence==

===Initial values===

The first few Sophie Germain primes are: 

<section begin="list"/>[[2]], [[3]], [[5]], [[11]], [[23]], [[29]], [[41]], [[53]], [[83]], [[89]], <toggledisplay>113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559 </toggledisplay>[[Oeis:A005384|View list on OEIS]]<section end="list"/>

The first few primes that are ''not'' Sophie Germain primes are: 7, 13, 17, 19, 31.

===Density in primes===

{| class="wikitable" border="1"
! Cutoff <math>n</math> !! Number of primes <math>\le n</math> !! Number of Sophie Germain primes <math>\le n</math> !! Proportion of primes that are Sophie Germain primes !! Number of Sophie Germain primes divided by <math>n/(\ln n)^2</math>
|-
| 10 || 4 || 3 || <math>3/4 = 0.75</math> || <math>1.59057</math>
|-
| 100 || 25 || 10 || <math>2/5 = 0.4</math> || <math>2.12076</math>
|-
| 1000 || 168 || 37 || <math>37/168 \approx 0.22</math> || <math>1.76553</math>
|}

===Infinitude conjecture===

{{further|[[Infinitude conjecture for Sophie Germain primes]]}}

It is conjectured that there are infinitely many Sophie Germain primes (or equivalently, that there are infinitely many [[safe prime]]s). It is also conjectured that the number of Sophie Germain primes less than or equal to <math>n</math> is <math>O(n/\log^2 n)</math>, in other words, there exist constants <math>a,b</math> such that the following holds for all sufficiently large <math>n</math>:

<math>\frac{an}{\log^2 n} \le \pi_{SG}(n) \le \frac{bn}{\log^2 n}</math>.

where <math>\pi_{SG}(n)</math> denotes the number of Sophie Germain primes less than or equal to <math>n</math>.

Other related conjectures to the existence of Sophie Germain primes are:

* [[Conjecture on existence of Cunningham chains of the first kind of arbitrary length]]
* [[Conjecture on existence of bitwin chains of arbitrary length]]

===Infinitude of complement===

Most primes are ''not'' Sophie Germain primes. It is rather easy to see that the number of primes that are not Sophie Germain primes is infinite: for instance, there are infinitely many primes that are <math>1</math> modulo <math>3</math>, and none of them can be a Sophie Germain prime.

==Facts==

While there are not too many interesting facts about the structure of Sophie Germain primes ''per se'', the structure of the corresponding [[safe prime]]s is very interesting:

* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]
* [[Safe prime has plus or minus two as primitive root]]

==Testing==

{{oeis|A005384}}