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.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).

Definition Sei und mit Primzahlen . Dann heißt Fastprimzahl -ter Ordnung, wobei gilt. Die Zahlenfolge für ein festes wird auch mit bezeichnet.Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0, S. 219. 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 1. Ordnung 2 3 5 7 11 13 17 19 23 29 31 37 … 2. Ordnung 4 6 9 10 14 15 21 22 25 26 33 34 … 3. Ordnung 8 12 18 20 27 28 30 42 44 45 50 52 … 4. Ordnung 16 24 36 40 54 56 60 81 84 88 90 100 … 5. Ordnung 32 48 72 80 108 112 120 162 168 176 180 200 … 6. Ordnung 64 96 144 160 216 224 240 324 336 352 360 400 … 7. Ordnung 128 192 288 320 432 448 480 648 672 704 720 800 … 8. Ordnung 256 384 576 640 864 896 960 1296 1344 1408 1440 1600 … 9. Ordnung 512 768 1152 1280 1728 1792 1920 2592 2688 2816 2880 3200 … 10. Ordnung 1024 1536 2304 2560 3456 3584 3840 5184 5376 5632 5760 6400 … 11. Ordnung 2048 3072 4608 5120 6912 7168 7680 10368 10752 11264 11520 12800 … 12. Ordnung 4096 6144 9216 10240 13824 14336 15360 20736 21504 22528 23040 25600 … 13. Ordnung 8192 12288 18432 20480 27648 28672 30720 41472 43008 45056 46080 51200 … 14. Ordnung 16384 24576 36864 40960 55296 57344 61440 82944 86016 90112 92160 102400 … 15. Ordnung 32768 49152 73728 81920 110592 114688 122880 165888 172032 180224 184320 204800 … 16. Ordnung 65536 98304 147456 163840 221184 229376 245760 331776 344064 360448 368640 409600 … 17. Ordnung 131072 196608 294912 327680 442368 458752 491520 663552 688128 720896 737280 819200 … 18. Ordnung 262144 393216 589824 655360 884736 917504 983040 1327104 1376256 1441792 1474560 1638400 … 19. Ordnung 524288 786432 1179648 1310720 1769472 1835008 1966080 2654208 2752512 2883584 2949120 3276800 … 20. Ordnung 1048576 1572864 2359296 2621440 3538944 3670016 3932160 5308416 5505024 5767168 5898240 6553600 …

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: Jede genügend große gerade Zahl lässt sich als die Summe zweier Primzahlen oder einer Primzahl und einer Fastprimzahl zweiter Ordnung darstellen. 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. 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 Fastprimzahlen Fastprimzahlen 2. Ordnung

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

Kategorie:Ganzzahlmenge Kategorie:Primzahl