Sophie Germain prime number

A prime number p is called a Sophie-Germain prime number or also Germain prime number , even if 2 p + 1 is a prime number (2 p + 1 is then a safe prime number (from the English safe prime )). These prime numbers are named after the mathematician Sophie Germain (1776–1831), who dealt with Fermat's conjecture and proved that the first case of the conjecture applies to all Sophie Germain prime numbers.

Examples

p = 2 is a Sophie Germain prime, because 2p + 1 = 5 is prime. The same goes for 3, 5, and 11.

p = 7 is not a Sophie Germain prime because 2p + 1 = 15 is not prime.

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

2	3	5	11	23	29	41	53	83	89	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	1583	1601	1733	1811	1889	1901	1931	1973
2003	2039	2063	2069	2129	2141	2273	2339	2351	2393	2399	2459	2543	2549	2693	2699	2741	2753	2819	2903
2939	2963	2969	3023	3299	3329	3359	3389	3413	3449	3491	3539	3593	3623	3761	3779	3803	3821	3851	3863
3911	4019	4073	4211	4271	4349	4373	4391	4409	4481	4733	4793	4871	4919	4943	5003	5039	5051	5081	5171
5231	5279	5303	5333	5399	5441	5501	5639	5711	5741	5849	5903	6053	6101	6113	6131	6173	6263	6269	6323
6329	6449	6491	6521	6551	6563	6581	6761	6899	6983	7043	7079	7103	7121	7151	7193	7211	7349	7433	7541
7643	7649	7691	7823	7841	7883	7901	8069	8093	8111	8243	8273	8513	8663	8693	8741	8951	8969	9029	9059
9221	9293	9371	9419	9473	9479	9539	9629	9689	9791

The first Sophie Germain prime numbers can also be found in the following OEIS link: ${\displaystyle p}$

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

The associated safe prime numbers are the following: ${\displaystyle 2p+1}$

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, ... (follow A005385 in OEIS )

The following list shows the 10 largest known Sophie Germain prime numbers. All discoverers of these prime numbers are participants in the PrimeGrid project.

rank	Rank in list of prime numbers a	Prime number ${\displaystyle p}$	Decimal places of ${\displaystyle p}$	Discovery date	Explorer	source
1	1609.	${\displaystyle 2618163402417\cdot 2^{1290000}-1}$	${\displaystyle 388342}$	February 29, 2016	Scott Brown ( USA )
2	1678.	${\displaystyle 18543637900515\cdot 2^{666667}-1}$	${\displaystyle 200701}$	April 4th or 9th 2012	Lee Blyth ( AUS )
3	1697.	${\displaystyle 183027\cdot 2^{265440}-1}$	${\displaystyle 79911}$	March 22, 2010	Tom Wu
4th	1703.	${\displaystyle 648621027630345\cdot 2^{253824}-1}$	${\displaystyle 76424}$	November 18, 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
5	1704.	${\displaystyle 620366307356565\cdot 2^{253824}-1}$	${\displaystyle 76424}$	November 2, 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai
6th	1722.	${\displaystyle 1068669447\cdot 2^{211088}-1}$	${\displaystyle 63553}$	17th May 2020	Michael Kwok
7th	1729.	${\displaystyle 99064503957\cdot 2^{200008}-1}$	${\displaystyle 60220}$	April 1, 2016	S. Urushihata
8th	1743.	${\displaystyle 607095\cdot 2^{176311}-1}$	${\displaystyle 53081}$	September 18, 2009	Tom Wu
9	1748.	${\displaystyle 48047305725\cdot 2^{172403}-1}$	${\displaystyle 51910}$	January 25, 2007	David Underbakke
10	1752.	${\displaystyle 137211941292195\cdot 2^{171960}-1}$	${\displaystyle 51780}$	May 3, 2006	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai

^aAs of June 4, 2020; the rank only reveals where these prime numbers are in this list

importance

characteristics

• A Sophie Germain prime can never end with 7 in the decimal system.

Proof:

Let p be a prime number with a final digit of 7. Then p can be represented as p = 10k + 7. Then: 2p + 1 = 20k + 14 + 1 = 20k + 15 = 5 · (4k + 3).

This means that 2p + 1 is divisible by 5, but greater than 14, i.e. not prime. ${\displaystyle \Box }$

• All Sophie-Germain primes belong to the remainder class , so they have the form with an integer . ${\displaystyle p>3}$ ${\displaystyle p\equiv 5{\pmod {6}}}$ ${\displaystyle p=6n+5}$ ${\displaystyle n\in \mathbb {N} }$

Proof:

All numbers of the remainder classes r ≡ 0 (mod 6), r ≡ 2 (mod 6) and r ≡ 4 (mod 6) are even and therefore divisible by 2.

All numbers of the remainder classes r ≡ 0 (mod 6) and r ≡ 3 (mod 6) are divisible by 3.

Although there are prime numbers in the remainder class r ≡ 1 (mod 6), 2 · (6n + 1) +1 = 12n + 3 = 3 · (4n + 1) - and 3 · (4n + 1) is divisible by 3 .

The only remaining class of six for the Sophie-Germain primes is the residual class r ≡ 5 (mod 6). Only in this case does the certain prime number belonging to a Sophie-Germain prime number have the form 2 · (6n + 5) +1 = 12n + 11 ≡ 5 (mod 6) and can be prime. ${\displaystyle \Box }$

Connection with the Mersenne numbers

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

If p> 3 is a Sophie-Germain prime with p ≡ 3 (mod 4), then 2p + 1 is a divisor of the p-th Mersenne number M (p).

Example:

p = 11 is a Sophie-Germain prime, because 2p + 1 = 23 is prime. Then 11 ≡ 3 (mod 4), because 11 divided by 4 gives the remainder 3.

The 11th Mersenne number M (11) = 2 ¹¹ -1 = 2047 is therefore not prime, but divisible by 2p + 1 = 23; concretely, M (11) = 23 · 89.

Frequency of Sophie Germain primes

In 1922 Godfrey Harold Hardy and John Edensor Littlewood published their conjecture regarding the frequency of Sophie Germain primes:

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

${\displaystyle {2C_{2}\int \limits _{2}^{N}{\cfrac {1}{\ln(x)\ln(2x+1)}}\;\mathrm {d} x\approx {\cfrac {2C_{2}N}{\ln ^{2}(N)}}}}$

with C ₂ = 0.6601618158 (see prime number twin constant ). This formula can be confirmed quite well with the well-known Sophie Germain prime numbers. For N = 10 ⁴ the prediction yields 156 Sophie-Germain primes, which means an error of 18% to the exact number of 190. For N = 10 ⁷ , the prediction delivers 50822, which is already only 9% away from the exact value 56032. A numerical approximation of the integral delivers even better results, about 195 for N = 10 ⁴ (error only 2.6%) and 56128 for N = 10 ⁷ (error almost negligible at 0.17%).

The density of the Sophie-Germain prime numbers falls in the order of magnitude by ln (N) times more strongly than that of the prime numbers themselves. It is used for a more precise runtime estimate for the AKS prime number test , which can determine the prime property in polynomial time.

Cunningham chain

A Cunningham chain of the first kind, with the exception of the last number, is a sequence of Sophie Germain primes. An example of such a chain is the sequence: 2, 5, 11, 23, 47.

Open questions

It is believed that there are an infinite number of Sophie Germain primes, but evidence of this has not yet been found.

Individual evidence

1. ↑ A distinction is made between possible solutions of Fermat's equation in two cases: the first case means that the exponent p is not a divisor of a · b · c .
2. ↑ Chris K. Caldwell: The Top Twenty: Sophie Germain (p). Prime Pages, accessed June 4, 2020 . 
3. ↑ List of the largest known prime numbers. Retrieved June 4, 2020 . 
4. ↑ 2618163402417 · 2 ^1290000 - 1 on primegrid.com (PDF)
5. ↑ 2618163402417 · 2 ^1290000 - 1 on Prime Pages
6. ↑ 18543637900515 · 2 ⁶⁶⁶⁶⁶⁷ - 1 on primegrid.com (PDF)
7. ↑ 18543637900515 · 2 ⁶⁶⁶⁶⁶⁷ - 1 on Prime Pages
8. ↑ 183027 · 2 ^265440-1 on Prime Pages
9. ↑ 648621027630345 · 2 ^253824-1 on Prime Pages
10. ↑ 620366307356565 · 2 ^253824-1 on Prime Pages
11. ↑ 1068669447 · 2 ^211088-1 on Prime Pages
12. ↑ 99064503957 · 2 ²⁰⁰⁰⁰⁸ - 1 on Prime Pages
13. ↑ 607095 · 2 ^176311-1 on Prime Pages
14. ↑ 48047305725 · 2 ^172403-1 on Prime Pages
15. ↑ 137211941292195 · 2 ^171960-1 on Prime Pages

Web links

• Eric W. Weisstein : Sophie Germain Prime . In: MathWorld (English).
• Sophie Germain Prime . In: PlanetMath . (English)
• The largest known Sophie Germain primes (English)