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]

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:

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

• 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. ${\displaystyle \Box }$

• Alle Sophie-Germain-Primzahlen ${\displaystyle p>3}$ gehören der Restklasse ${\displaystyle p\equiv 5{\pmod {6}}}$ an, haben also die Form ${\displaystyle p=6n+5}$ mit ganzzahligem ${\displaystyle 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. ${\displaystyle \Box }$

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.

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

${\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)}}}}$

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.

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.

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

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

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