Sophie-Germain-Primzahl

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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[Bearbeiten | Quelltext bearbeiten]

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 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 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-
listea[2][3]
Primzahl Dezimalstellen
von
Entdeckungsdatum Entdecker Quelle
1 1406. 29. Februar 2016 Scott Brown (USA) [4]
2 1494. 9. April 2012 Lee Blyth (AUS) [5]
3 1514. 22. März 2010 Tom Wu [6]
4 1518. 18. November 2009 Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai [7]
5 1519. 2. November 2009 Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai [8]
6 1532. 1. April 2016 S. Urushihata [9]
7 1546. 18. September 2009 Tom Wu [10]
8 1553. 25. Januar 2007 David Underbakke [11]
9 1557. 3. Mai 2006 Zoltán Járai, Gabor Farkas, Timea Csajbok, János Kasza, Antal Járai [12]
10 1591. Dezember 2010 S. Urushihata [13]
a Stand: 21. Juni 2018; der Rang verrät nur, an welcher Stelle diese Primzahlen in dieser Liste sind

Bedeutung[Bearbeiten | Quelltext bearbeiten]

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  • 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.
  • Alle Sophie-Germain-Primzahlen gehören der Restklasse an, haben also die Form mit ganzzahligem .
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.

Zusammenhang mit den Mersenne-Zahlen[Bearbeiten | Quelltext bearbeiten]

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) = 211-1 = 2047 ist also nicht prim, sondern durch 2p+1 = 23 teilbar; konkret ist M(11) = 23 · 89.

Häufigkeit von Sophie-Germain-Primzahlen[Bearbeiten | Quelltext bearbeiten]

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

mit C2 = 0,6601618158 (siehe Primzahlzwillingskonstante). Diese Formel kann man mit den bekannten Sophie-Germain-Primzahlen recht gut bestätigen. Für N = 104 liefert die Vorhersage 156 Sophie-Germain-Primzahlen, was einen Fehler von 18 % zur exakten Anzahl von 190 bedeutet. Für N = 107 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 = 104 (Fehler nur noch 2,6 %) und 56128 für N = 107 (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[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

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

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  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 21. Juni 2018.
  3. Liste der größten bekannten Primzahlen (englisch). Abgerufen am 21. Juni 2018.
  4. 2618163402417·21290000 - 1 auf primegrid.com (PDF)
  5. 18543637900515·2666667 - 1 auf primegrid.com (PDF)
  6. 183027·2265440 - 1 auf Prime Pages
  7. 648621027630345·2253824 - 1 auf Prime Pages
  8. 620366307356565·2253824 - 1 auf Prime Pages
  9. 99064503957·2200009 - 1 auf Prime Pages
  10. 607095·2176311 - 1 auf Prime Pages
  11. 48047305725·2172403 - 1 auf Prime Pages
  12. 137211941292195·2171960 - 1 auf Prime Pages
  13. 31737014565·2140003 - 1 auf Prime Pages

Weblinks[Bearbeiten | Quelltext bearbeiten]