Das chinesische Labyrinth

Carsten Elsner

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)

Literatur

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