Zahlentheorie fur Einsteiger. Eine Einfuhrung fur Schuller, Lehrer, Studierende und andere Interessierte Mit Online-Service zum Buch 3834812137, 9783834812131 [PDF]

Zitiervorschau

Andreas Bartholome | Josef Rung | Hans Kern

Zahlentheorie für Einsteiger Eine Einführung für Schüler, Lehrer, Studierende und andere Interessierte Mit einem Geleitwort von Jürgen Neukirch 7., aktualisierte Auflage STUDIUM

VIEWEG+ TEUBNER

Bibliografische Information Der Deutschen Nationalbibliothek Die Deutsche Nationalbibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet über abrufbar.

Dr. Andreas Bartholome" und Josef Rung unterrichten am Hans-Leinberger-Gymnasium in Landshut. Anschrift: Jürgen-Schumann-Straße 20, 84034 Landshut Dr. Hans Kern unterrichtet am Schyren-Gymnasium in Pfaffenhofen/Ilm. Anschrift: Niederscheyerer Straße 4, 85276 Pfaffenhofen

Online-Service: http://www.andreasbartholome.de

1. Auflage 1995 2., überarbeitete Auflage 1996 3., verbesserte Auflage 2001 4., durchgesehene Auflage 2003 5., verbesserte Auflage 2006 6., überarbeitete und erweiterte Auflage 2008 7., aktualisierte Auflage 2010 Alle Rechte vorbehalten © Vieweg+Teubner Verlag | GWV Fachverlage GmbH, Wiesbaden 2010 Lektorat: Ulrike Schmickler-Hirzebruch | Nastassja Vanselow Der Vieweg+Teubner Verlag ist ein Unternehmen von Springer Science+Business Media. www.viewegteubner.de Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Jede Verwertung außerhalb der engen Grenzen des Urheberrechtsgesetzes ist ohne Zustimmung des Verlags unzulässig und strafbar. Das gilt insbesondere für Vervielfältigungen, Übersetzungen, Mikroverfilmungen und die Einspeicherung und Verarbeitung in elektronischen Systemen. Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme, dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei zu betrachten wären und daher von jedermann benutzt werden dürften. Umschlaggestaltung: KünkelLopka Medienentwicklung, Heidelberg Druck und buchbinderische Verarbeitung: MercedesDruck, Berlin Gedruckt auf säurefreiem und chlorfrei gebleichtem Papier. Printed in Germany ISBN 978-3-8348-1213-1

Geleitwort „Von der Mathematik habe ich nie etwas verstanden!" Wann immer wir Mathematiker uns als Mathematiker zu erkennen geben, wird uns dieses freimütige Bekenntnis der Ignoranz serviert, meist im Tonfall der Genugtuung und mit der Gebärde des Triumphes, so als ob man sich damit in die Gemeinschaft der normalen Menschen einreiht, denen eine menschliche Seele innewohnt und ein warmes Herz in der Brust schlägt. An der Mathematik liegt es nicht, dass sie in so misslichem Ansehen steht. Wer ihr im echten Sinne begegnet ist, weiß, dass sie eine Welt der Wunder und der Schönheit ist, und wird sich vor dem obigen Ausruf ebenso verwahren wie vor stolzem Bekenntnis, nicht zu wissen, wer Beethoven ist. So muss es wohl an der Art liegen, wie sie unterrichtet wird, die Mathematik. Das vorliegende Buch von A. Bartholome , J. Rung und H. Kern setzt diesem Zerrbild unserer Wissenschaft die schöne Wahrheit entgegen. Es ist an die Schüler und - mit gutem Grund - an die Lehrer des Gymnasiums gerichtet. Ihr Gegenstand ist die Zahlentheorie, die „Königin unter den mathematischen Wissenschaften". Die Autoren haben für die Schule ein vorbildliches kleines Werk geschaffen. Es lebt von dem Wissen erfahrener Lehrer, von der Liebe echter Mathematiker zu ihrem Metier und von einer heiteren Lebendigkeit der Darstellung. Kluge Auswahl und weise Beschränkung des Stoffes zeichnet die Autoren als treffliche Lehrmeister aus. Nirgendwo werden „Klappern" zu billigem Erfolg herangezogen, überall handelt es sich um echte und wesentliche mathematische Probleme und Ereignisse, die in verständlicher Weise dargestellt werden, und von denen man sicher sein kann, sie auch im Bereich moderner Forschung anzutreffen. Die Darstellung ist in einer schwungvollen, verführerischen Sprache gefasst, die im jugendlichen Leser eigene Vorstellung und eigene Phantasie hervorzurufen vermag. Die vielen Aufgaben sind so gestellt, dass sie dem erfolgreichen Bearbeiter zum echten mathematischen Erlebnis werden können. Er wird später mit Freude berichten: „Ich habe einmal die Mathematik verstanden". Das Buch ist als ein Addendum zum gewöhnlichen mathematischen Unterricht am Gymnasium zu verstehen. Würde dieser Unterricht von seiner quälenden Überladenheit befreit und auf allen Stufen in dieser Weise geführt, so könnte sich das Bild der Mathematik in der Gesellschaft zum Besseren wenden. Regensburg, Dezember 1994 Prof. Dr. Jürgen Neukirch

Vorwort „...Was Sie mir von Ihrer Seite wie irn Auftrag von Herrn Euler sagen, ist zweifellos viel glänzender. Ich meine das schöne Theorem von Herrn Euler über Primzahlen und seine Methode, zu testen, ob eine gegebene Zahl, wie groß auch immer sie sein möge, eine Primzahl ist oder nicht. Was Sie sich bemühten, mir über den Gegenstand zu berichten, erscheint mir sehr scharfsinnig und Ihres großen Meisters würdig. Aber finden Sie nicht, dass es für die Primzahlen beinahe zuviel Ehre ist, soviel Gedanken über sie zu verbreiten, und sollte man nicht Rücksicht auf den verwöhnten Geschmack unserer Zeit nehmen? Ich unterlasse es nicht, allem, was aus Ihrer Feder kommt, Gerechtigkeit widerfahren zu lassen, und bewundere Ihre großen Geisteskräfte, um die misslichsten Schwierigkeiten zu überwinden; aber meine Bewunderung verstärkt sich, wenn das Thema zu nützlichen Erkenntnissen führen kann. Ich schließe hierin die gründlichen Untersuchungen über die Stärke von Balken ein, von denen Sie sprechen..." soweit Daniel Bernoulli in einem Antwortbrief an Nicolaus Fuß, den Assistenten Eulers (nach A. Weil). Wir werden dennoch nicht über die Stärke von Balken berichten, sondern den Primzahlen die Ehre antun. Dazu wollen wir die Leser dieses Buches im Klassenzimmer abholen und ins so helle und doch geheimnisvolle Reich der Zahlen führen. Dieses Buch handelt von dem, was schon die kleinen Kinder können und kennen: vom Zählen und den natürlichen Zahlen 1,2,3 und so weiter. Das Buch wurde für die Schulbank geschrieben: für Pluskurse oder Freiwillige Arbeitsgemeinschaften in Mathematik und Informatik, als Anregung für Jugend - forscht - Arbeiten oder als Hilfe für das Lösen von Aufgaben aus dem Bundeswettbewerb Mathematik. (Es wurde in den Schuljahren 1991/92 und 92/93 in einem Pluskurs am Hans-Leinberger-Gymnasium in Landshut verwendet. Teile von ihm dienten bei der Durchführung eines Proseminars an der Universität Regensburg.) Dieses Buch möchte etwas von dem spielerischen und experimentellen Charakter der Zahlentheorie vermitteln, es wird zeigen, wie man den Computer sinnvoll einsetzen kann- und es soll verdeutlichen, welche Grenzen diesem Rechenknecht gesetzt sind. Auch der Lehrer und Liebhaber wird sicher einiges Spannendes in dem Buch entdecken. In der Schule bleiben ja leider das Rechnen und die Algebra meist im rein Formalen. Dagegen ist die bescheidenste Geometrieaufgabe oft mit einer kleinen Erkenntnis verbunden. Auch im Algebraunterricht könnte das so sein. Es ist ein Unterschied, ob man um des Rechnens willen rechnet, oder ob man rechnet, weil man einer aufregenden Entdeckung auf der Spur ist. Es ist etwas anderes, die binomischen Formeln zu üben um des übens willen, oder ob man mit ihrer Hilfe Erkenntnisse über die Zahlen sammelt. Wir hoffen, der Leser wird hier einiges finden. Wer unser Buch studiert, soll dabei viel Handwerkliches mitbekommen, auch Anwendungen des doch etwas trockenen Algebrastoffes lernen (viele der über

vii 300 Aufgaben sind Routine, aber so manche sind sehr schwer und fordern alle Kraft und Phantasie!). Sie oder er soll aber auch ein wenig Theorie mitbekommen. Denn nur eine gute Theorie zeigt uns, „was dahintersteckt". Schließlich - und vielleicht ist dies das wichtigste - möge das Buch allen zur Erbauung und zum Trost dienen! Inhaltlich haben wir uns als Ziel gesteckt, einen wichtigen Primzahltest zu verstehen, wie er von fertigen Computerprogrammen zur Zahlentheorie verwendet wird. Dabei gehen wir nicht immer geradlinig auf das Ziel zu, sondern verweilen gerne am Wegrand, ja nehmen auch Umwege auf uns, wenn wir dort eine bunte Blume zu entdecken meinen. An viel Schönem mussten wir vorübereilen und manch Wichtiges (Überlegungen zur Rechenzeit etwa) achtlos liegen lassen. Aber der Leser weiß ja, der Mensch ist endlich (besonders die Autoren) und muss sich mit dem Unvollkommenen zufriedengeben. Dennoch hoffen wir, der Leser wird sich auf dieser Reise über die vielen schönen Kostbarkeiten von Herzen freuen. Den einzelnen Abschnitten dieser „Reise" haben wir Zitate aus Sonja Kowalewskajas Jugenderinnerungen vorausgestellt und wir würden uns sehr freuen, möchte unsere Leserin (Leser) am Ende doch mit Sonja ausrufen: „... ungeachtet all der Klagen und des Jammers (ob der Fehler der Verfasser) war die Fahrt doch herrlich"(Kowalewski [1968]). Wer sich zu sehr über die Fehler ärgert, möge an das Gebet der heiligen Theresia von Avila denken: „Herr! Lehre mich die wunderbare Weisheit, dass ich mich irren kann". Viel Vergnügen bei der Arbeit mit diesem Buch wünschen die Verfasser. Andreas Bartholome, Josef Rung, Hans Kern Zur sechsten und siebten Auflage Als wir die sechste Auflage vorbereiteten, haben wir uns entschlossen, die Teile über das Rechnen mit langen Zahlen und die zugehörigen Pascalprogramme wegzulassen. Wir haben sie durch Mathematik ersetzt. Unter anderem war es unser Ziel an ein paar Beispielen das Verallgemeinern zu lehren. Das ist eine hohe Kunst, die man nur durch Tun lernen kann. So wie man Singen nur durch Singen lernt. Sehr oft wird ja von den zur Zeit allgemeinsten Voraussetzungen ausgegangen. Mit diesen werden dann eine Fülle von Sätzen bewiesen und auf Seite 93 des Buches kommt das erste Ergebnis, welches man „mit Händen greifen" kann. Erst auf Seite 200 erfährt der gutwillige Leser, das was er eigentlich schon immer wissen wollte. Mathematik wird oft von „oben herab" gelehrt. So lernen Studenten gleich in der ersten Woche ihres Studiums Körper, Vektorräume, Ringe und Kategorien kennen. Keine anderen Beispiele als Q und E

viii sind ihnen bis dahin begegnet. Sie ahnen nicht, was endliche Körper sind. Eine spannende Frage zu diesen Begriffen kann ihnen nicht einfallen. Wir versuchen an manchen Stellen den Weg „von unten" zu wandern. Wir lernen die Primzahlen kennen und den Satz von der eindeutigen Primfaktorzerlegung. Uns begegnen unendlich viele endliche Körper Z/pZ, wenn p eine Primzahl ist. In einem zweiten Schritt wird gefragt: Kann man ähnliche Argumente in einer wenig veränderten Situation auch verwenden. So studieren wir den Ring Z[] dabei ist die Zahl des goldenen Schnittes, die Lösung der Gleichung x2 — x — 1 = 0. Hier gelten ähnliche Gesetze wie in den ganzen Zahlen, den guten alten Freunden. So bekommt das Buch zwei Stränge. Einen Lesestrang, der durch Z, die Menge der ganzen Zahlen, führt. Ein zweiter Lesestrang führt durch %[] den Ring der „goldenen Zahlen". Abschnitte, die sich mit den goldenen Zahlen befassen sind mit einem „goldigen" Bildchen verziert. Dieser zweite Weg zeigt sich im Rückblick. Man kennt den Verlauf des ersten Weges und sieht so leichter wie andere Pfade verlaufen. Hat man den zweiten Weg studiert, so erfährt man wieder Neues über die ganzen Zahlen. Neue Fragen nach weiteren Verallgemeinerungen tauchen auf. In diesem Büchlein können wir Ihnen nicht nachgehen. Für diesen zweiten Lesestrang ist allein Andreas Bartholome verantwortlich. Für alle dort auftretenden Dunkelheiten und Fehler ist nur er zu beschimpfen. In der siebten Auflage haben wir einige Fehler beseitigt und versucht manches klarer zu schildern. Auch haben wir uns entschlossen die Programme etwas an den Rand zu drängen. Wir trennen sie klar ab vom übrigen Stoff. Wen das langweilt überlese sie. Andererseits helfen sie, sich mit wenig Aufwand eine Fülle von Beispielen zu verschaffen. Als Programmiersprache haben wir Lisp gewählt. Es ist eine sehr alte Sprache, die zunächst wegen der vielen Klammern ungewohnt scheint. Aber diese Sprache ist sehr nahe an der Mathematik. Alles ist Funktion. Man wird nicht durch unklare Begriffe wie Objekte, Klassen etc. abgelenkt. Für das, was wir benötigen, reichen jeweils ein paar Zeilen Programm aus. Wir haben nur Software verwendet die unter der GNU Lizenz steht. Und zwar clisp und ein Computeralgebrasystem Maxima. Es basiert auf Lisp und ist auch völlig frei. Die Programme funktionieren in jedem Betriebssystem. Noch eine Bemerkung zu den Aufgaben: Die Fülle und - manchmal - die Schwierigkeit sollen nicht entmutigen. Viele sind zum reinen Üben da. Sie laden zum Wandern in der geistigen Landschaft ein. Manche der Aufgaben sollen den Leser anregen die Gedanken im Text in leicht abgewandelten Situationen nachzuvollziehen. Sehr lehrreich ist es, sich selbst Aufgaben zu stellen. Eigene Fragen bewegen innerlich mehr. Geduldiger denkt man über sie nach und lernt daher am meisten. Andere Aufgaben ragen wie Wände hoch. Sie sind für die Schwin-

ix

delfreien, die ihre Kraft am Felsen erproben wollen. Wem sie zu steil erscheinen, kann und sollte sie als Belebung der Landschaft wahrnehmen und vielleicht erst beim zweiten Lesen einen Kletterversuch wagen. Auf der Internetseite http://www.andreasbartholome.de/ kann der Leser zu einigen Aufgaben Lösungen und zu manchen Themen des Buches Ergänzungen finden. Unsere E-Mail-Adressen sind: j osefrungOgmx.de [email protected] Landshut im Dezember 2009, die Autoren.

Inhaltsverzeichnis 1

Vollständige Induktion 1.1 Das kleinste Element 1.2 Das Prinzip vom Maximum 1.3 Das Induktionsprinzip 1.4 Zusammenfassung

2

Euklidischer Algorithmus 2.1 Teilen mit Rest 2.2 Stellenwertsysteme 2.3 Größter gemeinsamer Teiler 2.4 Rechnen mit Kongruenzen 2.5 Gruppen und Ringe 2.5.1 Gruppen 2.5.2 Homomorphismen 2.5.3 Ringe 2.6 Geheimniskrämerei 2.7 Primzahlen 2.7.1 Natürliche Primzahlen 2.7.2 Ein kleiner Spaziergang zum Primzahlsatz 2.7.3 Primelemente in anderen Ringen 2.8 Der chinesische Restsatz 2.9 Die Euler-Punktion

25 25 28 35 44 50 51 59 66 75 80 80 93 95 101 113

3

Der 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9

122 122 127 129 135 147 151 153 156 161

kleine Fermatsche Satz Kleiner Fermat Die Ordnung einer Zahl modulo einer Primzahl Primitivwurzeln Quadratische Reste S. Germains Beitrag zum Problem von Fermat Verschlüsseln mit dem Kleinen Fermat Logarithmieren modulo p Einheiten in Primpotenzmoduln Fermat in anderen Ringen

1 1 10 10 21

Inhaltsverzeichnis 4 Die 4.1 4.2 4.3 4.4 4.5 4.6 4.7

Jagd nach großen Primzahlen Der negative Fermat-Test Pseudoprimzahlen Pseudoprimzahlen zur Basis a und Carmiehael-Zahlen Ein probabilistischer Primzahltest Starke Pseudoprimzahlen Der Lucas Test RSA- Verschlüsselung

xi 165 165 171 177 179 181 188 192

1 Vollständige Induktion „Wir öffnen, eines nach dem anderen, die Äuglein, beeilen uns aber keineswegs, aufzustehen und uns anzukleiden. Zwischen dem Augenblick des Erwachens und dem, da wir uns anziehen müssen, vergeht noch eine lange Zeit...Unsinn schwätzen." (Kowalewski [1968], Seite 9)

1.1 Das kleinste Element Als G o t t die Zahlen schuf g a b er ihnen als W o h n u n g eine G e r a d e . E r setzte ein R a d auf einen P u n k t m i t N a m e n „Null" u n d setzte es in Schwung. Eine sinnreiche Vorrichtung hinterließ nach jeder vollen U m d r e h u n g eine Markierung. Seitdem breitet sich der Zahlenstrahl a u s . Sein nicht vorhandenes E n d e verschwindet im Nebel der Unendlichkeit.

„Alles ist Zahl" ( P y t h a g o r a s ) •

•

•

•

•

0

1

2

3

•••

•

>• oo Nebel

Etwas Langweiligeres als diese sich ins Unendliche ausbreitenden Kilometersteine, wir nennen sie die natürlichen Zahlen, kann es eigentlich nicht geben. Weit gefehlt! E s wäre öde, wenn wir ein alles durchdringendes A u g e h ä t t e n u n d ein Hirn, in d e m alle Zahlen s a m t ihren Eigenschaften P l a t z fänden. So aber komm e n der Nebel, die Dunkelheit u n d die Rätsel. Diese Menge birgt Geheimnisse, die bis h e u t e nicht aufgedeckt sind. I m m e r wieder t a u c h e n auf der K a r t e des Landes N = { 0 , 1 , 2 , 3 , 4 . . . } höhere Gebirge und tiefere Täler auf. Neue Zahlenkontinente erscheinen und ehemals weiße Gebiete erhalten Farbe. Wollen wir diese Landschaften erforschen, so müssen wir uns ein paar Grundtatsachen klarmachen. D a s Prinzip v o m kleinsten Täter Denken wir uns einen Dämon, ausgeschickt mit einem Eimer roter Farbe. Er malt zufällig die Kilometersteine an oder auch nicht. Wir verfolgen ihn. Haben wir genügend Zeit, und hat der Dämon überhaupt etwas angemalt, so werden wir irgendwann auf einen ersten

1 Vollständige Induktion

2

roten Stein treffen. Ist also von einer gewissen Eigenschaft, die sinnvollerweise natürliche Zahlen haben können („rot" gehört nicht dazu), die Rede, und gibt es überhaupt Zahlen mit dieser Eigenschaft, dann gibt es auch eine kleinste (den kleinsten Täter). Jede nichtleere Teilmenge der natürlichen Zahlen hat ein kleinstes Element. N ist wohlgeordnet. Du wirst zu Unrecht, lieber Leser, denken: Was nützen solch allgemein philosophische Erörterungen beim Lösen einer Aufgabe? Betrachten wir dazu ein paar Beispiele: 1. Der junge Hippasos von Metapont hatte sich bei Sonnenaufgang aufgemacht und - wie es sein Meister Pythagoras befahl - einen Morgenspaziergang in eine ruhige Bucht mit Sandstrand gemacht. Seine Seele und Verstand sollten in der Einsamkeit zur Harmonie finden.

Fig. 1.1: Pentagramm

Als Meditationsthema hatte er sich die Lehre seines Meisters „Alles ist Zahl" und das Geheimzeichen des Bundes der Pythagoräer, das Pentagramm, gewählt. Die Blume im Sand regte ihn dazu an. Er fragte sich: Gibt es ein gleichschenkliges Dreieck mit Basiswinkel 72° und dessen Seitenlängen natürliche Zahlen sind? Der Dämon hat alle natürlichen Zahlen x anzumalen, die als Basen solcher Dreiecke auftauchen können. Wir werden ihn lange verfolgen können und keine solche Zahl finden. Angenommen es gibt überhaupt solche Zahlen. Dann gibt es eine kleinste solche natürliche Zahl x. Sei y der dazugehörige Schenkel. Es ist x < y, da dem größeren Winkel die größere Seite gegenüberliegt. Wir betrachten die Diagonale AC. Es ist die Winkelhalbierende des Winkels a = /.BAD. Sie schneidet den Schenkel [B, D] in F. Dann sind die Dreiecke ABFA und ADAF gleichschenklig. Also ist FD = x und FB — y — x. Da y und y — x natürliche Zahlen sind, hat das Dreieck ABFA wieder die gewünschten Eigenschaften. Es ist aber y — x < x im Widerspruch zur Wahl von x.

2. Betrachten wir nochmal die Zeichnung. Die Dreiecke ABFA und AABD sind ähnlich. Das heißt es ist y-x

x2 + xy - y2 = 0

Wir befreien uns von den geometrischen Voraussetzungen des vorigen Beispiels und fragen:

1.1 Das kleinste

3

Element

Gibt es natürliche Zahlen x , | / e N \ { 0 } mit x2+xy-y2=Q

(1.1)

Angenommen es gäbe überhaupt solche Paare natürlicher Zahlen. Dann ist für solche Paare (x,y): y2 = xy + x2 und daher y > x. Damit ist (y — x,x) ein weiteres solches Zahlenpaar. Denn (y - x)2 + x(y - x) - x2 = (-l)(x2 +xy-

y2) = 0.

Gibt es eine Lösung der Gleichung 1.1 in natürlichen Zahlen, so gibt es eine Lösung (#, y) mit kleinstmöglichem x. Dann ist (y—xy x) eine weitere Lösung. Aber y—x ist kleiner als x. Dies widerspricht der Wahl des Zahlenpaars (x, y). Den Gedanken zur Beantwortung der Frage hat uns die Geometrie eingegeben, obwohl wir rein algebraisch argumentiert haben. Beherzige daher lieber Leser: Auch wenn Du der „Arithmetica" huldigst, vergesse die Göttin „Geometria" nicht. 3. Wir spiegeln zunächst die natürlichen Zahlen an dem Nullpunkt und erhalten die Menge der ganzen Zahlen Z = {..., - 3 , - 2 , - 1 , 0 , 1 , 2 , 3 , . . . } . An den Punkten der Zahlengeraden, an denen normalerweise die ganzen Zahlen stehen, sind natürliche Zahlen so hingeschrieben, dass jede Zahl gleich dem arithmetischen Mittel ihrer beiden Nachbarn ist. Wir erinnern uns: Das arithmetische Mittel zweier Zahlen ist g^. Beispielweise könnten endliche Ausschnitte aus unserm Zahlenmuster so: 2 2 2 2 oder so: 6 9 12 15 aussehen. Wie sieht ein mögliches Zahlenmuster für die ganze Zahlengerade aus? Natürlich kannst du solch ein Zahlenmuster herstellen, wenn du an jeden Punkt die gleiche Zahl schreibst. Aber ist es möglich, ein solches Muster mit verschiedenen Zahlen herzustellen? Wir versuchen, das obige (zweite) Muster fortzusetzen. Nach rechts gibt es keine Probleme: 6 9 12 15 18 2 1 . . . , und es ist klar, wie man fortzufahren hat. Nach links müssten wir auch unendlich weit kommen. Doch hier: ???? 0 3 6 9 müssten wir links von der 0 die —3 (wieder links davon die —6) hinschreiben, und das sind nach unserer Vereinbarung keine natürliche Zahlen. Analysieren wir, „wo" wir gescheitert sind! Doch offenbar bei den kleinen Zahlen. Aber könnte es nicht einen anderen Anfang geben, so dass wir unser gewünschtes unendliches Muster erhalten? Dazu schauen wir uns den Punkt an, an dem die kleinste natürliche Zahl m (Minimum) steht sowie seine beiden Nachbarn: m < a, m < b. Wäre m < a oder m < b, so wäre 2m < a + 6. Andererseits ist 2m = a + 6, da m arithmetisches Mittel von a und b ist. Daher gilt: m = a = b. Dann müssen aber auch die Nachbarn von a und b gleich m sein und so fort. Damit ist bewiesen, dass alle natürlichen Zahlen, die wir gemäß unserer Verabredung an die Punkte der Zahlengeraden schreiben wollen, gleich sein müssen.

4

1 Vollständige

Induktion

Die wichtigste Idee in den Beispielen war das Prinzip vom kleinsten Element: In jeder nichtleeren Teilmenge der natürlichen Zahlen gibt es eine kleinste Zahl. Formulieren wir dieses Prinzip nochmals: (Kleinstes Element). Jede nichtleere Teilmenge T von N enthält eine kleinste Zahl m. Das heißt, für alle t e T gilt: m (c) \/ä, wobei a nicht Quadratzahl ist, irrational ist. 3. Zeige: a) Die Gleichung x2 + xy — y2 = 2 hat in N2 keine Lösung. b) Die Gleichung x2 + xy — y2 — 3 hat in N2 keine Lösung. c) Die Gleichung x2 + xy — y2 — 5 hat in N2 unendlich viele Lösungen. Unendlich ist hier in folgendem Sinn gemeint. Es gibt ein Verfahren welches immer wieder eine neue Lösung erzeugt. d) Zeige allgemein: Die Gleichung x2 +xy -y2 — d mit d € N hat unendlich viele Lösungen oder gar keine. Wie erreicht man alle Lösungen? 4. Die Basis eines gleichschenkligen rechtwinkligen Dreiecks sei x und die Schenkellänge sei y. a) Zeige wie im Beispiel 2: Es gibt kerne natürlichen Zahlen, die diese Bedingungen erfüllen. Beachte dazu die Zeichnung nebenan. b) Entwickle aus der Zeichnung ein Verfahren, aus einer Lösung I

1 der Gleichung x2—2y2 = 7

eine weitere zu erhalten. c) Wieviel Lösungen aus N2 hat die Gleichung: x2 - 2y2 = 2? 5. Gegeben ist der Term H(x, y) = x2 — 2 • x • y — y2.

1.1 Das kleinste Element

7

a) Zeige: Die Gleichung H(xyy) = 1 hat in N2 unendlich viele Lösungen, indem du ein Verfahren angibst aus einer Lösung eine neue zu erhalten. b) Zeige: Die Gleichung H(x, y) = d mit d € N hat keine oder unendlich viele Lösungen. 6. Zeige: die Gleichung x2 — axy — y2 = l hat unendlich viele Lösungen für a G N. D i e Multiplikation der alten Ä g y p t e r und der Computer Die alten Ägypter waren keine besonders guten Mathematiker - jedenfalls im Vergleich zu den Babyloniern. Aber multiplizieren mussten sie dennoch, obwohl sie nur addieren konnten. Sie ersannen folgende pfiffige Methode. Wir prod x y prod + x - y erklären sie zunächst an einem Beispiel. ? 0 13 21 Es soll die Aufgabe 13 • 21 gelöst werden. ? 13 13 20 Auf einem Papyrus fand man folgende Lis? 13 26 10 te. Bevor du nun weiterliest, lieber Leser, ? 13 52 5 versuche selbständig herauszubringen, wie ? 65 52 4 der ägyptische Schuljunge gerechnet hat. Es ? 65 104 2 sieht sehr kompliziert aus. Vertiefe dich et? 65 208 1 was in die drei linken Spalten und du wirst ? 273 208 0 sicher bald mit dem Verfahren eine selbstge273 stellte Aufgabe lösen können. Zum Beispiel: 21 • 13. Hier das Verfahren: 1. Zunächst werden in die Spalten x,y die beiden Faktoren geschrieben. In die Spalte prod schrieb der Ägypter die Zahl 0. 2. Ist y ungerade, so wird zu prod der Wert von x addiert und der Wert von y um 1 erniedrigt, x wird beibehalten. 3. Ist y gerade, so wird x mit 2 multipliziert und y durch 2 dividiert. 4. Das Verfahren wird so lange durchgeführt, bis sich y = 0 ergibt. In der Spalte prod wird dann das Ergebnis abgelesen. Woher wissen wir, ob die Ägypter stets zum richtigen Ergebnis kamen? Dazu füllt man (auf einem Blatt Papier) die rechte Spalte mit den Fragezeichen gemäß der Anweisung prod+x-y aus und erkennt: 0+13-21 = 13+13-20 = 13+26-10 = 13 + 5 2 - 5 . . . = 273 + 208 • 0, das Ergebnis. Für den Anfänger mag dies als „Beweis" - oder sagen wir besser als Plausibilitätsbetrachtung genügen. Manch einen wird vielleicht doch interessieren, wie man den Beweis logisch sauber,

1 Vollständige

Induktion

„hygienisch rein", aufschreibt. Auch wer an dieser Art von Beweisführung wenig Interesse zeigt, sollte ihn irgendwann mal schon deshalb lesen, weil das Prinzip vom kleinsten Element wieder Verwendung rindet. Wir besinnen uns auf die kennzeichnenden Eigenschaften des ägyptischen Rechenverfahrens. Das Ergebnis der ägyptischen Multiplikation bezeichnen wir wie im c l i s p Programm mit: aemul(a,b). Dann gilt: • aemul(a,0)

= 0 für alle a e N.

• Ist 6 eine ungerade Zahl, so ist aemul(a, b) := aemul(a, b — 1) + a. • Ist b eine gerade Zahl, so ist aemul(a,b)

:= aemul(a • 2,6/2) .

Dadurch ist für alle b e N aemul(ay b) erklärt. Es ist für alle a € N aemul(a, 1) = a-1 = a. Angenommen, es gäbe irgend eine natürliche Zahl 6, bei der die Ägypter ein anderes Multiplikationsergebnis berechnen als wir. Dann gibt es auch eine kleinste Zahl 6 > 0. 1. Fall: b ist ungerade. Dann ist aemul(a,b) 1) + a = a • b. Es ist ja (6 - 1) < b.

= aemul(a,b — l) + a = a-(b —

2. Fall: b ist gerade. Dann ist aemul(a, b) = aemul{a • 2, b/2) = a • 2 • (6/2) = a • 6. Wieder ist 6/2 < 6. Also erhalten die Ägypter für alle Zahlen das gleiche Ergebnis wie wir. Computerecke: 1. Lisp ist eine funktionale Sprache. Alles ist Funktion. Die Funktionsnamen werden vor die Argumente geschrieben. So ergibt (+ 2 3)==> 5, die Summe der Zahlen 2,3. Eine Summe kann beliebig viele Argumente haben ( + 1 2 3 4 5 )==> 15 und (+)==> 0. Genau dasselbe gilt für die Multiplikation. Der wichtigste Datentyp in Lisp ist die Liste, ( l i s t 1 2 3) macht aus den drei Zahlen 1,2,3 eine Liste dieser Zahlen. 2. Wir wollen die Funktion F : E 2 —> R2, von der im Beispiel 2 die Rede war in Lisp programmieren. (def un f ib (a) Der Funktion wird eine Liste aus zwei Zah( l i s t (nth 1 a) len übergeben. Sie gibt eine Liste von zwei (+ (nth 0 a) Zahlen zurück. Die erste Zahl ist ursprüng(nth 1 a)) lieh zweite Zahl. Die zweite Zahl ist die ) Summe der ersten und zweiten Komponen) te der übergebenen Liste. So ergibt: (fib ( l i s t 1 1)) ==>(! 2) 3. Die zu fib inverse Funktion soll programmiert werden:

1.1 Das kleinste

Element

9

(defun fibinvers(a) ( l i s t (- (nth 1 a) (nth 0 a)) (nth 0 a) ) )

Der Funktion wird eine Liste aus zwei Zahlen übergeben. Sie gibt eine Liste von zwei Zahlen zurück. Die erste Zahl ist die Differenz aus der zweiten und ersten Komponente der übergebenen Liste. Die zweite Zahl ist die ursprünglich erste Zahl. So ergibt: (fibinvers ( l i s t 1 2))=> (1 1)

4. Übersetzen wir die ägyptische Art der Multiplikation in ein Lispprogramm, so erhalten wir Folgendes. Probelauf: a b 532 53 0 532 532 52 532 1064 26 532 2128 13 2660 2128 12 2660 4256 6 2660 8512 3 11172 8512 2 11172 17024 1 28196 17024 0

(defun aemulr(a b) (if (= b 0) 0 (if (evenp b) (aemulr (* a 2) (/ b 2)) (+ (aemulr a (- b 1)) a) )) )

prod

Diese Methode ist von prinzipiellem Interesse, da Computer sehr schnell verdoppeln und addieren kömien. Da sind sie Spezialisten.

Wir werden in den Übungen die gleiche Methode anwenden, um ein sehr schnelles Verfahren zur Potenzierung einer natürlichen Zahl mit einer natürlichen Zahl zu erhalten. Aufgaben: 7. Berechne mit der „ägyptischen Multiplikation": (a) 32 • 31,

(b) 31 • 32,

(c) 172,

(d) 111-1231.

8. Schreibe ein Programm, welches folgendes leistet: Es berechnet für drei Zahlen a, 6, c den Ausdruck a + b-c. Verwende die gleiche Methode wie bei aemul. Nenne die Funktion r u s s ( a , b , c). 9. aepot(a b) Ersetzen wir im ägyptischen Multiplikationsalgorithmus Verdoppeln durch Quadrieren, Addieren durch Multiplizieren und 0 durch 1, so erhalten wir eine computergeeignete Möglichkeit, schnell zu potenzieren. Berechne mit dieser Methode a) xy = 3 7 . Berechne ebenso 7 3 und 4 18 . b) Schreibe ein Programm und teste es. c) Beweise die Richtigkeit des Verfahrens.

1 Vollständige

10

Induktion

1.2 Das Prinzip vom Maximum Bei den folgenden Aufgaben nutze man die nahezu selbstverständliche Tatsache, dass es in einer endlichen Menge von (reellen) Zahlen eine größte (und eine kleinste) gibt. (Prinzip v o m M a x i m u m ) In jeder endlichen Menge reeller Zahlen gibt es eine größte Zahl. Aufgaben: 10.

a) Sieben Schüler haben zusammen 100 Münzen. Keine zwei haben gleich viele Münzen. Zeige, dass es drei Schüler gibt, die zusammen mindestens 50 Münzen haben. b) In jedem konvexen Fünfeck kann man drei Diagonalen so auswählen, dass man aus ihnen ein Dreieck konstruieren kann. c) (Bundeswettbewerb Mathematik 1970/71) Von fünf beliebigen Strecken wird lediglich vorausgesetzt, dass man je drei von ihnen zu Seiten eines Dreiecks machen kann. Es ist nachzuweisen, dass mindestens eines der Dreiecke spitzwinklig ist. (Anleitung: E s s e i a > 6 > c > d > e > 0 . Führe die Annahme, dass die Dreiecke (a, 6, c) und (c, d, e) nicht spitzwinklig sind, mittels des „verallgemeinerten Pythagoras" a2 > b2 -f c2 usw. zu einem Widerspruch zur Dreiecksungleichung.)

1.3 Das Induktionsprinzip Erstaunliches gibt es aus der Welt der natürlichen Zahlen zu berichten. Betrachten wir zum Beispiel 1 = l2;

1 + 3 = 22;

1 + 3 + 5 = 32.

Wir sind mutig und vermuten: (*)

1 + 3 + 5 + . . . + (2n - 1) = n 2 .

Die Summe der ersten n ungeraden Zahlen ist n 2 . Ziehen wir zum Beweis das Prinzip vom kleinsten Untäter zu Rate. Wir betrachten die „Ungültigkeitsmenge" U = {n e N|l + 3 + 5 + . . . + (2n - 1) ^ n 2 } . Gibt es eine Zahl, für die unsere Behauptung nicht gilt, so ist U nicht leer. Also enthält U ein kleinstes Element m. Es muss m > 1 sein. Für m — 1 gilt die Formel. Also: l + 3 + ... + ( 2 - ( m - l ) - l ) l + 3... + (2m-l)

= =

(ra-1)2. (ra-l)2 + 2ra-l

| + (2m - 1) = m2.

1.3 Das Induktionsprinzip

11

Dem widerspricht, dass m aus der Ungültigkeitsmenge gewählt wurde. U ist also leer. Der Gültigkeitsbereich der Formel ist daher N. Wir wollen fürs erste diesen Beweis vergessen und uns dem Problem noch einmal nähern. Es liegt näher, den Gültigkeitsbereich G einer Formel zu betrachten. Wir suchen ja meist nach Zahlen, die eine Formel erfüllen, nach Tätern nicht nach Untätern. So probieren wir mehrere Zahlen aus. 0 erfüllt die Gleichung. Denn addieren wir überhaupt keine Zahlen so erhalten wir 0 = 02. Durch Rechnen wiesen wir nach: 1,2,3,4 erfüllen die Gleichung, liegen im Gültigkeitsbereich. Auf dieser „Basis" vermuten wir: Alle natürlichen Zahlen erfüllen unsere Formel. Wir verhalten uns ähnlich wie der Physiker, der 5 Messungen macht und dann ein Naturgesetz vermutet. Vorsicht sollte uns folgende Geschichte lehren, die der Mathematiker Ernst Eduard Kummer (1810 - 1893) in seiner Vorlesung zur Zahlentheorie erzählte: „Meine Herren, 120 ist teilbar durch 1,2,3,4 und 5; jetzt werde ich aufmerksam, ob 120 nicht durch alle Zahlen teilbar ist. Ich probiere weiter und finde, sie ist auch durch 6 teilbar; um nun ganz sicher zu gehen, versuche ich's noch mit 8, mit der 10, mit der 12, mit der 15, und schließlich auch mit 20 und 24.... Wenn ich jetzt Physiker bin, dann sage ich: Es ist sicher, dass 120 durch alle Zahlen teilbar ist." Wir sind also sehr kritisch. Wir beauftragen einen Supercomputer, uns möglichst viele Beispiele zu berechnen. Aber irgendwann wird der beste Computer auf eine Grenzzahl g stoßen. Jenseits dieser Zahl ist ihm das Rechnen unmöglich, einfach weil größere Zahlen nicht mehr in seinen Speicher passen. Wir gehen noch einen entscheidenden Schritt weiter. Angenommen, unser Computer hat die Gleichung für g bestätigt. Also 1 + 3 + .. . + ( 2 . 0 - 1 ) l + 3 + . . . + [2-(