|
Was ist eine Primzahl?
Eine natürliche Zahl heißt Primzahl,
wenn sie nur durch 1 und sich selbst teilbar ist. |
Das sind die ersten 100 Primzahlen.
Bis 500 sind 19% der Zahlen Primzahlen. |
Nach der Definition ist auch
die Zahl 1 eine Primzahl. Aber es ist zweckmäßig, sie nicht
mitzuzählen.
Christian Gleixner schreibt
mir, dass man deshalb definieren sollte: " Eine Zahl, die genau zwei Teiler
hat, heißt Primzahl."
Natürliche Zahlen, die
nicht Primzahlen sind, heißen zusammengesetzte Zahlen.
Auf dieser Seite findet man überwiegend Unterhaltsames
zum Thema Primzahlen.
Sieb des Eratosthenes
top
Es gibt viele Verfahren, um Primzahlen zu finden.
Die 100 Primzahlen oben hat ein Computerprogramm gefunden
mit der entscheidenden Zeile
If (n/t)= Int (n/t) and i=2 Then Print n;.
Ein Verfahren, das schon
auf Eratosthenes (ca 276 bis ca 195 v.Chr.) zurückgeht, ist das Sieb
des Eratosthenes.
... ... |
Man gibt die Folge der natürlichen Zahlen vor.
Dann streicht man der Reihe nach alle Zahlen, die durch
2, 3, 5, ... teilbar sind.
In diesem Falle geht es um die Zahlen bis 100.
Da genügt es, die Primteiler unter sqrt(100) oder
zu prüfen. |
...
teilbar durch 2? |
teilbar durch 3? |
teilbar durch 5? |
teilbar durch 7? |
Es bleiben die 25 Primzahlen bis 100 übrig.
Euklids
Überlegung zur Anzahl der Primzahlen top
Es gibt unendliche viele Primzahlen.
Ein Beweis geht auf Euklid zurück und ist ein berühmtes
Beispiel für einen indirekten Beweis.
Beweis
Angenommen, die Anzahl der Primzahlen sei endlich, nämlich
t.
Die t Primzahlen sollen p1, p2,
p3, ..., pt mit p1=2, p2=3,
p3=5, ... sein.
Dann ist x=p1* p2* p3*
...* pt+1 eine neue Zahl, die nach der Konstruktion durch keine
der Primzahlen pi teilbar ist.
Behauptung: Es gibt eine weitere Primzahl p, die x teilt,
x=a*p. p ist notwendig von allen pj verschieden.
Angenommen, es gilt p=pj
(1<=j<=t). Dann gilt pj*b+1 = a*pj , wobei
b das Produkt der restlichen t-1 Faktoren ist.
Weiter folgt aus pj* b+1 = a*pj
die Gleichung pj*(b-a)=1 und weiter pj =1.
Also ist p eine weitere Primzahl.
Das ist ein Widerspruch zur
Aussage, dass es nur t Primzahlen gibt.
Zahlenbeispiele dazu
2*3+1
=7 |
2*3*5+1
=31 |
2*3*5*7+1
=211 |
2*3*5*7*11+1
=2311 |
2*3*5*7*11*13+1=30031
=30031=59*509 |
2*3*5*7*11*13*17+1
= 510511=19*97*277 |
2*3*5*7*11*13*17*19+1
=9699691=347*27953 |
Folgen von Primzahlen
top
Satz von Derichlet
Auch der folgende Satz von Derichlet
stellt sicher, dass es unendlich viele Primzahlen gibt.
Jede arithmetische Folge an=q*n+r, in der
q und r teilerfremd sind, enthält unendlich viele Primzahlen.
Man weiß damit allerdings nicht, welche Glieder
der Folge konkret Primzahlen sind.
Ein Beispiel einer arithmetischen
Folge ist an=4n+3.
|
Die ersten 10 Primzahlen zu an=4n+3:.
|
|
n
an
|
0
3
|
1
7
|
2
11
|
4
19
|
5
23
|
7
31 |
10
43
|
11
47
|
14
59
|
16
67
|
|
Quadratische
Terme
Es gibt quadratische Terme wie an=n²+n+41,
die etliche aufeinander folgende Primzahlen enthalten (nach Euler).
|
Die ersten 10 Primzahlen zu an=n²+n+41
sind:.....
|
n
an
|
0
41
|
1
43
|
2
47
|
3
53
|
4
61
|
5
83
|
6
97
|
7
113
|
8
131
|
9
151
|
|
Die Folge der Primzahlen kann bis zur Primzahl a40=1681
fortgesetzt werden.
Dann allerdings folgt mit a41=41²+41+41
eine zusammengesetzte Zahl.
Hoppla! Benjamin Rott teilt mir mit, dass schon a40=1681
keine Primzahl mehr ist. Es gilt 1681=41².
Auch für größere Werte von n liefert
die Formel aufeinander folgende Primzahlen.
Weitere Terme dieser Art
sind an = n²-n+41 und an
=
n²-79n+1601.
Eine
Reihe von Dezimalzahlen
Die Zahlen 31, 331, 3331, 33331, 333331, 3333331, 33333331
sind Primzahlen.
Die nächste Zahl 333333331 ist zusammengesetzt.
Es gilt 333333331=17*19607843.
Verteilung
der Primzahlen
top
Es sei pi(n) die Anzahl der Primzahlen kleiner als n,
n ist eine natürliche Zahl. Es gilt
n
pi(n)
pi(n)/n
|
1 000
168
16,8%
|
10 000
1229
12,3%
|
100 000
9592
9,6%
|
1 000 000
78498
7,8%
|
10 000 000
664 579
6,6%
|
100 000 000
5 761 455
5,8%
|
(3) Seite 81
Die Tabelle zeigt: Je größer
die natürlichen Zahlen sind, desto größer ist auch die
Anzahl der Primzahlen, die bis zur betreffenden natürlichen Zahl gezählt
werden. Interessanter ist die dritte Zeile. Der Anteil der Primzahlen nimmt
immer mehr ab. Das bestätigen auch weitergehende Zahlenuntersuchungen.
... .
....Der
Graph ist hier nur zutreffend für x>>1..........
|
Es gilt der berühmte Primzahlsatz, der die Anzahl
pi(n) für hinreichend große Zahlen näherungsweise angibt.
Es gilt lim {pi(n)/[ln n/n]}= 1 für n gegen unendlich. D.h., die Funktion
f(x)=ln x/x beschreibt die Anzahl für hinreichend große natürliche
Zahlen. - Der Term ln x steigt langsam und beständig, der Term 1/x
geht gegen 0 für x gegen Unendlich. Der zusammengesetzte Term ln x/x
wird immer kleiner, erreicht aber nie Null. |
Für die Primzahlen bedeutet das, dass sie mit größer
werdenden Zahlen immer seltener werden, dass sie aber nie versiegen.
Die Ulam-Spirale
 |
... ... |
Ordnet man die ersten 25 natürlichen Zahlen in Form
einer Spirale an und markiert die Primzahlen in Rot, erhält man ein
Figur wie links.
Bei der Ulam-Spirale ersetzt man die zusammengesetzten
Zahlen durch weiße und die Primzahlen durch schwarze Pixel. Überraschenderweise
zeigt die Figur mit größer werdenden Zahlen eine Struktur. Es
entstehen Diagonalen. |
Die Ulam-Spirale kann mit einem Applet von Dario Alpern
(URL unten) gezeichnet werden. Dort liest man: Die Geradenabschnitte entstehen
durch die aufeinander folgenden Primzahlen in quadratischen Folgen wie
an=n²+n+41 (s.o.). Quadratische Terme erscheinen in der
Ulam-Spirale als Diagonalen.
Goldbachsche Vermutung
top
Christian Goldbach formulierte 1742 in einem Brief an
Leonard Euler die Vermutung, dass jede Zahl > 2 als Summe dreier Primzahlen
geschrieben werden kann. Euler antwortete darauf, dass er vermutet, dass
jede gerade Zahl eine Summe von zwei Primzahlen ist. - Damals zählte
man die Zahl 1 zu den Primzahlen.
Heute formuliert man Eulers
Vermutung ohne Berücksichtigung der Zahl 1 als goldbachsche Vermutung
wie folgt.
Jede gerade Zahl >2 kann auf mindestens eine Art in zwei
Primzahlen zerlegt werden.
Die ersten Zerlegungen sind 4=2+2, 6=3+3, 8=5+3, 10=5+5=3+7.
Die goldbachsche Vermutung
ist bis heute weder bewiesen noch widerlegt.
Primzahlzwillinge top
Das sind Paare von Primzahlen, die sich um die Differenz
2 unterscheiden.
Bis 100 gibt es (3, 5), (5, 7), (11, 13), (17, 19), (29,
31), (41, 43), (59, 61) und (71, 73).
Es ist ungewiss, ob es unendlich viele Primzahlzwillinge
gibt.
Besondere Primzahlen
top
Fermatsche Primzahlen
Es geht um die Zahlen an
=
2^(2^n)+1. (Es bedeutet 2^n = 2n.)
|
Die ersten 7 Zahlen zu an = 2^(2^n)+1
sind
|
n
an
|
0
3
|
1
5
|
2
17
|
3
257
|
4
65537
|
5
4294967297
|
6
18446744073709551617
|
|
Die ersten 5 Zahlen 3, 5, 17, 257, 65537 sind die fermatschen
Primzahlen.
Mehr Primzahlen in der Folge kennt man nicht. Es ist
bis heute auch nicht bekannt, ob es überhaupt unendlich viele fermatsche
Primzahlen
gibt.
Die 6. Zahl 2^(2^5)+1=4294967297 ist wegen 641*6700417
eine zusammengesetzte Zahl. Damit wurde die (erste) Vermutung von
Fermat widerlegt, alle Zahlen mit 2^ (2^n)+1 seien prim.
In der Theorie der Kreisteilung
spielen fermatsche Primzahlen eine wichtige
Rolle.
Noch eine Zahlenmerkwürdigkeit: 1031+1
= 11*909090909090909090909090909091
Mersenne-Primzahlen
top
Die Zahlen 2n-1 heißen Mersenne-Zahlen.
|
Die ersten 10 Zahlen zu an= 2n-1:
|
|
n
an
|
1
1
|
2
3
|
3
7
|
4
15
|
5
31
|
6
63
|
7
127
|
8
255
|
9
511
|
10
1023
|
|
Für bestimmte natürliche
Zahlen n ergeben sich Primzahlen.
|
n
an
|
2
3
|
3
7
|
5
31
|
7
127
|
13
8191
|
17
131071
|
19
524287
|
31
2147483647
|
61
2305843009213693951
|
89
618970019642690137449562111
|
Die Frage, ob es unendlich viele Mersenne-Primzahlen gibt,
ist nicht entschieden.
Unter den Mersenne-Zahlen
findet man die größten Primzahlen.
2^127-1 war bis 1952 die größte mit Ziffern
bekannte Primzahl.
Sie hat 39 Stellen und heißt 170141183460469231731687303715884105727.
Den Beweis erbrachte Edouard Lucas.
(1) Seite 73f.
Danach hat man mit Computerhilfe immer größere
mersennesche Primzahlen gefunden.
Die zuletzt (2009) gefundene Primzahl ist
|
Nr.47
|
2^42.643.801-1
|
12.837.064 Stellen
|
12.06.2009
|
Mehr über die Suche kann man auf den Webseiten http://www.mersenne.org/prime.htm
und http://www.primzahlen.de nachlesen.
Zusammengesetzte
Zahlen top
Definition
Zahlen, die nicht Primzahlen sind, heißen zusammengesetzte
Zahlen.
Für sie gibt es immer eine Produktdarstellung n=f1*
f2 mit 1<f1<n und 1< f2<n.
Man kann f1 und f2 weiter zerlegen und gelangt schließlich
zu einer Zerlegung in Primfaktoren, n=p1* p2* p3*
... *pt .
Gleiche Primfaktoren kann man als Potenzen zusammenfassen
 .
Nach dem "Hauptsatz der elementaren Zahlentheorie" lässt
sich jede zusammengesetzte Zahl >1 als Produkt von Primzahlen darstellen,
und zwar abgesehen von der Reihenfolge eindeutig.
Zahlenbeispiel: 300=2*2*3*5*5=2²*3*5²
Fast-Primzahl
(Semiprimzahl, semiprime)
Eine Zahl, die genau zwei Primfaktoren hat, heißt
Fast-Primzahl.
Die ersten Fast-Primzahlen sind
4, 6, 9, 10, 14, 15, 21, 22, ...
Die kleinsten Fast-Primzahlen mit
verschiedenen Primfaktoren sind 6, 10, 14, 15, 21, 22, 26, 33, ...
Sphenische
Zahl
Eine Zahl, die genau drei verschiedene Primfaktoren hat,
heißt sphenische Zahl.
Die sphenischen Zahlen auch Fast-Primzahlen
der Ordnung 3.
Die kleinsten sphenische Zahlen
sind 30, 42, 66, 70, 78, 102, 105, 110, ...
Glatte
Zahl (Smooth number)
Eine Zahl, die nur Primfaktoren, die kleiner oder gleich
k sind, heißt k-glatte Zahl.
Die Zweierpotenzen sind 2-glatte
Zahlen, 1, 2, 4, 8, 16, 32, 64, 128, ...
Die Zahl 2³*5³*7=7000
ist 7-glatt.
Zahlenspielereien top
In diesem Kapitel werden Ergebnisse aus Lietzmanns Buch
(1) von 1948 zusammengestellt und mit Computerhilfe überprüft
und ergänzt.
Aufeinander folgende Primzahlen
Die Summe der Primzahlen von 1 bis 59 ist 21².
Die Summe der Primzahlen von 3 bis 89 ist 31².
Die Summe der Primzahlen von 3 bis 107 ist 37².
Die Summe der Primzahlen von 3 bis 131 ist 43².
Die Summe der Primzahlen von 5 bis 101 ist 34².
Die Summe der Primzahlen von 11 bis 61 ist 22².
Die Summe der Primzahlen von 13 bis 37 ist 13².
Die Summe der Primzahlen von 37 bis 97 ist 30².
Die Summe der Primzahlen von 73 bis 103 ist 25².
Die Summe der Primzahlen von 73 bis 109 ist 29². |
6²=17+19
10²=47+53
12²=71+73
24²=283+293
42²=881+883 |
2³=3+5
6³=107+109
35=41+43+47+53+59
27=61+67
213=4093+4099 |
7*11*13*17*19=323 323
2*3*5*7*11
=11²+13²+17³+19²+23²+29² |
Palindrome
101
131
151
181
191
|
313
353
373
383
.
|
727
757
787
797
.
|
919
929
.
.
.
|
Kuriositäten top
Mirpzahlen
(Reversable primes)
Eine Mirpzahl ist eine Primzahl, die Primzahl bleibt,
wenn man sie rückwärts liest.
Ein Beispiel ist 149. Die rückwärts gelesene
Zahl 941 ist wieder eine Primzahl.
Die Eigenschaft, Mirpzahl zu sein, hängt vom Stellensystem
ab.
So ist 149 im Zweiersystem keine Mirpzahl: Es gilt 149=(10010101)2,
aber die Rückwärts-Zahl ist (10101001)2=169.
Der merkwürdige Name entsteht aus prim - mirp. Im
Englischen wird aus prime - emirp.
Mirpzahlen unter 1000
Die Mirpzahlen sind die schwarzen Zahlen.
Die grauen Zahlen sind Palindrome,
die Mirpzahlen sein könnten. Es ist üblich, sie nicht zu ihnen
zu zählen.
Mirpzahlen unter 100 im Dualsystem
(1011)2=11
(1101)2=13
(10111)2=23
(11101)2=29 |
(100101)2=37
(101001)2=41
(101011)2=43
(101111)2=47 |
(110101)2=53
(111101)2=61
(1000011)2=67
(1000111)2=71 |
(1010011)2=83
(1100001)2=97
.
. |
Kürzbare
Primzahlen
(Truncatable primes)
Kürzbare Primzahlen werden
an einem Beispiel erklärt. Eine kürzbare Primzahl ist
739397.
Entfernt man von rechts nacheinander
eine Ziffer, so entsteht die Zahlenfolge 739397, 73939, 7393, 739, 73,
7.
Entfernt man von links nacheinander
eine Ziffer, so entsteht die Zahlenfolge 739397, 39397, 9397, 397, 97,
7.
Das Besondere ist, dass alle neuen
Zahlen auch Primzahlen sind.
Es gibt Zahlen wie 739391133. Sie
sind nur rechts-kürzbar (right-truncatable ).
Und es gibt Zahlen wie 916237547,
die sind nur links-kürzbar (left-truncatable).
7
7 3
7 3 9
7 3 9 3
7 3 9 3 9
7 3 9 3 9 7
3 9 3 9 7
9 3 9 7
3 9 7
9 7
7 |
7 3 9 3 9 1 1 3 3
7 3 9 3 9 1 1 3
7 3 9 3 9 1 1
7 3 9 3 9 1
7 3 9 3 9
7 3 9 3
7 3 9
7 3
7 |
9 1 6 2 3 7 5 4 7
1 6 2 3 7 5 4 7
6 2 3 7 5 4 7
2 3 7 5 4 7
3 7 5 4 7
7 5 4 7
5 4 7
4 7
7
|
Permutierbare
Primzahlen (permutable primes)
Vertauscht man auf jede Weise die
Ziffern einer
permutierbaren Primzahl, so sind die so entstehenden
neuen Zahlen auch Primzahlen.
Ein Beispiel ist die Primzahl 733.
Die Zahl hat die Permutationen 337 und 373. Die beiden
neuen Zahlen sind auch Primzahlen.
Zyklische
Primzahlen
(Circular primes)
Vertauscht man die Ziffern einer
zyklischen
Primzahl zyklisch, so sind die so entstehenden neuen Zahlen auch Primzahlen.
Ein Beispiel ist die Primzahl 1193.
Die Zahl hat die Vertauschungen 1931, 9311 und 3119.
Die drei neuen Zahlen sind auch Primzahlen.
Repunit-Primzahlen
(Rep-unit primes)
Die Zahlen, die nur die Ziffer
1 enthalten und gleichzeitig Primzahl sind, heißen Repunit-Primzahlen.
Ein Beispiel ist R2=11,
die nächste Primzahl ist erst R19=1111111111111111111.
Primzahlen im
Internet top
Deutsch
H. B. Meyer
Das Sieb
des Eratosthenes
Wikibooks
Tabelle
der Primzahlen (2 bis 100.000)
Wikipedia
Primzahl,
Sieb
des Eratosthenes,
Primzahlzwilling,
Goldbachsche
Vermutung,
Dirichletscher
Primzahlsatz, Ulam-Spirale,
Kleiner
fermatscher Satz, Mirpzahl,
Truncatable
Prime,
Repunit,
SphenischeZahl,
Gaußsche
Zahl
Ferner in alphabetischer Reihenfolge
Englisch
Dario Alpern
Ulam's
Spiral (Applet)
Eric W. Weisstein (MathWorld)
Prime
Number,
Twin
Primes, Prime
Number Theorem, Goldbach
Conjecture, Emirp,
Semiprime,
Emirpimes,
Truncatable
Prime, Smooth
Number,
Rough
Number,
Semiprime,
Economical
Number, Equidigital
Number, Wasteful
Number,
GIMPS Home
Great Internet Mersenne
Prime Search
Robert Sacks
Number spirals
The
On-Line Encyclopedia of Integer Sequences
The prime numbers. A000040
Mersenne primes. A000668
Fermat numbers. A000215
Primes of form n^2 + n + 41. A155884
Repunits: (10^n - 1)/9. A002275
Emirps. A006567
Primes that are both left-truncatable and right-truncatable.
A020994
Absolute primes: every permutation of digits is a prime.
A003459
Semiprimes (or biprimes): products of two primes. A001358
Products of 3 distinct primes. A007304
Additive primes: sum of digits is a prime. A046704
Wikipedia
Prime
number,
Ulam spiral,
Twin
prime,
Goldbach's
conjecture, Fermat's
little theorem,
Dirichlet's
theorem on arithmetic progressions,Emirp,
Truncatable
prime,
Permutable
prime,Repunit
prime,
Smooth
number, Rough number,
Semiprime,
Sphenic
number, Gaussian
integer
More in alphabetical order
Referenzen top
(1) Walter Lietzmann: Sonderlinge im Reich der Zahlen,
Bonn 1948
(2) Maximilian Miller: Gelöste und ungelöste
mathematische Probleme, Leipzig 1982
(3) Jan Gullberg: Mathematics- From the Birth of Numbers,
New York, London 1997 (ISBN0-393-04002-X)
Feedback: Emailadresse auf meiner Hauptseite
URL meiner
Homepage:
https://www.mathematische-basteleien.de/
©
2009 Jürgen Köller
top |