Primzahlen
Inhalt dieser Webseite
Was ist eine Primzahl?
Sieb des Eratosthenes
Euklids Überlegung
Folgen von Primzahlen
Verteilung der Primzahlen
Goldbachsche Vermutung
Primzahlzwillinge
Besondere Primzahlen
Zusammengesetzte Zahlen
Zahlenspielereien
Kuriositäten
Primzahlen im Internet
Referenzen
.
Zur Hauptseite    "Mathematische Basteleien"

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

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=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 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

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 PrimzahlsatzUlam-Spirale,
Kleiner fermatscher Satz, Mirpzahl, Truncatable Prime, Repunit, SphenischeZahl, Gaußsche Zahl
Ferner in alphabetischer Reihenfolge
Bellsche Zahl
Carmichael-Zahl
Cullen-Zahl
Fastprimzahl
Fröhliche Zahl
Glückliche Zahl
Pell-Folge
Pseudoprimzahl
Ruth-Aaron-Zahlen
Ulam-Folgen
.
.

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 TheoremGoldbach Conjecture, Emirp, Semiprime, Emirpimes,
Truncatable Prime, Smooth Number, Rough Number, Semiprime
Economical NumberEquidigital NumberWasteful 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 conjectureFermat's little theorem, Dirichlet's theorem on arithmetic progressions,Emirp, Truncatable prime, Permutable prime, Repunit prime, Smooth number, Rough number
Semiprime, Sphenic numberGaussian integer
More in alphabetical order
Almost prime
Bell number
Blum integer
Carmichael number
Carol number
Cullen number
Happy number
Hilbert number
Idoneal number
Interprime
Kynea number
Lucas number
Lucky number
Motzkin number
Padovan sequence
Pell number
Perrin number
Powerful number
Practical number
Primefree sequence
Proth number
Pseudoprime
Thabit number
Ulam numbers
Unusual number
Wedderburn-Etherington number
Woodall number
Zeisel number


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