Fastprimzahl

aus Wikipedia, der freien Enzyklopädie
Dies ist die aktuelle Version dieser Seite, zuletzt bearbeitet am 3. Oktober 2021 um 15:29 Uhr durch imported>Troubled asset(795950) (→‎Einleitung: Ein bisschen OMA-Tauglichkeit ergänzt).
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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. Ordnung 2 3 5 7 11 13 17 19 23 29 31 37 Folge A000040 in OEIS
02. Ordnung 4 6 9 10 14 15 21 22 25 26 33 34 Folge A001358 in OEIS
03. Ordnung 8 12 18 20 27 28 30 42 44 45 50 52 Folge A014612 in OEIS
04. Ordnung 16 24 36 40 54 56 60 81 84 88 90 100 Folge A014613 in OEIS
05. Ordnung 32 48 72 80 108 112 120 162 168 176 180 200 Folge A014614 in OEIS
06. Ordnung 64 96 144 160 216 224 240 324 336 352 360 400 Folge A046306 in OEIS
07. Ordnung 128 192 288 320 432 448 480 648 672 704 720 800 Folge A046308 in OEIS
08. Ordnung 256 384 576 640 864 896 960 1296 1344 1408 1440 1600 Folge A046310 in OEIS
09. Ordnung 512 768 1152 1280 1728 1792 1920 2592 2688 2816 2880 3200 Folge A046312 in OEIS
10. Ordnung 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632 5760 6400 Folge A046314 in OEIS
11. Ordnung 2048 3072 4608 5120 6912 7168 7680 10368 10752 11264 11520 12800 Folge A069272 in OEIS
12. Ordnung 4096 6144 9216 10240 13824 14336 15360 20736 21504 22528 23040 25600 Folge A069273 in OEIS
13. Ordnung 8192 12288 18432 20480 27648 28672 30720 41472 43008 45056 46080 51200 Folge A069274 in OEIS
14. Ordnung 16384 24576 36864 40960 55296 57344 61440 82944 86016 90112 92160 102400 Folge A069275 in OEIS
15. Ordnung 32768 49152 73728 81920 110592 114688 122880 165888 172032 180224 184320 204800 Folge A069276 in OEIS
16. Ordnung 65536 98304 147456 163840 221184 229376 245760 331776 344064 360448 368640 409600 Folge A069277 in OEIS
17. Ordnung 131072 196608 294912 327680 442368 458752 491520 663552 688128 720896 737280 819200 Folge A069278 in OEIS
18. Ordnung 262144 393216 589824 655360 884736 917504 983040 1327104 1376256 1441792 1474560 1638400 Folge A069279 in OEIS
19. Ordnung 524288 786432 1179648 1310720 1769472 1835008 1966080 2654208 2752512 2883584 2949120 3276800 Folge A069280 in OEIS
20. Ordnung 1048576 1572864 2359296 2621440 3538944 3670016 3932160 5308416 5505024 5767168 5898240 6553600 Folge 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 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.

Weblinks

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.