Sophie-Germain-Primzahl

Eine Primzahl p nennt man Sophie-Germain-Primzahl oder auch Germainsche Primzahl, wenn auch 2p+1 eine Primzahl ist. 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.

Beispiele

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

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

Zwischen 1 und 10.000 gibt es 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

Siehe auch: (Folge A005384 in OEIS)

Große bekannte Sophie-Germain-Primzahlen sind

• die momentan größte bekannte: 18.543.637.900.515 · 2^666.667 - 1, eine Zahl mit 200.701 Stellen, entdeckt 2012
• 648.621.027.630.345 · 2^253.824 - 1, eine Zahl mit 76.424 Stellen, entdeckt im November 2009
• 620.366.307.356.565 · 2^253.824 - 1, eine Zahl mit 76.424 Stellen, entdeckt im November 2009
• 607.095 · 2^176.311 - 1, eine Zahl mit 53.081 Stellen, entdeckt im September 2009
• 48.047.305.725 · 2^172.403 - 1, eine Zahl mit 51.910 Stellen, entdeckt im Januar 2007
• 137.211.941.292.195 · 2^171.960 - 1, eine Zahl mit 51.780 Stellen, entdeckt am 3. Mai 2006
• 7.068.555 · 2^121.301 - 1, eine Zahl mit 36.523 Stellen, entdeckt 2005
• 109.433.307 · 2^66.452 - 1, eine Zahl mit 20.013 Stellen, welche 2001 von Underbakke (und anderen) gefunden wurde.
• 92.305 · 2^16.998 + 1, eine Zahl mit 5.117 Stellen, die 1998 von Hoffmann gefunden wurde.

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$

Multipliziert man eine Sophie-Germain-Primzahl p mit der Primzahl 2p+1, so erhält man als Produkt eine Dreieckszahl:

$p \cdot (2p+1) = \frac{2p}{2} \cdot (2p+1) = \frac{(2p) \cdot (2p+1)}{2}$

Allerdings hat jede natürliche Zahl diese Eigenschaft. In obigem Beweis wurde schließlich nirgends die Primzahleigenschaft von p bzw. von 2p+1 verwendet.

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 dx \approx \cfrac{2C_2N}{\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.

Weblinks

• Sophie Germain Prime auf Mathworld.com (englisch)
• Die größten bekannten Sophie-Germain-Primzahlen (englisch)