Sophie-Germain-Primzahl

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

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

${\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.

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.