Marco Polo (1254 bis 1324) hat am Hofe des chinesischen Kaisers eine Prüfung zu bestehen. Er geht gemeinsam mit zwei Mitbewerbern durch ein Labyrinth mit fünf Stationen. In jeder Kammer haben die Bewerber Aufgaben zu lösen, die alle mit der Teilbarkeit von Zahlen zu tun haben.
Erste Kammer: Diese einfache Abschätzung der möglichen Primteiler einer Zahl ist auch die Grundlage eines bereits in der Antike bekannten Verfahrens zur Ermittlung von Primzahlen: Setzt man die Primzahlen unterhalb 10 als bekannt voraus (also: 2, 3, 5 und 7), so erhält man alle Primzahlen zwischen 10 und 10 * 10 = 100, indem man aus den Zahlen 10, 11, ... , 100 erst alle Vielfachen von 2 streicht (also alle geraden Zahlen), dann alle Vielfachen von 3, von 5, und zuletzt alle Vielfachen von 7. Einige Zahlen werden dabei mehrfach gestrichen, wie z.B. die 30, da sie ein Vielfaches von 2, 3 und 5 ist. Übrig bleiben genau die 21 Primzahlen zwischen 10 und 100. Das ist das Sieb des Eratosthenes (3. vorchr. Jahrhundert).
Zweite Kammer: Hier hat Meister Wan einen tieferen Satz aus
der Primzahltheorie angewendet. Zunächst hat er nachgewiesen, dass die Zahl
3.240.001 auf zwei wesentlich verschiedene Weisen als Summe von zwei Quadraten
natürlicher Zahlen geschrieben werden kann:
18002 + 12 = 3.240.001 = 17992 + 602
Die linke Darstellung sieht man schnell der Zahl selbst an, die rechte ergibt
sich mit der Binomischen Formel:
18002 + 12 = (1800 - 1)2 + 2*1800
Nun weiß man aus der Primzahltheorie, dass eine Primzahl >2 überhaupt nur
dann als eine solche Summe von zwei Quadraten geschrieben werden kann, wenn sie
bei der Division durch 4 den Rest 1 lässt. Dieses Kriterium erfüllt 3.240.001
noch. Weiter weiß man aber auch, dass in diesem Fall nur eine solche
Darstellung existiert (abgesehen vom Tausch der Summanden untereinander). 3.240.001
kann also keine Primzahl sein, da sie zwei Darstellungen als Summe von zwei
Quadraten besitzt, und in der Tat ist 3.240.001 = 1.741 * 1.861.
Dritte Kammer: Was Meister Wan in dieser Kammer angewendet
hat, kennen spätere Zeiten als den Satz von Wilson (Sir John
Wilson, 1741 - 1793). Es handelt sich dabei um das bis heute theoretisch
einfachste Mittel zur Charakterisierung einer natürlichen Zahl als Primzahl:
Eine natürliche Zahl n>1 ist genau dann eine Primzahl, wenn sie das um 1
vermehrte Produkt aller Zahlen von 1 bis (n-1) teilt. Da 101 Primzahl ist,
teilt sie also die Zahl
1*2*3*4* ... *99*100 + 1,
und die ist somit selbst keine Primzahl. Da aber, wie Meister Wan erwähnt hat,
das Produkt der ersten (n-1) natürlichen Zahlen sehr rasch mit n anwächst
(Mathematiker nennen dieses Produkt heutzutage eine Fakultät), eignet sich das
Wilson-Kriterium leider nicht zum praktischen Nachweis einer größeren Zahl n
als Primzahl. Die obige Zahl aus der dritten Kammer beispielsweise hat genau
158 Dezimalstellen! Wollte man also mit dem Wilson-Kriterium 101 auf seine
Primzahleigenschaft prüfen, müsste man diese riesige Zahl berechnen.
Vierte Kammer: Hier haben sich unsere beiden Kandidaten
geirrt. Zwar hat man lange vermutet, dass für jede natürliche Zahl n die
zugehörige Fermatsche Zahl
(A) 2{2n} + 1
eine Primzahl darstellt (Pierre de Fermat, 1601 - 1665). Aber L. Euler
(1707 - 1783) hat diese Vermutung für n=5 widerlegt: die Zahl der vierten
Kammer ist durch 641 teilbar. Es ist bis heute nicht bekannt, ob es unendlich
viele Primzahlen von dieser Gestalt gibt. Für n>5 hat man noch keine weitere
gefunden! Die modernen Primzahlrekorde werden auch mit Zahlen von der Form 2p - 1
aufgestellt, wobei p selbst eine Primzahl ist. Diese Zahlen heißen Mersennesche
Zahlen. Man kennt einige Primzahlen p, für die 2p -1 wieder
eine Primzahl ist; unter 10.000 sind es 22 solche Primzahlen p. Die derzeit
größte bekannte Primzahl ist auch eine Mersennesche Primzahl:
2(6.972.593) - 1 ,
sie hat 2.098.960 Dezimalstellen (Stand Juni 1999).
Es ist allerdings recht einfach einzusehen, dass eine Zahl der Gestalt
2k + 1
wie aus der vierten Kammer nur dann überhaupt eine Primzahl sein kann, wenn sie
die Form (A) hat, also wenn der Exponent k selbst eine Zweierpotenz ist.
Fünfte Kammer: Der Mandarin hatte Recht als er Marco Polo auf seine falsche Wahl aufmerksam machte: Die Zahl in der fünften Kammer ist das Produkt der beiden Primzahlen 29.153 und 36.833. Dies ist jedoch nicht das zu ergründende Geheimnis, sondern die Antwort auf die Frage, warum für jede natürliche Zahl n>1 die Summe aus der n-ten Potenz von 4 und der vierten Potenz von n stets eine zusammengesetzte Zahl ist.
Marco Polos wahrscheinlichkeitstheoretische Vermutung zu der Dominanz
kleiner Teiler bei zusammengesetzten Zahlen wurde später streng bewiesen. Man
kann für jede natürliche Zahl a>1 nämlich Folgendes zeigen (siehe
Literaturverzeichnis, [5]): Unter den ersten m Zahlen 1,2,3, ... ,m konvergiert
der relative Anteil der Zahlen mit Primteilern oberhalb a (das ist die Anzahl
der Zahlen unter 1,2,3, ... ,m , von denen jede ausschließlich
Primteiler >=a hat, geteilt durch m) für immer größeres m gegen die Zahl
(1 - 1/2)*(1 - 1/3)*(1 - 1/5)*
(1 - 1/7)*(1 - 1/11)* ... *(1 - 1/p) ;
hierbei ist p die größte Primzahl unterhalb von a. Dieser Grenzwert und damit
der relative Anteil von Zahlen mit Primteilern oberhalb a wird für größer
gewähltes a also auch immer kleiner. So konvergiert der relative Anteil der
ersten m Zahlen mit Primteilern oberhalb 10 für wachsendes m gegen
(1 - 1/2)*(1 - 1/3)*(1 - 1/5)*
(1 - 1/7) = 8/35 = 0,228 571 ...
Also rund 23% aller Zahlen 1,2,3, ..., m (bei großem m) haben keine
Primteiler 2, 3, 5 und 7.
Der relative Anteil der Primzahlen unter den ersten m Zahlen (m>=2) ist
hingegen geringer als 2/ln (m). Hierbei ist ln (m) der natürliche Logarithmus
der Zahl m. Dieser relative Anteil strebt mit wachsendem m also gegen null.
Primzahlen unter den ersten m Zahlen sind bei immer größer gewähltem m also
auch immer dünner gesät. (bb)
[1] G.Hardy / E.M.Wright:
An Introduction to the Theory of Numbers, fifth edition, Clarendon Press,
Oxford (1984)
[2] K.Prachar: Primzahlverteilung, Springer-Verlag , Berlin - Göttingen - Heidelberg (1957)
[3] A.E.Ingham: The
Distribution of Primes Numbers, Cambridge Tracts in Mathematics and
Mathematical Physics, no. 30 (1990).
[4] D.M.Bressoud / S.Wagon:
A Course in Computational Number Theory, Springer - Textbooks (mit CD Rom)
(2000).
[5] R.Warlimont: Eine Bemerkung zu einem Ergebnis von N.G. de Bruijn, Monatshefte für Mathematik 74 (1970), 273-276.