Sophie-Germain-Primzahl

Eine Primzahl p nennt man Sophie-Germain-Primzahl oder auch Germainsche Primzahl, wenn auch 2p + 1 eine Primzahl ist (2p + 1 ist dann eine sichere Primzahl (vom englischen Safe prime)). Diese Primzahlen sind nach der Mathematikerin Sophie Germain (1776–1831) benannt, die sich mit der Fermatschen Vermutung beschäftigte und bewies, dass der erste Fall der Vermutung für alle Sophie-Germain-Primzahlen zutrifft.[1]

Beispiele

p = 2 ist eine Sophie-Germain-Primzahl, denn 2p + 1 = 5 ist prim. Das Gleiche gilt für 3, 5 und 11.

p = 7 ist keine Sophie-Germain-Primzahl, da 2p + 1 = 15 nicht prim ist.

Zwischen 1 und 10.000 gibt es die folgenden 190 Sophie-Germain-Primzahlen:

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

Die ersten Sophie-Germain-Primzahlen $p$ kann man auch dem folgenden OEIS-Link entnehmen:

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

Die dazugehörigen sicheren Primzahlen $2p+1$ sind die folgenden:

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

Der folgenden Liste kann man die 10 größten bekannten Sophie-Germain-Primzahlen entnehmen. Sämtliche Entdecker dieser Primzahlen sind Teilnehmer des PrimeGrid-Projektes.

Rang	Rang in Primzahl- liste⁠^a[2][3]	Primzahl $\,p$	Dezimal- stellen von $p$	Datum der Entdeckung	Entdecker	Quelle
1	1609.	$2618163402417\cdot 2^{1290000}-1$	$388342$	29. Februar 2016	Scott Brown (USA)	[4][5]
2	1678.	$18543637900515\cdot 2^{666667}-1$	$200701$	4. oder 9. April 2012	Lee Blyth (AUS)	[6][7]
3	1697.	$183027\cdot 2^{265440}-1$	$79911$	22. März 2010	Tom Wu	[8]
4	1703.	$648621027630345\cdot 2^{253824}-1$	$76424$	18. November 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai	[9]
5	1704.	$620366307356565\cdot 2^{253824}-1$	$76424$	2. November 2009	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai	[10]
6	1722.	$1068669447\cdot 2^{211088}-1$	$63553$	17. Mai 2020	Michael Kwok	[11]
7	1729.	$99064503957\cdot 2^{200008}-1$	$60220$	1. April 2016	S. Urushihata	[12]
8	1743.	$607095\cdot 2^{176311}-1$	$53081$	18. September 2009	Tom Wu	[13]
9	1748.	$48047305725\cdot 2^{172403}-1$	$51910$	25. Januar 2007	David Underbakke	[14]
10	1752.	$137211941292195\cdot 2^{171960}-1$	$51780$	3. Mai 2006	Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai	[15]

^a

Stand: 4. Juni 2020; der Rang verrät nur, an welcher Stelle diese Primzahlen in dieser Liste sind

Bedeutung

Eigenschaften

Eine Sophie-Germain-Primzahl kann im Dezimalsystem niemals die Endziffer 7 haben.

Beweis:

Sei p eine Primzahl mit Endziffer 7. Dann kann man p darstellen als p = 10k + 7. Dann gilt: 2p + 1 = 20k + 14 + 1 = 20k + 15 = 5·(4k + 3).

Das bedeutet, 2p + 1 ist durch 5 teilbar, aber größer als 14, also nicht prim.

\Box

Alle Sophie-Germain-Primzahlen $p>3$ gehören der Restklasse $p\equiv 5{\pmod {6}}$ an, haben also die Form $p=6n+5$ mit ganzzahligem $n\in \mathbb {N}$ .

Beweis:

Alle Zahlen der Restklassen r ≡ 0 (mod 6), r ≡ 2 (mod 6) und r ≡ 4 (mod 6) sind gerade und demnach durch 2 teilbar.

Alle Zahlen der Restklassen r ≡ 0 (mod 6) und r ≡ 3 (mod 6) sind durch 3 teilbar.

Zwar existieren Primzahlen in der Restklasse r ≡ 1 (mod 6), jedoch ergibt 2·(6n+1)+1 = 12n+3 = 3·(4n+1) – und 3·(4n+1) ist durch 3 teilbar.

Als einzige Sechser-Restklasse für die Sophie-Germain-Primzahlen bleibt die Restklasse r ≡ 5 (mod 6) übrig. Nur in diesem Fall hat die zu einer Sophie-Germain-Primzahl gehörende sichere Primzahl die Form 2·(6n+5)+1 = 12n+11 ≡ 5 (mod 6) und kann prim sein.

\Box

Zusammenhang mit den Mersenne-Zahlen

Die folgende Eigenschaft wurde von Leonhard Euler und Joseph-Louis Lagrange bewiesen:

Ist p > 3 eine Sophie-Germain-Primzahl mit p ≡ 3 (mod 4), dann ist 2p+1 ein Teiler der p-ten Mersenne-Zahl M(p).

Beispiel:

p = 11 ist eine Sophie-Germain-Primzahl, denn 2p+1 = 23 ist prim. Weiter ist 11 ≡ 3 (mod 4), denn 11 dividiert durch 4 ergibt als Rest 3.

Die 11. Mersenne-Zahl M(11) = 2¹¹-1 = 2047 ist also nicht prim, sondern durch 2p+1 = 23 teilbar; konkret ist M(11) = 23 · 89.

Häufigkeit von Sophie-Germain-Primzahlen

1922 veröffentlichten Godfrey Harold Hardy und John Edensor Littlewood ihre Vermutung bzgl. der Häufigkeit von Sophie-Germain-Primzahlen:

Die Anzahl aller Sophie-Germain-Primzahlen unterhalb einer Grenze N beträgt ungefähr

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

mit C₂ = 0,6601618158 (siehe Primzahlzwillingskonstante). Diese Formel kann man mit den bekannten Sophie-Germain-Primzahlen recht gut bestätigen. Für N = 10⁴ liefert die Vorhersage 156 Sophie-Germain-Primzahlen, was einen Fehler von 18 % zur exakten Anzahl von 190 bedeutet. Für N = 10⁷ liefert die Vorhersage 50822, was bereits nur noch 9 % vom exakten Wert 56032 entfernt ist. Eine numerische Approximation des Integrals liefert noch bessere Ergebnisse, etwa 195 für N = 10⁴ (Fehler nur noch 2,6 %) und 56128 für N = 10⁷ (Fehler fast vernachlässigbar bei 0,17 %).

Die Dichte der Sophie-Germain-Primzahlen fällt in der Größenordnung um ln(N)-mal stärker als die der Primzahlen selbst. Sie findet Anwendung für eine genauere Laufzeitabschätzung für den AKS-Primzahltest, der die Primeigenschaft in polynomialer Zeit feststellen kann.

Cunningham-Kette

Bei einer Cunningham-Kette der ersten Art handelt es sich, mit Ausnahme der letzten Zahl, um eine Folge von Sophie-Germain-Primzahlen. Ein Beispiel für eine solche Kette ist die Folge: 2, 5, 11, 23, 47.

Offene Fragen

Man vermutet, dass es unendlich viele Sophie-Germain-Primzahlen gibt, aber ein Beweis dafür wurde bis heute nicht gefunden.

Einzelnachweise

Man unterscheidet mögliche Lösungen der Fermatschen Gleichung in zwei Fälle: der erste Fall bedeutet, dass der Exponent p kein Teiler von a·b·c ist.
Chris K.Caldwell: The Top Twenty: Sophie Germain (p). Prime Pages, abgerufen am 4. Juni 2020.
Liste der größten bekannten Primzahlen (englisch). Abgerufen am 4. Juni 2020.
2618163402417·2^1290000 - 1 auf primegrid.com (PDF)
2618163402417·2^1290000 - 1 auf Prime Pages
18543637900515·2⁶⁶⁶⁶⁶⁷ - 1 auf primegrid.com (PDF)
18543637900515·2⁶⁶⁶⁶⁶⁷ - 1 auf Prime Pages
183027·2²⁶⁵⁴⁴⁰ - 1 auf Prime Pages
648621027630345·2²⁵³⁸²⁴ - 1 auf Prime Pages
620366307356565·2²⁵³⁸²⁴ - 1 auf Prime Pages
1068669447·2²¹¹⁰⁸⁸ - 1 auf Prime Pages
99064503957·2²⁰⁰⁰⁰⁸ - 1 auf Prime Pages
607095·2¹⁷⁶³¹¹ - 1 auf Prime Pages
48047305725·2¹⁷²⁴⁰³ - 1 auf Prime Pages
137211941292195·2¹⁷¹⁹⁶⁰ - 1 auf Prime Pages

Weblinks

Eric W. Weisstein: Sophie Germain Prime. In: MathWorld (englisch).
Sophie Germain Prime. In: PlanetMath. (englisch)
Die größten bekannten Sophie-Germain-Primzahlen (englisch)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Man unterscheidet mögliche Lösungen der Fermatschen Gleichung in zwei Fälle: der erste Fall bedeutet, dass der Exponent p kein Teiler von a·b·c ist.

[2] Chris K.Caldwell: The Top Twenty: Sophie Germain (p). Prime Pages, abgerufen am 4. Juni 2020.

[3] Liste der größten bekannten Primzahlen (englisch). Abgerufen am 4. Juni 2020.

[4] 2618163402417·2^1290000 - 1 auf primegrid.com (PDF)

[5] 2618163402417·2^1290000 - 1 auf Prime Pages

[6] 18543637900515·2⁶⁶⁶⁶⁶⁷ - 1 auf primegrid.com (PDF)

[7] 18543637900515·2⁶⁶⁶⁶⁶⁷ - 1 auf Prime Pages

[8] 183027·2²⁶⁵⁴⁴⁰ - 1 auf Prime Pages

[9] 648621027630345·2²⁵³⁸²⁴ - 1 auf Prime Pages

[10] 620366307356565·2²⁵³⁸²⁴ - 1 auf Prime Pages

[11] 1068669447·2²¹¹⁰⁸⁸ - 1 auf Prime Pages

[12] 99064503957·2²⁰⁰⁰⁰⁸ - 1 auf Prime Pages

[13] 607095·2¹⁷⁶³¹¹ - 1 auf Prime Pages

[14] 48047305725·2¹⁷²⁴⁰³ - 1 auf Prime Pages

[15] 137211941292195·2¹⁷¹⁹⁶⁰ - 1 auf Prime Pages

a


formelbasiert	Carol ((2ⁿ − 1)² − 2) \| Doppelte Mersenne (2^{2^p − 1} − 1) \| Fakultät (n! ± 1) \| Fermat (2^2ⁿ + 1) \| Kubisch (x³ − y³)/(x − y) \| Kynea ((2ⁿ + 1)² − 2) \| Leyland (x^y + y^x) \| Mersenne (2^p − 1) \| Mills (A^3ⁿ) \| Pierpont (2^u⋅3^v + 1) \| Primorial (p_n# ± 1) \| Proth (k⋅2ⁿ + 1) \| Pythagoreisch (4n + 1) \| Quartisch (x⁴ + y⁴) \| Thabit (3⋅2ⁿ − 1) \| Wagstaff ((2^p + 1)/3) \| Williams ((b-1)⋅bⁿ − 1) \| Woodall (n⋅2ⁿ − 1)
Primzahlfolgen	Bell \| Fibonacci \| Lucas \| Motzkin \| Pell \| Perrin
eigenschaftsbasiert	Elitär \| Fortunate \| Gut \| Glücklich \| Higgs \| Hochkototient \| Isoliert \| Pillai \| Ramanujan \| Regulär \| Stark \| Stern \| Wall–Sun–Sun \| Wieferich \| Wilson
basisabhängig	Belphegor \| Champernowne \| Dihedral \| Einzigartig \| Fröhlich \| Keith \| Lange \| Minimal \| Mirp \| Permutierbar \| Primeval \| Palindrom \| Repunit-Primzahl ((10ⁿ − 1)/9) \| Schwach \| Smarandache–Wellin \| Strobogrammatisch \| Tetradisch \| Trunkierbar \| Zirkular
basierend auf Tupel	Ausbalanciert (p − n, p, p + n) \| Chen \| Cousin (p, p + 4) \| Cunningham (p, 2p ± 1, …) \| Drilling (p, p + 2 oder p + 4, p + 6) \| Konstellation \| Sexy (p, p + 6) \| Sichere (p, (p − 1)/2) \| Sophie Germain (p, 2p + 1) \| Vierling (p, p + 2, p + 6, p + 8) \| Zwilling (p, p + 2) \| Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe	Titanisch (1.000+ Stellen) \| Gigantisch (10.000+ Stellen) \| Mega (1.000.000+ Stellen) \| Beva (1.000.000.000+ Stellen)