Sophie Germain prime: Difference between revisions

Latest revision as of 22:08, 2 January 2012

This article defines a property that can be evaluated for a prime number. In other words, every prime number either satisfies this property or does not satisfy this property.
View other properties of prime numbers | View other properties of natural numbers

Definition

A Sophie Germain prime is a prime number $p$ such that $2 p + 1$ is also prime. The corresponding prime $2 p + 1$ is termed a safe prime.

Occurrence

Initial values

The first few Sophie Germain primes are:

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, [SHOW MORE]

View list on OEIS

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

Density in primes

Cutoff $n$	Number of primes $\leq n$	Number of Sophie Germain primes $\leq n$	Proportion of primes that are Sophie Germain primes	Number of Sophie Germain primes divided by $n / (\ln n)^{2}$
10	4	3	$3 / 4 = 0.75$	$1.59057$
100	25	10	$2 / 5 = 0.4$	$2.12076$
1000	168	37	$37 / 168 \approx 0.22$	$1.76553$

Infinitude conjecture

Further information: 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 primes). It is also conjectured that the number of Sophie Germain primes less than or equal to $n$ is $O (n / \log^{2} n)$ , in other words, there exist constants $a, b$ such that the following holds for all sufficiently large $n$ :

$\frac{a n}{\log^{2} n} \leq π_{S G} (n) \leq \frac{b n}{\log^{2} n}$ .

where $π_{S G} (n)$ denotes the number of Sophie Germain primes less than or equal to $n$ .

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

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 $1$ modulo $3$ , 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 primes is very interesting:

Testing

The ID of the sequence in the Online Encyclopedia of Integer Sequences is A005384

@@ Line 6: / Line 6: @@
 ==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===
@@ Line 16: / Line 36: @@
 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===