Fastprimzahl

Eine -Fastprimzahl oder auch Fastprimzahl -ter Ordnung ist eine natürliche Zahl, deren Primfaktorzerlegung aus genau Primzahlen besteht, wobei mehrfache Primteiler entsprechend oft gezählt werden. Da alle natürlichen Zahlen größer eins aus Primfaktoren zusammengesetzt sind, ist jede natürliche Zahl zugleich auch eine Fastprimzahl. Fastprimzahlen zweiter Ordnung (also die Produkte von genau zwei Primzahlen) nennt man auch Semiprimzahlen.

Fastprimzahlen bewegen sich zwischen den Polen der unteilbaren Primzahlen und der maximal teilbaren hochzusammengesetzten Zahlen und schließen dabei beide mit ein.

Der Norweger Viggo Brun führte den Begriff um 1915 zur Verallgemeinerung von Primzahlen ein, um einen neuen Ansatz für ungelöste Primzahlprobleme zu finden.[1]

Definition

Sei und mit Primzahlen . Dann heißt Fastprimzahl -ter Ordnung, wobei gilt. Die Zahlenfolge für ein festes wird auch mit bezeichnet.[2] Die Wohldefiniertheit folgt aus der Eindeutigkeit der Primfaktorzerlegung für alle natürlichen Zahlen.

Dieses Konzept kann problemlos auf die ganzen Zahlen und beliebige ZPE-Ringe verallgemeinert werden.

Beispiele und Werte

Beispiele:

  • ist eine Fastprimzahl erster Ordnung („Primzahl“).
  • ist eine Fastprimzahl zweiter Ordnung („Semiprimzahl“).
  • ist eine Fastprimzahl vierter Ordnung.
  • ist eine Fastprimzahl zehnter Ordnung.
  • ist eine Fastprimzahl zwanzigster Ordnung.
Die ersten zwölf Fastprimzahlen erster bis zwanzigster Ordnung
01. Ordnung23571113171923293137Folge A000040 in OEIS
02. Ordnung469101415212225263334Folge A001358 in OEIS
03. Ordnung81218202728304244455052Folge A014612 in OEIS
04. Ordnung1624364054566081848890100Folge A014613 in OEIS
05. Ordnung32487280108112120162168176180200Folge A014614 in OEIS
06. Ordnung6496144160216224240324336352360400Folge A046306 in OEIS
07. Ordnung128192288320432448480648672704720800Folge A046308 in OEIS
08. Ordnung25638457664086489696012961344140814401600Folge A046310 in OEIS
09. Ordnung5127681152128017281792192025922688281628803200Folge A046312 in OEIS
10. Ordnung102415362304256034563584384051845376563257606400Folge A046314 in OEIS
11. Ordnung20483072460851206912716876801036810752112641152012800Folge A069272 in OEIS
12. Ordnung409661449216102401382414336153602073621504225282304025600Folge A069273 in OEIS
13. Ordnung81921228818432204802764828672307204147243008450564608051200Folge A069274 in OEIS
14. Ordnung1638424576368644096055296573446144082944860169011292160102400Folge A069275 in OEIS
15. Ordnung32768491527372881920110592114688122880165888172032180224184320204800Folge A069276 in OEIS
16. Ordnung6553698304147456163840221184229376245760331776344064360448368640409600Folge A069277 in OEIS
17. Ordnung131072196608294912327680442368458752491520663552688128720896737280819200Folge A069278 in OEIS
18. Ordnung26214439321658982465536088473691750498304013271041376256144179214745601638400Folge A069279 in OEIS
19. Ordnung5242887864321179648131072017694721835008196608026542082752512288358429491203276800Folge A069280 in OEIS
20. Ordnung104857615728642359296262144035389443670016393216053084165505024576716858982406553600Folge A069281 in OEIS

Eigenschaften

  • Jede Primzahl ist eine Fastprimzahl der Ordnung 1, jede zusammengesetzte Zahl ist eine Fastprimzahl der Ordnung 2 oder höher. Fastprimzahlen dritter Ordnung, sofern diese aus 3 verschiedenen Primfaktoren bestehen, nennt man auch sphenische Zahlen.
  • Die Vereinigung der bilden eine Zerlegung der natürlichen Zahlen.
  • Jede Fastprimzahl -ter Ordnung ist das Produkt von Fastprimzahlen der Ordnungen mit , z. B.: Das Produkt der 3-Fastprimzahl 12 und der 4-Fastprimzahl 40 ergibt die 7-Fastprimzahl 480. Für gibt es solcher möglichen Zerlegungen, wobei die Stirling-Zahlen zweiter Art bezeichnet.
  • Da es für die Null keine mögliche Primfaktorzerlegung gibt, ist sie keine Fastprimzahl -ter Ordnung.
  • Der Eins wird das leere Produkt als Primfaktorzerlegung zugewiesen. Entsprechend kann sie definitionskonform als Fastprimzahl 0-ter Ordnung bezeichnet werden.
  • Sei die Anzahl der positiven ganzen Zahlen kleiner gleich mit genau Primteilern (die nicht unbedingt verschieden sein müssen). Dann gilt:[3]
  • Jede genügend große gerade Zahl lässt sich als die Summe zweier Primzahlen oder einer Primzahl und einer Fastprimzahl zweiter Ordnung darstellen.[4]
    Diese Aussage hat Ähnlichkeit mit der Goldbachschen Vermutung, wurde 1978 von Chen Jingrun bewiesen und nennt sich Satz von Chen.
  • Es gibt unendlich viele Primzahlen, sodass eine 2-Fastprimzahl ist.[4]
    Diese Aussage hat Ähnlichkeit mit der Vermutung über Primzahlzwillinge und wurde ebenfalls von Chen bewiesen.

Anwendungen

Fastprimzahlen zweiter Ordnung, also Produkte zweier Primzahlen, finden in der Kryptographie Anwendung.

Literatur

  • Władysław Narkiewicz: The Development of Prime Number Theory. From Euclid to Hardy and Littlewood. Springer, Berlin u. a. 2000, ISBN 3-540-66289-8.
  • Hans Riesel: Prime Numbers and Computer Methods for Factorization. Birkhäuser, Boston/Basel/Stuttgart 1985, ISBN 3-7643-3291-3.
  • David M. Bressoud: Factorization and Primality Testing. Springer, New York u. a. 1989, ISBN 0-387-97040-1.
  • Paulo Ribenboim: The little book of bigger primes. 2. Ausgabe. Springer, New York u. a. 2004, ISBN 0-387-20169-6.
  • Die Welt der Primzahlen. Geheimnisse und Rekorde. Auf den neuesten Stand gebracht von Wilfrid Keller. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0.

Einzelnachweise

  1. Wolfgang Blum: Goldbach und die Zwillinge. In: Spektrum der Wissenschaft, Dezember 2008, S. 97 (reproduziert: Primzahlen: Wer lüftet das Geheimnis der Unteilbarkeit? Spiegel Online, 25. Dezember 2008; abgerufen am 24. August 2018).
  2. Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0, S. 219.
  3. Edmund Landau: Handbuch der Lehre von der Verteilung der Primzahlen. B. G. Teubner, 1909, S. 211, abgerufen am 30. Juni 2018.
  4. a b Konstantin Fackeldey: Die Goldbachsche Vermutung und ihre bisherigen Lösungsversuche. (PDF) Freie Universität Berlin, 2002, S. 25–27, abgerufen am 30. Juni 2018.