Prothsche Primzahl - LinkFang.de





Prothsche Primzahl


Prothsche Primzahlen sind Primzahlen der Form [math]k\cdot 2^n+1[/math], wobei [math]k, n \in \mathbb N[/math] positive ganze Zahlen sind (mit [math]k \lt 2^n\ [/math] und [math]k\ [/math] ungerade). Solche Zahlen heißen allgemein Proth-Zahlen, auch wenn sie keine Primzahlen sind.

Wissenswertes

Jede Primzahl lässt sich eindeutig in der Form [math]k\cdot 2^n+1[/math] schreiben; damit eine Primzahl eine Prothsche Primzahl ist, muss aber zusätzlich [math]k \lt 2^n \ [/math] gelten.

Die Bedeutung der Prothschen Primzahlen liegt darin, dass François Proth (1852–1879) einen einfachen Test gefunden hat (Satz von Proth), mit dem sich nachweisen lässt, ob Proth-Zahlen Primzahlen sind. Viele der derzeit größten bekannten Primzahlen wurden mit diesem Test gefunden und es gibt ein frei verfügbares Programm von Yves Gallot, dass den Satz von Proth implementiert und häufig für solche Zwecke benutzt wird[1].

Der Satz von Proth besagt: Die Proth-Zahl [math]N[/math] ist prim, falls es eine natürliche Zahl [math]a[/math] gibt mit:

[math]a^{\frac{N-1}{2}}\equiv -1\ \pmod{N}[/math]

Die Prothschen Primzahlen spielen auch bei den Sierpiński-Zahlen insofern eine Rolle, als eine Folge von Zahlen der Form [math]k \cdot 2^n+1\ [/math] frei von Prothschen Primzahlen sein muss, damit [math]k\ [/math] eine Sierpiński-Zahl sein kann.

Unter den prothschen Primzahlen befinden sich auch Cullen-Primzahlen. Das sind Primzahlen der Form [math]n\cdot 2^n+1[/math].

In der folgenden Tabelle finden sich Primzahlen nach [math]k[/math] geordnet bis 10.000.000. Primzahlen mit [math]k \gt 2^n\ [/math], die also keine Prothschen Primzahlen sind, stehen in Klammern. Prothsche Primzahlen mit [math]k=1[/math] nennt man auch Fermatsche Primzahlen.

Primzahlen [math]N[/math] nach [math]k[/math] geordnet
k Form Primzahlen dieser Form Folge ergibt Primzahlen für n=[2] Folge
1 [math]1 \cdot 2^n+1[/math] 3, 5, 17, 257, 65537 (keine weiteren bekannt) Folge A019434 in OEIS 1, 2, 4, 8, 16 (keine weiteren bekannt) ---
3 [math]3 \cdot 2^n+1[/math] (7), 13, 97, 193, 769, 12289, 786433, … Folge A039687 in OEIS (1), 2, 5, 6, 8, 12, 18, 30, 36, 41, … Folge A002253 in OEIS
5 [math]5 \cdot 2^n+1[/math] (11), 41, 641, 163841, … --- (1), 3, 7, 13, 15, 25, 39, … Folge A002254 in OEIS
7 [math]7 \cdot 2^n+1[/math] (29), 113, 449, 114689, 7340033, … Folge A050527 in OEIS (2), 4, 6, 14, 20, 26, … Folge A032353 in OEIS
9 [math]9 \cdot 2^n+1[/math] (19), (37), (73), 577, 1153, 18433, 147457, 1179649, … Folge A050528 in OEIS (1), (2), (3), 6, 7, 11, 14, 17, 33, 42, 43, … Folge A002256 in OEIS
11 [math]11 \cdot 2^n+1[/math] (23), (89), 353, 1409, 5767169, … Folge A050529 in OEIS (1), (3), 5, 7, 19, 21, 43, … Folge A002261 in OEIS
13 [math]13 \cdot 2^n+1[/math] (53), 3329, 13313, … --- (2), 8, 10, 20, 28, … Folge A032356 in OEIS
15 [math]15 \cdot 2^n+1[/math] (31), (61), 241, 7681, 15361, 61441, … Folge A195745 in OEIS (1), (2), 4, 9, 10, 12, 27, 37, 38, 44, 48, … Folge A002258 in OEIS
17 [math]17 \cdot 2^n+1[/math] (137), 557057, … --- (3), 15, 27, … Folge A002259 in OEIS
19 [math]19 \cdot 2^n+1[/math] 1217, 19457, … --- 6, 10, 46, … Folge A032359 in OEIS
21 [math]21 \cdot 2^n+1[/math] (43), (337), 673, 2689, 10753, … --- (1), (4), 5, 7, 9, 12, 16, 17, 41, … Folge A032360 in OEIS
23 [math]23 \cdot 2^n+1[/math] (47), 11777, … --- (1), 9, 13, 29, 41, 49, … Folge A032361 in OEIS

Die ersten Proth-Zahlen bis 250 lauten:

3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, 241, … (Folge A080075 in OEIS )

Die ersten Proth-Primzahlen bis 500 lauten:

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, … (Folge A080076 in OEIS )

Beispiele

Beispiel 1: (Prothsche Primzahl)

Sei [math]k:=3[/math] und [math]n:=2.[/math] Dann ist [math]N=k \cdot 2^n+1=3 \cdot 2^2+1=13[/math] eine Proth-Zahl, weil [math]k=3[/math] ungerade und [math]3=k\lt2^n=2^2=4[/math] ist.

[math]N=13[/math] ist eine Prothsche Primzahl, wenn eine natürliche Zahl [math]a \in \mathbb N[/math] existiert, sodass [math]a^{\frac{N-1}{2}}= a^{\frac{13-1}{2}}=a^6\equiv -1 \pmod{13}[/math] gilt. Man probiert also alle Zahlen durch, bis man ein geeignetes [math]a[/math] findet:

[math] \begin{align} 1^{\frac{13-1}{2}} & = & 1^6 & = & 1 & & & \equiv & 1 \pmod{13} \\ 2^{\frac{13-1}{2}} & = & 2^6 & = & 64 & = & 5 \cdot 13-1 & \equiv & -1 \pmod{13} \end{align} [/math]

Somit hat man gleich am Anfang schon ein geeignetes [math]a=2[/math] gefunden, das den Beweis erbringt, dass [math]N=13[/math] eine Prothsche Primzahl ist. Auch [math]a=5, 6, 7, 8, 11[/math] sind geeignete Zahlen für diesen Beweis.

Beispiel 2: (Primzahl, aber keine Prothsche Primzahl)

Sei [math]k:=3[/math] und [math]n:=1.[/math] Dann ist [math]N=k \cdot 2^n+1=3 \cdot 2^1+1=7[/math] keine Proth-Zahl, weil [math]k=3[/math] zwar ungerade, aber [math]3=k\not\lt2^n=2^1=2[/math] ist. Allerdings ist [math]N=7[/math] eine Primzahl, aber eben keine Prothsche Primzahl.

Beispiel 3: (keine Primzahl)

Sei [math]k:=5[/math] und [math]n:=4.[/math] Dann ist [math]N=k \cdot 2^n+1=5 \cdot 2^4+1=81[/math] eine Proth-Zahl, weil [math]k=5[/math] ungerade und [math]5=k\lt2^n=2^4=16[/math] ist.

[math]N=81[/math] ist eine Prothsche Primzahl, wenn eine natürliche Zahl [math]a \in \mathbb N[/math] existiert, sodass [math]a^{\frac{N-1}{2}}= a^{\frac{81-1}{2}}=a^{40}\equiv -1 \pmod{81}[/math] gilt. Man probiert also wieder alle Zahlen durch, bis man ein geeignetes [math]a[/math] findet:

[math] \begin{align} 1^{\frac{81-1}{2}} & = & 1^{40} & = & 1 & \equiv\ & 1 \pmod{81} \\ 2^{\frac{81-1}{2}} & = & 2^{40} & = & 1.099.511.627.776 & \equiv\ & 70 \pmod{81} \\ 3^{\frac{81-1}{2}} & = & 3^{40} & = & & \equiv\ & 0 \pmod{81} \\ 4^{\frac{81-1}{2}} & = & 4^{40} & = & & \equiv\ & 40 \pmod{81} \\ 5^{\frac{81-1}{2}} & = & 5^{40} & = & & \equiv\ & 4 \pmod{81} \end{align} [/math]

Analog findet man auch bei allen anderen [math]a[/math] kein geeignetes, das die Bedingung [math] a^{\frac{81-1}{2}} \equiv -1 \pmod{81}[/math] erfüllt. Natürlich gibt es Rechenregeln für die Modulorechnungen, sodass man hohe Zahlen umgehen kann. Somit hat man den Beweis erbracht, dass [math]N=81[/math] keine Prothsche Primzahl ist (was eigentlich von vornherein klar war, da [math]N=3 \cdot 3 \cdot 3 \cdot 3[/math] ist).

Größte bekannte Proth-Primzahl

Die größte bisher bekannte Proth-Primzahl wurde im Mai 2007 von Konstantin Agafonov entdeckt, hat 3.918.990 Stellen[3] und lautet

[math]19249 \cdot 2^{13018586} + 1[/math]

Sie ist auch gleichzeitig die größte Primzahl, die nicht gleichzeitig auch Mersenne-Primzahl ist[4]. Sie wurde im Zuge des Internet-Projektes Seventeen or Bust gefunden, bei dem man nach der kleinsten Sierpinski-Zahl sucht.

Weblinks

Einzelnachweise

  1. Yves Gallot's Proth.exe: an implementation of Proth's Theorem for Windows. Abgerufen am 5. Dezember 2015.
  2. Liste von Primzahlen nach k geordnet für k < 300. Abgerufen am 5. Dezember 2015.
  3. Chris Caldwell, The Top Twenty: Proth
  4. Chris Caldwell, The Top Twenty: Largest Known Primes
fi:Prothin teoreema

fr:Théorème de Proth it:Teorema di Proth ko:프로트의 정리 vi:Kiểm tra Proth


Kategorien: Primzahl

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Prothsche Primzahl (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.