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.
1. Ordnung | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 | 37 | … | Folge A000040 in OEIS |
2. Ordnung | 4 | 6 | 9 | 10 | 14 | 15 | 21 | 22 | 25 | 26 | 33 | 34 | … | Folge A001358 in OEIS |
3. Ordnung | 8 | 12 | 18 | 20 | 27 | 28 | 30 | 42 | 44 | 45 | 50 | 52 | … | Folge A014612 in OEIS |
4. Ordnung | 16 | 24 | 36 | 40 | 54 | 56 | 60 | 81 | 84 | 88 | 90 | 100 | … | Folge A014613 in OEIS |
5. Ordnung | 32 | 48 | 72 | 80 | 108 | 112 | 120 | 162 | 168 | 176 | 180 | 200 | … | Folge A014614 in OEIS |
6. Ordnung | 64 | 96 | 144 | 160 | 216 | 224 | 240 | 324 | 336 | 352 | 360 | 400 | … | Folge A046306 in OEIS |
7. Ordnung | 128 | 192 | 288 | 320 | 432 | 448 | 480 | 648 | 672 | 704 | 720 | 800 | … | Folge A046308 in OEIS |
8. Ordnung | 256 | 384 | 576 | 640 | 864 | 896 | 960 | 1296 | 1344 | 1408 | 1440 | 1600 | … | Folge A046310 in OEIS |
9. 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 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.
Weblinks
- Eric W. Weisstein: Almost prime. In: MathWorld (englisch). Fastprimzahlen
- Eric W. Weisstein: Semiprime. In: MathWorld (englisch). 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
- ↑ 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).
- ↑ Paulo Ribenboim: Die Welt der Primzahlen. Geheimnisse und Rekorde. Springer, Berlin / Heidelberg / New York 2006, ISBN 978-3-540-34283-0, S. 219.
- ↑ Edmund Landau: Handbuch der Lehre von der Verteilung der Primzahlen. B. G. Teubner, 1909, S. 211, abgerufen am 30. Juni 2018.
- ↑ 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.