|
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 sinnvoll, sie nicht mitzuzählen.
Da besteht unter den Mathematikern heute Einigkeit.
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) 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:.....
|
|
n
an
|
1
43
|
2
23
|
3
29
|
4
61
|
5
71
|
6
83
|
7
97
|
8
113
|
9
131
|
10
151
|
|
Die Folge der Primzahlen kann bis zur Primzahl a40=1681 fortgesetzt
werden.
Dann allerdings folgt mit a41=41²+41+41 eine zusammengesetzte
Zahl.
Auch für größere Werte von n liefert die Formel aufeinander
folgende Primzahlen.
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
Die Zahlen 2n+1 heißen fermatsche Zahlen.
|
Die ersten 7 Zahlen zu an= 2n+1:
|
|
n
an
|
1
3
|
2
5
|
3
17
|
4
257
|
5
65537
|
6
4294967297
|
7
18446744073709551617
|
|
Die ersten 5 Zahlen 3, 5, 17, 257, 65537 sind Primzahlen, die
sich als 2n + 1 mit n=2m schreiben lassen.
Mehr Primzahlen kennt man nicht. Es ist bis heute auch nicht bekannt,
ob es überhaupt unendlich viele fermatsche
Primzahlen
gibt.
Die 5. fermatsche 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^m)+1 seien prim.
In der Theorie der Kreisteilung spielen
fermatsche Primzahlen eine wichtige Rolle.
Nur dann ist ein regelmäßiges n-Eck mit Zirkel und Lineal
konstruierbar, wenn n eine fermatsche
Primzahl
ist.
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=1007 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
Hans-Michael Elvenich
Primzahlen
H. B. Meyer
Das Sieb des Eratosthenes
Jens Bernheiden
Wie
viele Primzahlen gibt es?
Walter Fendt
Primzahlentabelle
bis 1 000 000 000 000
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
Ferner in alphabetischer Reihenfolge
Willi Jeschke
Kleine und große
Primzahlen
Wolfgang Stanglmeier
Wolfs Faktorisator
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
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:
http://www.mathematische-basteleien.de/
©
2009 Jürgen Köller
top |