Elementare Zahlentheorie

Rei n h o Id Re m m e rt Peter U IIrich El~rn~n rc Zahl~nth~ori~ Dritte Auflage Birkh~user Basel. Boston 9 Berlin ...

Author: Reinhold Remmert | Peter Ullrich

81 downloads 1078 Views 13MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

Rei n h o Id Re m m e rt Peter U IIrich

El~rn~n rc Zahl~nth~ori~ Dritte

Auflage

Birkh~user Basel. Boston 9 Berlin

Autoren: Reinhold Remmert Westf~lische Wilhelms-Universit~t Mathematisches Institut Einsteinstral3e 62 D-48149 MOnster

Peter Ulldch Universit~t Koblenz-Landau Campus I
Erste Auflage 1987 Zweite Aut]age 1995

Bibliografische Information der Deutschen Bibliothek Die Deutsche Bibliothek verzeichnet diese Publikation in der Deutschen Nationalbibliografie; detaillierte bibliografische Daten sind im Internet Qber abrufbar.

ISBN 9 7 8 - 3 - 7 6 4 3 - 7 7 3 0 - 4 Birkh~user V e d a 9, Basel - B o s t o n - Berlin

Das Werk ist urheberrechdich 9eschOtzt. Die dadurch begrOndeten Rechte, insbesondere die des Nachdrucks, des Vortrags, der Entnahme yon Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der Vervielf~ltigun 9 auf anderen Wegen und der Speicherun 9 in Datenverarbeitungsanlagen,bleiben, auch bei nur auszugsweiser Verwertun 9, vorbehaUten. Eine Vervielf~ltigung dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen der gesetzlichen Bestimmungen des Urheberrechtsgesetzes in der jeweils geltenden Fassung zul~issig. Sie ist grunds~tzlich verg0tungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des Urheberrechts. 9 2008 Birkh~user Verlag, Postfach 133, CHo4010 Basel, Schweiz Ein Unternehmen von Springer Science+Business Media Gedruckt auf s~urefreiem Papier, hergestellt aus chlorfrei 9ebleichtem Zellstoff. TCF oo Printed in Germany ISBN 978-3-7643-7730-4

e-ISBN 978-3-7643-7731-1

987654321

www.birkhauser.ch

Vorwort Die Mathematik ist die K6nigin der Wissenschaften,und die Arithmetik ist die K6nigin der Mathematik. C. F. GAuss ,,Gegenstand der elementaren Zahlentheorie sind in erster Linie die natiirlichen Zahlen 1, 2, 3. . . . . Nach KRONECKER hat sie der liebe Gott geschaffen, nach DEDEKIND der menschliche Geist. Das ist je nach Weltanschauung ein unl6sbarer Widerspruch oder ein und dasselbe. Ffir die Zahlentheorie ist es gleichgfiltig, wer die natfirlichen Zahlen geschaffen hat. Sie stelit sich auf den Standpunkt, dab sie jedenfalls da sind und uns wohlbekannt sind." Mit diesen eindrucksvollen S/itzen beginnt H. HASSE seine ,,Vorlesungen fiber Zahlentheorie" [7]. Der von HASSEbezogene Standpunkt wird heute von nahezu allen Autoren, die fiber Zahlentheorie schreiben, geteilt. Auch wir sehen es in diesem Buch nicht als unsere Aufgabe an, den Begriff der natfirlichen Zahl axiomatisch einzuffihren, sondern setzen das Rechnen mit diesen Zahlen als bekannt voraus. Das unverg/ingliche Problem der Zahlentheorie ist das der Teilbarkeit: Ist eine Zahl durch eine andere teilbar oder nicht? Alle in diesem Buch behandelten Fragen sind Variationen dieses einen Themas. S/itze und Begriffsbildungen der elementaren Zahlentheorie, die seit alters her auch h6here Arithmetik genannt wird, bedfirfen kaum einer Motivierung. Jeder Leser ist bereits vom Grundschul- und Gymnasialunterricht mit vielen Fragestellungen der Zahlentheorie (bewul3t oder unbewul3t) wohlvertraut: Wir alle haben schon grol3e Zahlen in Primfaktoren zerlegt, Hauptnenner als kleinste gemeinsame Vielfache bestimmt und irgendwann auch Divisionen mit Rest durchgeffihrt. So ist es leicht und vielfach sogar fiberflfissig, den Leser noch besonders ffir die Probleme des Textes zu motivieren. Das vorliegende Buch umfal3t den Stoff einer vierstfindigen Vorlesung im Sommersemester. Es richtet sich an Dozenten und Studenten der Mathematik, Lehrer an Realschulen und Gymnasien, - jeden, der sich ffir ein weit fiber dreitausend Jahre altes Teilgebiet der Mathematik interessiert. Der Leser lasse sich nicht durch die relative L/inge des Textes irritieren: Wir haben es vorgezogen, auch solche Begriffe, die an sich bekannt sind, noch einmal zu besprechen. Insbesondere setzen wir beim Leser an Vorkenntnissen neben elementarem Schulstoff nur eine gewisse Vertrautheit mit der Mengenschreibweise voraus. Diese Ausffihrlichkeit der Darstellung macht den Text auch zum

6

Vorwort

Selbststudium geeignet; hierzu tragen ebenfalls die Aufgaben am Ende eines jeden Paragraphen bei, die den behandelten Stoff einfiben und vertiefen. Wir haben uns bemfiht, das Wechselspiel zwischen konkretem und abstraktem Schliel3en herauszustellen. Der Leser wird je nach Veranlagung konkretes oder abstraktes Vorgehen besonders schfitzen. Ein Werturteil, welcher Art yon Zahlentheorie der Vorrang gegeben werden mug, ist objektiv nicht m6glich: Der uralte Streit, welcher Zugang der didaktisch bessere ist, wird immer aufs neue entflammen; er erscheint vielen Mathematikern heute ebenso unverstfindlich wie der Streit der Byzantiner fiber das Geschlecht der Engel. Wir sehen uns aul3erstande, dem Leser einen K6nigsweg zu beschreiben, der unmittelbar zum Verst/indnis dieses Textes fiihrt. Die von Didaktikern seit eh und je diskutierte Frage: ,,Wie lernt man Mathematik?'" wird wohl allen Bemfihungen zum Trotz niemals eine allgemein zufriedenstellende Antwort finden. Die Situation scheint immer noch dieselbe zu sein, wie ffir d'ALEMBERT, der einem zweifelnden Anf/inger gesagt haben soil: ,,Allez en avant, la foi vous viendra".* Dem einen Leser wird das Verstfindnis der Begriffe und Sfitze vorrangig sein, und er wird Beweise nicht bis in letzte Detail analysieren; dem anderen Leser wird gerade das voile Erfassen der Beweise oberstes Ziel sein. Gut beraten ist natiirlich jeder, der sich diese beiden Gesichtspunkte gleichberechtigt zu eigen macht. Wir haben ein ausffihrliches Inhaltsverzeichnis zusammengestellt, das aufgrund seiner spezifizierten Untergliederung einen detaillierten {)berblick fiber den Gesamttext gibt. Auf einige Besonderheiten des Inhalts m6chten wir dennoch an dieser Stelle hinweisen, so auf die Untersuchung der quadratischen Zahlbereiche 7Z[\//m] und Q[v/'m], insbesondere der Gaul3schen Zahlbereiche 2~[i] und Q [i] und des Dedekindschen Ringes 77[,r - 5], den ~t-adischen Algorithmus, der die Verallgemeinerung der wohlvertrauten Dezimalbruchentwicklung ffir beliebige Grundzahlen ~/liefert, die Verwendung des Satzes von FERMAT-EULERals Verschlfisselungsverfahren. /

Aul3erdem haben wir mehr als sonst fiblich historische Bemerkungen in den Text eingewobcn. Das Buch ist aus Vorlesungen entstanden, die der filtere von uns mehrfach gehalten hat. Wertvolle Hinweise erhielten wir von Herrn M. KOECHER. Bei der Herstellung des Manuskriptes haben uns Frau U. PETERNELL und Herr M. STEINSIEK unterstfitzt. Ihnen gilt unser Dank. Der Birkh/iuser Verlag hat die Drucklegung des Textes mit bewiihrter Sorgfalt betreut. * ..Arbeiten Sie nur tiichtig, der Glaube wird Ihnen schon kommen."

Vorwort

7

Wir schliegen diese einleitenden Bemerkungen mit jenen denkwtirdigen Sfitzen, die GAUSS 1847 Abhandlungen" schrieb: ,,Die H6here Arithmetik bietet einen unersch6pflichen Reichthum an interessanten Wahrheiten dar, und zwar an solchen, die nicht vereinzelt, sondern in innigem Zusammenhange stehen, und immer neue, ja unerwaxtete Verkntipfungen erkennen lassen, je weiter die Wissenschaft sich ausbildet. Ein grol3er Theil ihrer Lehren gewinnt auch einen neuen Reiz durch die Eigenthtimlichkeit, dal3 gewichtige Lehrsfitze in einfach ausgepr~gtem Inhalt uns leicht durch Induction zugeftihrt werden, deren Begrtindung doch so tief liegt, dal3 man erst nach vielen vergeblichen Versuchen dazu gelangt, und dann meistens erst auf beschwerlichen ldinstlichen Wegen, wfihrend die einfacheren Methoden lange verborgen bleiben. [...1 Von den eigenthtimlichen Sch6nheiten dieser Gebiete haben Alle sich angezogen geftihlt, die darin besch~ftigt gewesen sind: keiner aber hat es wohl so oft ausgesprochen wie E u 1 e r, der namentlich in fast allen seinen zahlreichen, zur H6heren Arithmetik geh6renden Aufsfitzen die Erklfirung wiederholt, wie viele Freude ihm diese Forschungen machen, und wie sehr er darin eine Erholung von und eine StS.rkung zu andern der unmittelbaren practischen Anwendung nS.her liegenden Arbeiten finde." Mtinster/Westf., 18. September 1986

R. REMMERT, P. ULLRICH

Vorwort zur 2. Auflage Gegentiber dem Erstdruck wurden nur Fehler und Unebenheiten beseitigt. Ftir diesbeztigliche Hinweise danken wir insbesondere den Herren B. ARTMANN (Daxmstad0, W. GREVE-KRAMER (G6ttingen), M. KNESER (G6ttingen), M. PETERS (Mtinster), H. ROSCHLAU (Kappeln) und St. SPRINGMANN (G6ttingen). Mtinster/Westf., 26. Januar 1995

R. REMMERT, P. ULLRICH

Vorwort zur 3. Auflage Neben einigen Erg~inzungen wurden wieder Gl~itmngen vorgenommen. Ftir Hinweise danken wir den Herren J. ELSTRODT (Mtinster), M. KNESER (?), H. MOLLER (Mtinster) und M. PETERS (Mtinster). Mtinster/Westf. und Koblenz, 30. April 2007

R. REMMERT, P. ULLRICH

Lesehinweise Ein Zitat 3.4.2 bedeutet Abschnitt 2 im Paragraphen 4 des Kapitels 3; entsprechend wird die Aufgabe 2) zu Paragraph 4 in Kapitel 3 als ,,Aufgabe 3.4.2)" zitiert. Innerhalb eines Kapitels wird die Kapitelnummer, innerhalb eines Paragraphen auch die Paragraphennummer weggelassen. Die mit * gekennzeichneten Paragraphen bzw. Abschnitte k/Snnen bei der ersten Lekttire tibergangen werden.

a,, cq (',4 c4

~

oo ~,

oo

__

- -

~

C

~ oo

I eq

- -

eq or

i~<;, m

m

m~ N

4q

oo

..o

E

co oo

[ ,,-q

I tr~ c-3o

'~ 3o

~ _

=

~ L~

so

r~"

~ r,'-~ 3o

oo

r~, 30 J

I

C 84

eL)

r--- I

J

,,,q oo ,<3

n c~ ,,,o oc oc

"

b4

E

m

Inhaltsverzeichnis

Kapitel 1

Primzerlegung in 77 und Q Einleitung w0

Natfirliche, ganze und r a t i o n a l e Z a h l e n . . . . . . . . . . . . . . . 1. D e r Ring 77 der g a n z e n u n d der K 6 r p e r Q der r a t i o n a l e n Z a h l e n 2. A n o r d n u n g v o n 77 und II~ 3. P r i n z i p v o m kleinsten E l e m e n t und Induktionsprinzip 4. D i v i s i o n mit Rest

13

w1

Teilbarkeit. P r i m z a h l e n . . . . . . . . . . . . . . . . . . . . . . 1. Teilbarkeitsbegriff 2. P r i m z a h l e n - 3. Existenz unendlich vieler P r i m z a h l e n - 4. U n z e r l e g b a r k e i t und P r i m e i g e n s c h a f t

22

w2

D e r H a u p t s a t z der e l e m e n t a r e n Z a h l e n t h e o r i e . . . . . . . . . . . . 1. Existenz einer P r i m z e r l e g u n g 2. E i n d e u t i g k e i t der P r i m z e r l e g u n g 3*. D e r E i n d e u t i g k e i t s b e w e i s v o n ZERMELO 4*. Kritische B e m e r k u n g e n

28

w3

A n w e n d u n g e n des H a u p t s a t z e s 1. Anzahl aller positiven Teiler 3. S u m m e aller positiven Teiler 5. M e r s e n n e s c h e P r i m z a h l e n 6.

33

w4

Z a h l e n t h e o r i e im K 6 r p e r Q . . . . . . . . . . . . . . . . . . . . 1. P r i m z e r l e g u n g in Q -- 2. Irrationalit~itsaussagen 3*. Z u r Irrationalit~it und T r a n s z e n d e n z v o n e und 7t 4. Die Vielfachheitsfunktion Wp(a) 5*. A.gyptische Bruchdarstellungen, F i b o n a c c i m e t h o d e

. . . . . . . . . . . . . . . . . . 2. P r o d u k t aller positiven Teiler 4. V o l l k o m m e n e Z a h l e n Fermatsche Primzahlen

42

Kapitel 2

Theorie des gri/flten gemeinsamen Teilers in Z Einleitung G r 6 B t e r g e m e i n s a m e r Teiler . . . . . . . . . . . . . . . . . . . . 1. G r 6 B t e r g e m e i n s a m e r Teiler zweier ganzer Z a h l e n 2. E u k l i d i s c h e r Algorithmus 3. I d e a l t h e o r e t i s c h e C h a r a k t e r i s i e r u n g des gr6Bten g e m e i n s a m e n Teilers - 4. G r 6 B t e r g e m e i n s a m e r Teiler endlich vieler g a n z e r Z a h l e n - 5. Teilerfremdheit - 6. R e d u z i e r t e B r u c h d a r s t e l l u n g 7. Kleinstes g e m e i n s a m e s Vielfaches

55

w

O b e r die Verteilung und D a r s t e l l u n g v o n P r i m z a h l e n . . . . . . . . . 1. E l e m e n t a r e Verteilungss/itze - 2. G r o B e r P r i m z a h l s a t z - 3*. Die C h e b y s h e v s c h e Absch~itzung - 4. G r o B e P r i m z a h l e n 5. P r i m z a h l e n in arithmetischen Progressionen 6. P r i m z a h l e n als Werte v o n P o l y n o m e n

70

w

Zahlentheoretische Funktionen . . . . . . . . . . . . . . . . . . 1. M u l t i p l i k a t i v e F u n k t i o n e n - 2. Eulersche ~0-Funktion 3. DmICHLET-Faltung -- 4. S u m m a t o r f u n k t i o n e n

81

10

Inhaltsverzeichnis

Kapitel 3

Zahlentheorie in ailgemeinen lntegritiitsringen Einleitung w0

Integrit'atsringe . . . . . . . . . . . . . . . . . . . . . . . . . 1. Allgemeine Begriffe der Ringtheorie 2. Polynomringe 3. Quadratische Zahlbereiche

95

Teilbarkeitstheorie in Integrit~tsringen . . . . . . . . . . . . . . . 1. Grundbegriffe der Teilbarkeitstheorie 2. Normfunktionen 3. Zerlegungssatz ffir Integrit/itsringe mit monotoner Normfunktion

101

w

Faktorielle Ringe, Hauptidealringe und euklidische Ringe . . . . . . . 1. Faktorielle Ringe 2. Hauptidealringe 3. Euklidische Ringe 4. Beispiele 5*. Weiterfiihrende Ergebnisse 6. Zerlegung von Primzahlen in quadratischen Zah|bereichen 7. Charakterisierung von Primzahlen in quadratischen Zahlbereichen

111

w

Zahlentheorie in faktoriellen Ringen und in Hauptidealringen . . . . . 1. Zahlentheorie in faktoriellen Ringen 2. Theorie des gr6gten gemeinsamen Teilers 3. Integrit/itsringe mit ggT 4. Charakterisierung faktorieller Ringe. Zerlegungssatz fiir noethersche Ringe

126

Kapitel 4

Der g-adische AIgorithmus Einleitung w1

,q-adische und Cantorsche Darstellung natfirlicher Zahlen . . . . . . . 0. Historisches Prfiludium 1. Existenz und Eindeutigkeit der y-adischen Darstellung 2. Rechnen im ,q-adischen System 3*. Cantorsche Darstellung natfirlicher Zahlen

139

w2

,q-adische Darstellung rationaler Zahlen . . . . . . . . . . . . . . . 1. ,q-adischer Algorithmus 2. Endliche ,q-adische Darstellungen 3. Periodische y-adische Darstellungen

148

w3

Periodizit~itss/itze. Satz von FERMAT-EULER . . . . . . . . . . . . . 1. Kriterien fiir reine Periodizit/it 2. Charakterisierung von Vorperioden und Perioden 3. Zyklische Ziffernverschiebung 4. Satz von

158

F E R M A T - E u LER

w4"

(Anhang) ,q-adische Entwicklung als Approximationsverfahren . . . . . 1". Approximationskriterium 2*. Konstruktion yon Briichen zu .q-periodischen Folgen 3*..q-adische Entwicklungen und unendliche Reihen

168

Kapitel 5

Kongruenzen und Restklassenringe Einleitung w1

Kongruenzenrechnung . . . . . . . . . . . . . . . . . . . . . . I. Kongruenzrelation. Elementares Rechnen mit Kongruenzen 2. Kongruenzen zu verschiedenen Moduln 3. Neuner- und Elferprobe

179

Inhaltsverzeichnis 4. Der Satz von FERMAT-EULER als Kongruenzsatz Satzes von FERMAT-EULER in der K r y p t o g r a p h i e

11 5. Anwendung des

w

Satz yon WILSON. Chinesischer Restsatz . . . . . . . . . . . . . . . 1. Lineare Kongruenzen -- 2. Der Satz von WILSON 3. Ein Satz von EULER 4. Chinesischer Restsatz

192

w

Restklassenringe und P o l y n o m k o n g r u e n z e n . . . . . . . . . . . . . I. Restklassenringe 2. Primideale und maximale Ideale 3. P o l y n o m k o n g r u e n z e n und Polynomgleichungen 4. Satz von LAGRANGE

201

Kapitel 6

Prime Restklassengruppen Einleitung w1

Elementare G r u p p e n t h e o r i e . . . . . . . . . . . . . . . . . . . . I. Gruppenbegriff. Beispiele aus der Zahlentheorie 2. Untergruppen, Kongruenz, O r d n u n g einer G r u p p e 3. O r d n u n g eines Gruppenelementes 4. Verallgemeinerungen der Sfitze yon FERMAT-EULER und WILSON

213

w2

Zyklische prime Restklassengruppen . . . . . . . . . . . . . . . . 1. Allgemeines Zyklizitfitskriterium 2. Existenz von Primitivwurzeln zu Primzahlen 3. Zyklizitfit der G r u p p e n Z*,, 4. Kleine Primitivwurzeln zu pn 5. Zyklizitfit der G r u p p e n Z~po 6. Bestimmung aller zyklischen G r u p p e n )Z*,

223

Kapitel 7 Theorie der quadratischen Rcste Einleitung wI

Quadratische Reste . . . . . . . . . . . . . . . . . . . . . . . 1. Quadratische Reste m o d u l o einer beliebigen Zahl m > 1 2. Quadratische Reste m o d u l o Prirnzahlpotenzen 3. Quadratische Reste m o d u l o einer ungeraden Primzahl 4. Legendresches Restsymbol 5. Gaul3sches L e m m a

237

w2

Quadratisches Reziprozitfitsgesetz . . . . . . . . . . . . . . . . . 1. Formulierung des Reziprozitfitsgesetzes. Beispiele - 2. Beweis des Reziprozitfitsgesetzes 3*. Analytischer Beweis des Reziprozit/itsgesetzes nach EISENSTEIN 4. Das Reziprozitiitsgesetz ffir das Jacobische Restsymbol 5. Anwendungen des allgemeinen Reziprozitfitsgesetzes

248

Literatur

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Namenverzeichnis Sachverzeichnis Symbolverzeichnis

266

. . . . . . . . . . . . . . . . . . . . . . . . . . .

267

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

269

. . . . . . . . . . . . . . . . . . . . . . . . . . .

274

13

Kapitel 1 Primzerlegung in Z und Q In diesem Kapitel wird Stoff dargestellt, der zum Teil aus dem Schulunterricht bekannt ist. Insbesondere stellt der Paragraph 0 die dem Leser wohlvertrauten Eigenschaften der natiirlichen, ganzen und rationalen Zahlen zusammen, die wir im weiteren unbewiesen voraussetzen. Den Schwerpunkt des Kapitels bildet der Paragraph 2, wo der Hauptsatz der elementaren Zahlentheorie behandelt wird, d.h. der Satz v o n d e r eindeutigen Darstellbarkeit jeder natfirlichen Zahl 4:0 als Produkt von Primzahlen. Dieser Satz wird im elementaren Rechenunterricht stillschweigend als richtig unterstellt, da aufjener Stufe ja fiberhaupt noch nicht von mathematischer Strenge die Rede sein kann. Leider wird dadurch, wie die Erfahrung immer aufs neue lehrt, bei manchem Leser der ganz unberechtigte Eindruck entstanden sein, dab dieser Darstellungssatz unmittelbar einsichtig sei und keiner Begrfindung bediirfe. Es ist ein Hauptanliegen des ersten Kapitels, diesen irrigen Eindruck, der sich bei vielen ffir immer festgesetzt hat, zu korrigieren. Die Anwendungen des Hauptsatzes der elementaren Zahlentheorie, die in den letzten beiden Paragraphen besprochen werden, demonstrieren dessen mathematische Kraft. Die getroffene Auswahl ist naturgem~iB willkiirlich: Der Leser sollte vor allem ein Geffihl daffir bekommen, wie hfiufig der Hauptsatz bei der L6sung von Fragen, die auch einem mathematischen Laien nahegebracht werden k6nnen, verwendet werden mug.

w0

Natiirliche, ganze und rationale Zahlen

In diesem Paragraphen stellen wir ffir uns wichtige Tatsachen fiber natfirliche, ganze und rationale Zahlen zusammen. Da unser Thema ,,Zahlentheorie" und nicht ,,Aufbau des Zahlensystems" heil3t, sind wir nicht an einer streng logischen Begrfindung des Zahlenbegriffs ab ovo interessiert. Vielmehr soll dieser Paragraph dem Leser all jene Dinge in Erinnerung bringen, die er schon von der Schule her kennt und die zu den allgemeinen mathematischen Grundkenntnissen geh6ren.

1. Der Ring Z der ganzen und der Kfrper Q der rationalen Zahlen. Die Zahlen 1, 2, 3,... heiBen seit altersher natiirliche Zahlen. Wir vcreinbaren, dab auch die Null eine natiirliche Zahl ist, und bezeichnen die so erweitcrte Menge mit N, also

Der Ring 7/der ganzen und der K6rper II) der rationalen Zahlen

14 N'=

!.0.!

{0,1,2,3 . . . . . 1001,1002 . . . . }.

Da h/iufig die Menge {1,2, 3 . . . . ] aller yon 0 verschiedenen natfirlichen Zahlen betrachtet wird, ist es zweckm/iBig, auch ffir diese Menge ein Symbol einzuffihten. Wir verabreden folgende Bezeichnung: N•

{1,2,3 . . . . }.

Es gilt also: N = {0} w N • . Die Menge N ist eine echte Teilmenge der Menge ) 7 ' = { .... - 3, -- 2, -- 1,0, 1,2,3 . . . . } aller g a n z e n Zahlen. Es gibt gute Griinde daffir, die zahlentheoretischen Untersuchungen sofort in 7/, (und nicht in N ) durchzufiihren: Z u m einen 1/iBt sich in )7 uneingeschr/inkt subtrahieren und daher einfacher rechnen als in N ; zum anderen ist ffir spfitere Verallgemeinerungen )7 und nicht N der richtige Ausgangsbereich. Wir setzen das Rechnen mit ganzen Zahlen als bekannt voraus, stellen aber die grundlegenden Rechenregeln in zwei Aussagen zusammen:

Additionsregeln: In 27 gibt es eine Addition + , d. h. j e z w e i E l e m e n t e n a, b 9 27 ist ein (drittes) E l e m e n t a + b 9 27, zugeordnet. Fiir alle a, b, c 9 7Z gilt." 1) (a + b) + c = a + (b + c) 2) a + b = b + a

(Assoziativgesetz). (Kommutativgesetz).

3) Z u j e d e m P a a r a , b ~ )7 gibt es genau ein x 9 7Z mit x + b = a, m a n schreibt x = a

b.

Der Leser beachte, dab die Aussage 3) i.a. nicht in N gilt, da a - b nicht notwendig eine natfirliche Zahl ist: So gibt es z.B. kein x in N mit x + 4 = 3. Man faBt die Additionsregeln zusammen, indem man sagt: Die M e n g e )7 ist bzgl. der Addition + eine k o m m u t a t i v e Gruppe. Start k o m m u t a t i v e G r u p p e sagt man auch abelsche G r u p p e (zu Ehren des norwegischen M a t h e m a t i k e r s Niels Henrik ABEL, 1802 1829).

Multiplikationsregeln:

In )7 gibt es eine M u l t i p I i k a t i o n ., d.h. j e z w e i E l e m e n t e n a, b 9 27 ist ein (drittes) E l e m e n t a 9b ~ 27 zugeordnet. Fiir alle a, b, c 9 )7 gilt."

1) 2) 3) 4)

(a.b).c=a.(b-c)

(Assoziativgesetz) .

a.b=b.a

(K o m m u t a t i v g e s e t z ) .

(a+b)-c=(a'c)+(b'c) 1 .a=a.

(Distributivgesetz).

Statt a 9b schreibt man auch einfach ab. M a n faf3t die Additionsregeln und die Multiplikationsregeln dahin zusammen, dab m a n sagt: Die M e n g e Z ist bzgl. der Addition + und der M u l t i p l i k a t i o n . ein k o m m u t a t i v e r R i n g mit E i n s e l e m e n t .

Eine wichtige Eigenschaft von Z ist die Nullteilerfreiheit." A u s a b = 0 mit a, b 9 )7 f o l g t a = 0 oder b = 0 (in Worten." ein P r o d u k t ist nur dann null, wenn w e n i g s t e n s ein F a k t o r null ist). Die Nullteilerfreiheit impliziert die

1.0.1 Der Ring 7/der ganzen und der K6rper Q der rationalen Zahlen

15

Kiirzungsregel: Seien a, b, c ~ 7/.; es gelte ab = ac und a + O. Dann gilt. b = c. Beweis." Aus ab = ac folgt a (b - c) = 0. Wegen a 4= 0 m u g gelten b - c = 0, d. h. b=c.

Der Ring 77 1/il3t sich erweitern zum Bereich Q der rationalen Z a h l e n

{0,+1

_+2,+ 89

2 _

5,+4,+3

}

Jede rationale Zahl 7 gestattet (auf mannigfache Weise) eine Bruchdarstellung 7

a

b mit einem Zgihler a ~ 77 und einem N e n n e r b ~ 7Z, b 4= 0;

dabei gilt: Z w e i rationale Z a h l e n 7 = b' 7' = ~a' mit a , a ' , b , b ' e T Z , b + O, b'-~ O, sind genau dann gleich, wenn gilt ab' = a'b.

Statt ,, rationale Z a h l " sagen wir auch ,,Bruch". Wir bezeichnen im folgenden rationale Zahlen i.a. mit kleinen lateinischen Buchstaben und benutzen den griechischen Buchstaben 7 vorwiegend dann, wenn die Zahl in einer Bruchdara stellung 7 = ~ mit a, b e 77 gegeben wird. Die Additionsregeln und die Multiplikationsregeln ffir 77 gelten unver/indert for den Bereich Q ; fiberdies gilt ffir (I~ auch die

Divisionsregel: Z u j e d e m P a a r a, b ~ q) mit b ~ 0 gibt es genau ein x ~ ~ mit b x = a; man schreibt x = b

l a oder auch x - a b"

Beispiel." Ffir a = 2, b = ~s ist x - ~14.

Die Additionsregeln, Multiplikationsregeln und die Divisionsregel beschreiben ersch6pfend die Rechengesetze f/.ir die vier elementaren R e c h e n o p e r a t i o n e n der Addition, Subtraktion, Multiplikation und Division im Zahlensystem @. M a n faBt sie wie folgt zusammen: Die M e n g e ~ ist beziiglich der A d d i t i o n + und der Multiplikation 9 ein K6rper.

Wir werden im Ring 7/ und im K 6 r p e r Q u n b e k i i m m e r t und wie seit frfiher Jugend gewohnt rechnen. Wir schreiben durchweg ab + c d statt (ab) + (cd). Auch verwenden wit die gebr/iuchlichen Redeweisen wie S u m m e bzw. Differenz bzw. P r o d u k t bzw. Quotient ffir a + b bzw. a - b bzw. ab bzw. a b" Sind die rationalen Zahlen 71 = ~al, 72 = ~a2 in Bruchdarstellung vorgegeben, so sind 71 ~

72 --

a l b 2 + a2b I

,

7172

--

ala2

blb2 bib 2 Bruchdarstellungen ffir Summe, Differenz und P r o d u k t . Falls ba 7~ =I=0, so gilt a 14=0, und 71 1 al

ist eine Bruchdarstellung des ,,Inversen" von 7~ (Kehrwert).

16

Anordnung von 7/und Q

1.0.2

Sind a l , . . . , a, endlich viele Elemente aus Q, so sind (auf G r u n d der Assoziativgesetze) die endliche S u m m e a I + a 2 + ... + a, und das endliche P r o d u k t al a 2 ' . . . . a , in Q wohldefiniert. Wir v e r w e n d e n die b e k a n n t e Schreibweise

v:l

a v =

a 1 q-

...

-k a n,

|l v:l

av

ftir S u m m e und P r o d u k t . Falls al = a2 tl

H

a,, = aL wobei a ~

=

=

al

. . -

" ...

=

"an

a, = a , s o g i l t

I gesetzt wird.

~ a,.=naund "~'=1

"r

Wir erinnern an die

Summenformel der endlichen geometrischen Reihe: Fi~r alle x ~ ~ und alle nati~rlichen Z a h l e n n > 1 gilt:

(1 + x + x

2+--.+x"-l)(1-x)=l-x".

D e r Beweis ergibt sich durch Ausmultiplizieren der linken Seite.

[7~

Wir m a c h e n stillschweigend G e b r a u c h von den I n k l u s i o n e n N• cNcTZcQ. 2. Anordnung von 7/und Q. Die M e n g e 7Z,ist in natiirlicher Weise angeordnet:

...<-3<-2<-1<0<1<2<3---. M a n schreibt allgemein b < a und liest ,,b ist kleiner als a", wenn b e Z in dieser Zahlenreihe links von a e Z steht. (Das 1/iBt sich auch so ausdrticken: Es gilt b < a genau dann, wenn es eine nattirliche Z a h l n 4= 0 gibt, so d a b gilt: b + n = a.) Statt ,,b ist kleiner als a " sagt m a n auch ,,a ist gr6fler als b", m a n schreibt a > b anstelle von b < a. Wir werden vorwiegend mit der Relation > arbeiten. Die A n o r d n u n g von 7Z setzt sich zu einer A n o r d n u n g von Q fort: So ist z.B. 1 > i2 . Allgemein gilt Rir zwei Z a h l e n 7, ~ ) , wenn die Q genau d a n n 7 > ~'' Differenz 7 - 7' ein Bruch der F o r m ~ mit von 0 verschiedenen nati~rlichen Zahlen a, b ist. Wir stellen die fiir das Rechnen unerl~Blichen Eigenschaften der A n o r d nungsrelation > z u s a m m e n , verzichten aber auch hier bewuBt auf eine strenge Begriindung.

Anordnungsregeln: Seien a, b, c ~ Q . 1) Es gilt entweder a > b oder a = b oder b > a. 2) A u s a > b und b > c f o l g t a > c (Transitivitdit).

1.0.2

Anordnung von 7Z und Q

17

3) A u s a > b f o l g t a + c > b + c. 4) A u s a > O und b > O f o l g t a b > O. Als V e r a l l g e m e i n e r u n g v o n 4) gilt: 4') A u s a > b und c > O f o l g t a c > bc. B e w e i s v o n 4'): Aus a > b folgt a - b > 0 (nach 3) m i t c ' = - b). D a h e r gilt (a - b) c > 0 n a c h 4). Aus a c - b c > 0 folgt a c > b c (wieder n a c h 3)). [] Ein E l e m e n t a 9 t~ heil3t positiv bzw. negativ, w e n n gilt a > 0 bzw. 0 > a. M i t a ist a u c h a 1 positiv, d e n n aus - a - l > 0 wfirde n a c h 4) folgen: -1 =-a l a > 0 , w a s a b s u r d ist. W i c h t i g ist n o c h f o l g e n d e R e c h e n r e g e l : 5) A u s a > b und b > O f o l g t a l b u n d b > 0 gilt a > 0, also ab > 0 n a c h 4) u n d folglich aucha-lb l=(ab) l>0. Nach4,)folgtnun(mitc:=a-lb-1). a(a-lb-1)

> b(a-lb

1),

d.h. b 1 > a - 1

[]

N e b e n der R e l a t i o n ,,gr6fler" b e n u t z e n wir a u c h die R e l a t i o n ,,gr6J3er oder gleich". W i r s c h r e i b e n a > b, w e n n a > b o d e r a = b; e n t s p r e c h e n d a __< b, w e n n a 7, 8 < 8, 10101~ 2203 . Ffir die R e l a t i o n > gelten ebenfalls die A n o r d n u n g s r e g e l n 2 ) - 4 ) , 4'). Hfiufig w e r d e n wir a u c h den Betrag [a[ einer r a t i o n a l e n Z a h l a b e n u t z e n . M a n definiert: a_, [a['=

falls a > 0, a,

falls a < 0.

Es gelten die fiblichen B e t r a g s r e g e l n : Ffir alle a, b 9 ti) gilt: 1) [a[ > 0, [a[ = 0 - ~ a 2) [a b [ = [a [ 9[b [ 3) [a + b[ < [a[ + [b[

= 0. (Vroduktregel). (Dreiecksungleichung).

P r o d u k t r e g e l u n d D r e i e c k s u n g l e i c h u n g gelten a u c h in a l l g e m e i n e r e r F o r m : a~ =

v=l

[a~l,

< Z

V=I

[av[

ffir alle a l , a 2 , . . . , a , 9

~.

Nfitzlich fiir z a h l e n t h e o r e t i s c h e A n w e n d u n g e n ist folgende V a r i a n t e v o n 1): 1') Ffir a 9 7Z gilt a = 0 bereits dann, wenn l al < 1. Ffir endlich viele Z a h l e n a l , a 2 . . . . . a, 9 Q definiert m a n min(a 1,a2,...,a.)

bzw.

max(al,a2,...,a,)

Prinzip vom kleinsten Element und Induktionsprinzip

18

1.0.3

als d i e kleinste bzw. d i e grOJ3te d i e s e r Z a h l e n . D i e E x i s t e n z v o n m i n u n d m a x i s t a n s c h a u l i c h klax. W i r w e r d e n spfiter o h n e B e w e i s e i n f a c h e R e g e l n ftir d a s R e c h n e n m i t m i n u n d m a x b e n u t z e n ; z. B. g i l t stets: m i n ( t + r, t + s)

t + m i n ( r , s);

m i n ( r , s) + m a x ( r , s)

r + s.

M a n s c h r e i b t a l l g e m e i n e r m i n T bzw. m a x T ftir j e d e M e n g e T / ~ 0 r a t i o n a l e r Z a h len, w e n n T e i n k l e i n s t e s bzw. gr613tes E l e m e n t h a t (i. a. i s t d a s n i c h t d e r F a l l , e t w a fiir T Q !).

3. Prinzip vom kleinsten Element und Induktionsprinzip. In vielen Existenzbeweisen d e r Z m h l e n t h e o r i e w i r d e n t s c h e i d e n d b e n u t z t d a s Prinzip von kleinsten Element: Jede nicht leere Menge A yon nat~irlichen Zahlen enthdlt ein kleinstes Element ao m i n A . E b e n s o w i c h t i g w i e d a s P r i n z i p v o m k l e i n s t e n E l e m e n t ist d a s

Prinzip der vollst/indigen Induktion: Es sei B eine Menge nat~irlicher Zahlen, so dafi folgendes gilt." a) Es gibt wenigstens eine Zahl bo E B. b) Falls n E B, so gilt auch n + 1 E B.

(Induktionsanfang) (Induktionsschritt)

Dann enthdlt die Menge B bereits alle nat~irlichen Zahlen, die grOfier oder gleich bo sin& {x E IN: x > bo} C B. Das Prinzip vom kleinsten Element l~iBtsich einfach formulieren und sofort nachvollziehen; vom Induktionsprinzip l~iBtsich dies nicht ohne weiteres behaupten. Wir wollen uns plausibel machen, dab das Prinzip der vollst~indigen Induktion eine Konsequenz aus dem Prinzip vom kleinsten Element ist (wobei allerdings an entscheidender Stelle eingeht, dab ftir ao, bo E IN mitao > bo gilt ao - 1 __>bo). Man argumentiert wie folgt: Es sei irgendeine Menge B C IN mit den Eigenschaften a) und b) gegeben. Die Inklusion {x E IN : x __>bo} C B besteht genau dann, wenn die Menge

A:

{xEIN:x>=boundx~B}

leer ist. Wfire nun A nicht leer, so h~itte A als Teilmenge von IN ein kleinstes Element ao. Da bo~A aufGrundvona),sogiltao>bo undalson: ao-l_->bo. Wegennbo} C B. [] Es ist eine echte Uberraschung zu sehen, dab das Prinzip vom kleinsten Element keineswegs logisch einfacher als das Induktionsprinzip ist. Beide Prinzipien sind vielmehr logisch iiquivalent. Wir wollen noch kurz darlegen, wie man das Prinzip vom kleinsten Element aus dem Induktionsprinzip deduzieren kann: Es sei A C IN irgendeine nichtleere Menge. Wenn 0 E A gilt, so ist 0 ein kleinstes Element. Sei also 0 ~ A. Wir nennen b E IN eine (echte) untere Schranke von A, wenn far alle x E A gilt: x > b. Wir bezeichnen mit B die Menge aller echten unteren Schranken von A, nach Annahme gilt 0 E B. Wir ftihren nun die Annahme, dab A kein kleinstes Element hat, mit Hilfe der Menge B

1.0.3

Prinzip vom kleinsten Element und Induktionsprinzip

19

zum Widerspruch. Sei n ~ B, also x > n ffir alle x e A. Es folgt x > n + 1 ffir alle x ~ A. Es mug gelten n + 1 ~ A, denn sonst wiire n + 1 ein kleinstes Element von A. Aus n + I r A folgt x > n + I ffir alle x e A. Dies besagt, dag auch n + 1 eine echte untere Schranke von A ist, d.h. n + 1 e B. Damit hat B die Eigenschaft b). Wegen 0 ~ B folgt N c B. Dann mfiBte A aber leer gewesen sein, da es keine Zahl a ~ N gibt, die gr6ger als jede Zahl b E N ist. Widerspruch ! [] Als nfitzliche Anwendung des Induktionsprinzips beweisen wir den binomischen L e h r s a t z . F f i r alle v, n ~ N d e f i n i e r e n w i r d i e Fakultdten n! u n d d i e Binomial-

koeffizienten(n) wieiiblichdurchdieGleichungen n!:=l.2.3.....(n-1).ns]N

0!'=1, =

vi

•

r

ffir h e n

ffir v > l ,

• :=1.

Es gilt d a n n <:)=

1,(~):0

fiir v > n ,

v!(n - v)!

ffir v < n,

Die wichtige Identit/it

(*)

v-I

+

v

=

v

verifizieren wir durch Nachrechnen +

(~)

=

wie folgt:

.(.-1)....-(.-(v-l)+1) (v--~ n(n-1)....

=

nr

f/,ir v e N •

-~

+

. ( n - v + 2) [ 1)!

.(.-1).....(.-~+1) v! n - v + l]

1 +

=n(n--1)'""(n--v+2)'(n+l)v,

v =(n+l)v

"

Wir behaupten nun

Binomischer Lehrsatz: Fiir alle a, b ~ ~ und allen ~ N • gilt: + v=O

n--1

"

Beweis: Es sei B d i e M e n g e a l l e r nati.irlichen Z a h l e n n > 1, so d a b fi.ir alle a, b r Q d i e b e h a u p t e t e F o r m e l ffir (a + b)" r i c h t i g ist. Es gilt o f f e n s i c h t l i c h :

20

Prinzip vom kleinsten Element und Induktionsprinzip

1.0.3

1 e B. Sei n e B. U m n + 1 e B zu verifizieren, rechnen wir wie folgt" (a + b)"~ l = (a v=O

=a"+l+

~ V =

\~/

a ' + l - V b V + Y", 1

an-Vb v a" V b " + l + b " + l .

v=0

In der zweiten Summe r e c h t s / i n d e r n wir den Summationsindex: Y~ v=0

a"

Vbv+l

=

a "+1 ~"b'.

n

V-

v=l

1

D a n n erhalten wir unter Verwendung der Gleichung (*) ffir Binomialkoeffizienten:

,()

= a"~l+ Z

n+l

v=l

a,,+ 1 " b " + b,+ 1 = 52

1'

v=O

Y/+ 1 a "+l

*'bL

V

Damit sehen wir: n + i e B. Auf G r u n d des Induktionsprinzips folgt B = {n e N : n > 1 }, womit der binomische Lehrsatz bewiesen ist. Bemerkung: Die Zahlen ( n ) s i n d /

\

x

/

,. ,diesk,ar dadann(0

als Brfiche definiert. Es gilt aber:

0 Im a,,v

,ie tmand .ehaup.

unmittelbar aus der binomischen Formel ab, denn ( n ) miBt gerade die Anzahl, wie oft das P r o d u k t a~-~'b " als S u m m a n d beim Ausrechnen des ,,Binoms" (a + b)" v o r k o m m t . Wenn man anspruchsvoller argumentieren will, kann m a n h-~1 wieder das Induktionsprinzip heranziehen. Das induktionsprinzip wird in vielen Varianten benutzt. M a n kann es auch so aussprechen" Es sei E eine Eigenschqft, die auf natiirliche Zahlen zutreffen kann, d.h. .f~r jedes x c]N gilt entweder E(x) oder nicht E(x). Es sei folgendes richtig: a) Es gibt ein b o e N, so daft gilt E(bo). b) Fiir allen >=bo hat E(n) zur Folge: E(n + 1). Dann trifft die Eigenschaft E fiir alle x e N , x >=b o, zu.

(lnduktionsanjang) (I nduktionsschritO

1.0.4 Division mit Rest

21

In Anwendungen ist h~iufig der Induktionsschritt ,,von E(n) nach E ( n + 1)" nur dann durchftihrbax, wenn man nicht nur E ( n ) , sondern sogax die Gtiltigkeit aller Aussagen E(0), E(1) . . . . . E ( n - 1), E ( n ) benutzen daxf. Das ist nat0rlich vom anschaulichen Standpunkt aus gesehen klax, denn hat man E(n) induktiv sichergestellt, so hat man ja bereits in allen Schritten vorher E(1), E(2) . . . . . E ( n - 1) ebenfalls abgehandelt. Wir formulieren dieses erweiterte Induktionsprinzip der Vollst~indigkeit halber als

Prinzip der vollstfindigen Induktion mit erweiterter Induktionsvoraussetzung: Es sei E eine Eigenschaft, die auf natiirliche Zahlen zutreffen kann oder nicht, d. h. fiir jedes x E IN gilt entweder E(x) oder nicht E(x). Es sei folgendes richtig: a) Es gilt E (0). b) a u s E(O), E(1) . . . . . E(n) folgt E ( n + 1).

(Induktionsanfang) (Induktionsschritt)

Dann gilt E(x) fiir alle x E IN. 4. Division mit Rest. Als elementare Anwendung des Prinzips vom kleinsten Element beweisen wit die aus dem Schulunterricht wohlbekannte Division mit Rest, die beim Beweis grundlegender Resultate der Zahlentheorie in Z eine entscheidende Rolle spielt.

Division mit Rest: Es seien a, b E Z zwei Zahlen, es gelte b >= 1. Dann gibt es eindeutig bestimmte Zahlen q, r E Z zu a, b, so daJ3 gilt." a

qb+r

mit

O
Man nennt q den Quotienten und r den Rest bei der Division yon a dutch b; im Fall a > 0 gilt stets: q > O. Beweis." Existenz yon q und r." Die Menge A:

{x E iN" x

a-zbmitzEZ}CiN

istnichtleer:Fallsa>=O, s o g i l t a E A ; f a l l s a < O , sogilta-ab a(1-b) EA, da a < 0 und 1 - b =< 0 die Ungleichung a(1 - b) => 0 zur Folge hat. Nach dem Prinzip yore kleinsten Element besitzt A ein kleinstes Element r. Es gilt also r a-qb > 0 mit q E Z. Es gilt notwendig r < b, da sonst die Zahl a - (q + 1)b r - b ebenfalls nicht negativ, abet kleiner als r w~ire. Mithin ist a q b + r eine gesuchte Gleichung. Falls a => 0, so mul3 q => 0 gelten, denn q <= - l, d. h. - q >= l f~hrt zu r a - qb >=b. q b + r eine weitere Gleichung Eindeutigkeit yon q und r: Es sei neben a a q'b + r' gegeben, wobei q',r' E Z und 0 =< r' < b. Dann gilt r - r ' (q'-q)b,

also q ' - q

F -b

i.t

Wegen 0 _< r < b und 0 _< r' < b gilt --

r - - fl -b < r-r' < b, also - 1 < - < 1. Da q ' - q b q'-q O,d.h.q' qunddamitauchr' r.

--

E Z, ist also notwendig []

22

Teilbarkeitsbegriff 1.1.1

Beispiele: 1) a : = 531, b : = 93, 531 = 5 -93 + 66 mit q : = 5 und r : = 66 < 93. 2) a : = 617, b : = 758, 617 = 0 . 758 + 617 mit q : = 0 und r : = 617 < 758. 3) a : = - 5 , b:=2, -5=(-3).2+ 1 mitq:=-3 undr:= 1 <2.

w1

Teilbarkeit. Primzahlen

Im Ring 7 / d e r ganzen Zahlen sind Addition, Subtraktion und Multiplikation uneingeschrfinkt ausfiihrbare Rechenoperationen. Fiir die Division ist dies nicht mehr der Fall, da 7 / k e i n K 6 r p e r ist. Diese Tatsache ist verantwortlich dafiir, dab es in 7 / e i n e Zahlentheorie gibt: Die Frage, warm a e 7 / d u r c h d e 7/ teilbar ist, ist die Urfrage der Zahlentheorie. Der Hauptbegriff dieses P a r a g r a phen ist der Begriff der Primzahl; wit diskutieren ihn ausftihrlich und beweisen unter anderem den Satz von EUKLID fiber die Existenz unendlich vieler Primzahlen.

1. Teilbarkeitsbegriff. Eine Zahl d ~ Z heil3t ein Teiler der Zahl a ~ 7Z, in Zeichen d I a, wenn es eine Zahl v e 7/gibt, so dab gilt: a = dt'~. M a n sagt dann auch: d reilt a. Ist d kein Teiler von a, so schreibt man: d,~ a. Ist d :4= 0 ein Teiler yon a, so ist v e 7/, in der Gleichung a = dv auf G r u n d der Kiirzungsregel 0.1 eindeutig bestimmt.

Beispiele: 3f12, - 8 1 7 2 , (a-1)l(a"-l)

-111-99,4~/7,

ffir alle a, n s T l ,

n>l,

17[0,010, da a ' - I

=(a-l)(l+a+..-+a"-~).

Ist d ein Teiler von a, so nennt man d auch eine in a aujgehende Zahl und a ein Vielfaches yon d. Zur Einffihrung des Teilbarkeitsbegriffes ben6tigt m a n nur die multiplikative, nicht aber die additive Struktur von Z. Die Frage, ob d ein Teiler von a ist, kann aber unter Benutzung der S u b t r a k t i o n auch so formuliert werden: M a n entscheide, ob die lineare Gleichung dx - a = 0 eine L6sung in Z hat. Bei dieser Auffassung ist die Teilbarkeitstheorie in 7Z, nichts anderes als die Theorie einer linearen Gleichung in einer Unbestimmten i~ber Z. Der Teilbarkeitsbegriff k o m m t bereits im Talmud vor: M a n finder dort die Behauptung, dab eine Zahl der F o r m 100a + b sicher dann durch 7 teilbar ist, wenn 7 die Zahl 2a + b teilt. (Geben Sie hierffir einen Beweis!) Im t/iglichen Leben benutzt m a n den Teilbarkeitsbegriff, wenn man von geraden bzw. ungeraden Zahlen spricht: Eine Zahl a e 7/ heil3t gerade bzw. ungerade, wenn gilt: 21a bzw. 2 X a , d.h. wenn a v o n der F o r m 2v bzw. 2v + 1 mit t;~7/ ist. Fiir die Teilbarkeit gelten folgende grundlegende

I.l.l

23

Teilbarkeitsbegriff

Rechenregeln: Seien a, b, c, d ~ 7/. Dann gilt: 1) 2) 3) 4)

ala. A u s a lb und b ] c f o l g t A u s a lb und c ld f o l g t Aus a ] b und a ] c f o l g t

Beweis: ad 1): K l a r ad 2): Aus b ad 3): Aus b ad 4): Aus b

wegen a = = av~ u n d = av I u n d = av 1 u n d

a c d c

(Reflexivitdt) a ] c. ( Transitivitdt) ac[bd. a ] (x b + y c) fiir alle x, y ~ 7/.

9 1. = b y 2 folgt = cv3 folgt = at; 4 folgt

c = a ( v , v2).

b d = a c ( v l U3). x b + y c = a ( x v 1 + yv4) fiir alle x, y e 2g.

[]

M a n b e a c h t e , d a b d u r c h die R e c h e n r e g e l 4) eine V e r b i n d u n g z w i s c h e n T e i l b a r keit u n d A d d i t i o n hergestellt wird. Weiter m a c h e m a n sich klar, d a b die R e c h e n regel 3) nicht gilt, w e n n m a n a + c bzw. b + d statt ac bzw. b d schreibt. Die Z a h l 0 wird v o n j e d e r Z a h l d e 7/ geteilt, d a 0 = d 9 0. D a s ist a b e r a u c h bereits der einzige Fall einer Z a h l m i t u n e n d l i c h vielen v e r s c h i e d e n e n Teilern; dies ergibt sich aus f o l g e n d e r Aussage, die einen w i c h t i g e n Z u s a m m e n h a n g z w i s c h e n der T e i l b a r k e i t s r e l a t i o n ] u n d der A n o r d n u n g s r e l a t i o n herstellt. Satz: Sei a ~ 77, a 4: 0; sei d c 7 / e i n Teiler von a. Dann gilt:

I NldlNlal. Insbesondere hat eine Z a h l a 4 : 0 h6chstens endlich viele verschiedene Teiler. Beweis: Es gilt a = dv m i t v ~ 7/. H i e r a u s folgt la] = [d] Iv]. W e g e n a 4 : 0 gilt d 4= 0 u n d v 4= 0. Ersteres b e d e u t e t ]d[ _>_ 1, letzteres h a t Iv[ > 1 u n d also La] = ]dl Ivl > Id] zur Folge. D a m i t ist bereits gezeigt, d a b gilt: 1 < Id] < ]a]. D a es h 6 c h s t e n s 2 l a] v e r s c h i e d e n e Z a h l e n d e Z m i t 1 < ]d] < l a[ gibt, h a t a h 6 c h stens 2 l a [ v e r s c h i e d e n e Teiler. ~]

W i r w e r d e n im A b s c h n i t t 3.1 eine explizite F o r m e l fiir die A n z a h l aller Teiler v o n a kennenlernen. K o r o l l a r : Seien a, d ~ 7Z. A u s d > 0, a > O, d l a und a ] d j o l g t d = a. Beweis: Aus d e m Satz folgt d < a u n d a < d, also a = d.

[]

Die R e c h e n r e g e l 1) ist sofort e r w e i t e r b a r : J e d e g a n z e Z a h l a h a t die vier (i.a. v e r s c h i e d e n e n ) Teiler a, -- a, 1, -- 1. Diese n e n n t m a n die trivialen Teiler yon a. Alle iibrigen Teiler v o n a h e i g e n echte Teiler yon a. Aus d e m o b i g e n Satz folgt: Ist d ein echter Teiler yon a 4= O, so gilt 1 < Idl < lal.

24

Primzahlen

1.1.2

Die Z a h l e n a u n d - a h a b e n dieselben Teiler, d e n n es gilt a = dv g e n a u d a n n , w e n n gilt: - a - d ( - v). D a stets a o d e r - a eine nattirliche Z a h l ist, so ist es also keine E i n s c h r / i n k u n g , w e n n wit T e i l b a r k e i t s u n t e r s u c h u n g e n v o r w i e g e n d fiir nat/,irliche Z a h l e n durchffihren. D a mit d a u c h stets - d ein Teiler v o n a ist (denn a = d v mit v e 7Z,k a n n a u c h in der F o r m a = ( - d) ( - v) geschrieben werden), so k e n n t m a n bereits alle Teiler der ganzen Zahl a, w e n n m a n alle positiven Teiler der natiirlichen Zahllal kennt. Aus diesem G r u n d e beschrfinkt m a n viele Bet r a c h t u n g e n in der Z a h l e n t h e o r i e hfiufig a u f d i e M e n g e N • der positiven g a n z e n Zahlen.

2. P r i m z a h l e n . Eine erste A u f g a b e der Z a h l e n t h e o r i e besteht darin, eine g e g e b e n e natiirliche Z a h l a > 1 als ein P r o d u k t v o n m 6 g l i c h s t vielen F a k t o r e n , die alle gr613er als 1 u n d kleiner als a selbst sind, zu schreiben. So gilt z.B.: /188=9.11.12, 3315=3-5.13.17, 512=29=2.2.2.2.2.2.2.2.2. D e r Vorteil solcher Faktorisierungen ffir p r a k t i s c h e R e c h n u n g e n liegt a u f der H a n d : Mit kleinen Z a h l e n r e c h n e t es sich b e q u e m e r als mit grol3en Z a h l e n ! N u n st613t m a n i m m e r wieder a u f Z a h l e n , z. B. 8 8 3 , 9 9 7 . . . . . 9587 . . . . . 2 9 9 4 7 9 , . . . , 1 0 0 0 0 0 7 9 , . . . , die sich allen F a k t o r i s i e r u n g s v e r s u c h e n widersetzen: Sie lassen sich nicht als P r o d u k t kleinerer Z a h l e n darstellen. Diese , , u n z e r l e g b a r e n " Z a h l e n w e r d e n d u r c h eine Definition h e r v o r g e h o b e n : Eine natiirliche Z a h l p heil3t Primzahl, w e n n gilt: a) p > l . b) Ist p = ab mit a, b e N eine P r o d u k t d a r s t e l l u n g v o n p, so gilt a = 1 o d e r b = 1. Die M e n g e aller P r i m z a h l e n wird mit IP bezeichnet. Gem/il3 dieser Definition ist die Z a h l 1 keine P r i m z a h l : 1 ~ IP. Die ersten P r i m zahlen sind: 2, 3, 5, 7, 11 . . . . . Der Begriff der P r i m z a h l 1/if3t sich a u c h n o c h a n d e r s fassen. L e m m a : Folgende Aussagen i~ber eine natiirliche Zahl p > 1 sind dquivalent: i) ii) iii)

peIP. 1 und p sind die einzigen positiven Teiler yon p.

p hat keine echten Teiler.

Beweis: i ) ~ ii}: G/ibe es einen Teiler a v o n p mit 1 < a < p, so wtirde eine G l e i c h u n g p = ab mit b e ]N gelten, w o w e d e r a = 1 n o c h b = 1 gilt. ii) ~ iii): W/ire d ein echter Teiler v o n p, so a u c h Idq, im W i d e r s p r u c h zu ii). iii) ~ i): Sei p = ah mit a, b e N . N a c h V o r a u s s e t z u n g h a t p n u t triviale Teiler, d.h. es gilt e n t w e d e r a = 1 o d e r a = p u n d d a n n b = 1. !

1.1.3

Existenz unendlich vieler Primzahlen

25

Aufgrund der Eigenschaft iii) nennt man Primzahlen hfiufig auch unzerlegbar. Wir haben die Existenz von Primzmhlen durch Probieren sichergestellt. Ohne Probieren ergibt sich das Vorhandensein von Primzmhlen aus folgendem

Existenzsatz: Jede natiirliche Zahl a > 1 besitzt einen kleinsten (positiven) Teiler t > 1; dieser Teiler t ist eine Primzahl. Beweis: Die Menge T a l l e r positiven Teiler /~ 1 von a ist nicht leer, da a E T. Nach dem Prinzip vom kleinsten Element enthfilt T ein kleinstes Element t. Diese Zmhl ist der kleinste positive Teiler > 1 von a. WSxe t nicht Primzahl, so gfibe es einen Teiler t / v o n t mit 1 < t / < t. Aus t~l t und t la folgt wegen der Transitivitfit der Teilbaxkeit, dag t ~ ein Teiler von a wSxe. Wegen t ~ > 1 wfirde t ~ also zur Menge T geh6ren. Wegen t' < t ist das ein Widerspruch zur minimalen Wahl von t.

3. Existenz unendlich vieler Primzahlen. Durch den Existenzsatz 2 wird fiber die Anzmhl aller Primzmhlen noch nichts gesagt. Es wfire denkbax, dab es nur endlich viele Primzahlen giN. Aus der Unendlichkeit yon IN allein kann man nicht die Unendlichkeit der Menge P deduzieren: Auch mit endlich vielen Primzmhlen (sogax schon mit einer einzigen) lassen sich unendlich viele natfirliche Zahlen gewinnen, z. B. 2, 4, 8, 16 . . . . . 512, 1024 . . . . . 2" . . . . . In den Elementen yon EUKLID (Buch IX, Satz 20) * findet sich bereits der Satz yon EUKLID: Es gibt unendlich viele Primzahlen. Im Text von EUKLID k o m m t das Wort ,,unendlich" nicht vor; er formuliert seinen Satz wie folgt: Die Primzahlen sind mehr als jede vorgegebene Menge yon Primzahlen. Wie oft in der Mathematik werden wir mehr beweisen als behauptet wird. Der Beweis y o n E U K L I D , den wir wiedergeben, liefert n~imlich ein Verfahren, immer neue Primzahlen zu konstruieren. Wir werden zeigen:

Satz: Es seien ql, q 2 , . . . , qn endlich viele Primzahlen (die irgendwie vorgegeben sind). Dann ist der kleinste (positive) Teiler t > 1 der natiirlichen Zahl a:

ql q2 " . . . " qn + l

eine Primzahl, die yon allen Primzahlen ql, q 2 , . . . , q~ verschieden ist. Es ist Max, dag der Satz von EUKLID in dieser Aussage als Spezialfall enthalten ist. Die Elemente bestehen aus 13 Btichern und entstanden um 300 vor Christi Geburt; sie bilden die grol3e Enzyklopfidie der griechischen Mathematik und sind neben der Bibel das am hfiufigsten verlegte Werk der Weltliteratur.

26

Unzerlegbarkeit und Primeigenschaft

1.1.4

Beweis des Satzes: D a a > 1, existiert t, u n d z w a r ist t eine P r i m z a h l ( E x i s t e n z s a t z 2). W f i r d e t m i t e i n e r der Z a h l e n q~, q2 . . . . . q, f i b e r e i n s t i m m e n , so w/ire t e i n Teiler des P r o d u k t e s q i q 2 "... " G . A u s t t a u n d t ] ( q l q 2 . . . . . q,) u n d 1 = a - ql q2 " .-. ' qn folgt t I I aus der R e c h e n r e g e l 1,4). D a I n u t die Teiler 1 u n d - 1 hat, w/ire t = I im W i d e r s p r u c h zu t > 1. Bemerkung: Es ist interessant, die euklidische Konstruktion sukzessiv durchzufiihren. Ausgehend von n = I und der kleinsten Primzahl q~ : = 2 erhiilt man im ersten Schritt a = 2 + 1 = 3 und damit fiir t die zweitkleinste Primzahl q2:= 3. Im zweiten Schriu gewinnt man a - 2 93 + I - 7 und damit ftir t nicht die drittkleinste Primzahl 5, sondern q3 : - 7. Im dritten Schritt entsteht a - 2 93 97 + 1 = 43 mit q4:= 43. So fortfahrend gewinnt man eine Folge von Primzahlen q,, die aber nicht monoton wachsend ist, da die auftretenden Zahlen a nicht immer, wie in den ersten Schritten, selbst Primzahlen sind. So ist bereits im vierten Schritt a = 2 93 ' 7 9 43 + 1 = 1807 - 13 - 139 keine Primzahl; als kleinster Primteiler t ergibt sich q s : = 13. also qs
4. U n z e r l e g b a r k e i t und Primeigenschaft. Als e l e m e n t a r e , a b e r weitreic h e n d e K o n s e q u e n z der D i v i s i o n m i t Rest zeigen wir das f o l g e n d e Fundamentallemma: Teih eine Primzahl p ein P r o d u k t ab yon zwei positiven natiirlichen Z a h l e n a und b, so teilt p einen der Faktoren.

• " p ] a x } e n t h / i l t p u n d b u n d also n a c h d e m P r i n z i p v o m k l e i n s t e n E l e m e n t eine k l e i n s t e Z a h l c e N • B e w e i s e n t s c h e i d e n d ist f o l g e n d e B e h a u p t u n g : e l y ffir j e d e s 3' ~ E. N a c h d e m Satz v o n d e r D i v i s i o n mit Rest 0.4 gilt eine G l e i c h u n g y = qc + r m i t q, r e N , 0 < r < c. A u s p l a y , p t a c u n d ar = a y - q(ac) folgt p lar. W/ire r > 0, so 1/ige r in E, was w e g e n der M i n i m a l i t / i t y o n c u n d r < c n i c h t geht. Es folgt r = 0, d.h. c ly. Setzen wir y : = p, so folgt c [p. W e g e n L e m m a 2 s i n d d a h e r n u t zwei F/ille m 6 g l i c h : c = 1 o d e r c = p. I m F a l l e c = 1 gilt p la w e g e n p [ac. I m F a l l e c = p folgt p lb w e g e n

Beweis: Die M e n g e E : = { x e N

beE.

1.1.4

Unzerlegbarkeit und Primeigenschaft

27

Bemerkung: Der obige Beweis kann begrifflich durchsichtiger gestaltet werden: Man betrachtet E ' : = {x E 71:Pl ax} anstelle von E und bemerkt zun/ichst, dab E' ein Ideal in 71 ist (zur Definition vergleiche man 2.1.3). Die Schlugweise mit der Division mit Rest liefert dann, dab E' ein Hauptideal mit c als erzeugendem Element ist (vgl. auch den Hauptsatz fiber Ideale in 71 2.1.3). Ein direktes Argument ffihrt dann auf die beiden F/ille c = I bzw. c = p. M a n beachte, d a b die A u s s a g e des F u n d a m e n t a l l e m m a s rein m u l t i p l i k a t i v ist, w / i h r e n d in seinen Beweis a u c h die a d d i t i v e S t u k t u r y o n N eingeht, u n d z w a r in e n t s c h e i d e n d e r Weise (vgl. hierzu die B e m e r k u n g in 2.2). Eine u n m i t t e l b a r e V e r a l l g e m e i n e r u n g ist das f o l g e n d e K o r o i l a r : Teilt eine Primzahl p ein P r o d u k t a~ 9 ... 9 a, aus n positiven natiJrlichen Z a h l e n a 1 . . . . . a,, so teilt p einen der Faktoren. Beweis (durch l n d u k t i o n nach n): Die F/ille n = 0 u n d n = 1 sind trivial. Sei die B e h a u p t u n g richtig ffir P r o d u k t e v o n n - 1 positiven natfirlichen Z a h l e n . Teilt d a n n p das P r o d u k t al - ... 9 a, 1 " a, = (a I 9 ... 9 a , _ 1) 9 a, der n positiven natiirlichen Z a h l e n a~ . . . . . a,, so folgt aus d e m F u n d a m e n t a l l e m m a , dal3 a I 9 ... 9 a , _ 1 o d e r a, v o n p geteilt wird. I m ersten Fall erh/ilt m a n aus der I n d u k t i o n s v o r a u s setzung, d a b p eine der Z a h l e n al . . . . . a , _ 1 teilt, so d a b stets einer der F a k t o r e n a l . . . . . a, v o n p geteilt wird. [] D a s F u n d a m e n t a l l e m m a e r m 6 g l i c h t eine neue u n d wichtige C h a r a k t e r i s i e r u n g der P r i m z a h l e n , die nicht m e h r a u f der , , U n z e r l e g b a r k e i t s e i g e n s c h a f t " dieser Z a h l e n basiert u n d die im f o l g e n d e n eine wichtige Rolle spielen wird. S a t z : F o l g e n d e A u s s a g e n iiber eine natiirliche Z a h l p > 1 sind dquivalent: i) ii)

p ist eine Primzahl. A u s p l(ab), a, b ~ 27, f o l g t p la oder p lb.

Beweis: i) ~ ii): Falls a = 0 o d e r b = 0, so ist nichts zu zeigen. S o n s t k a n n m a n d u r c h f,)bergang z u m N e g a t i v e n o h n e E i n s c h r / i n k u n g a u n d b als positiv a n n e h m e n u n d hat somit die V o r a u s s e t z u n g e n des F u n d a m e n t a l l e m m a s erffillt. ii) ~ i): W i t zeigen, d a b A u s s a g e ii) v o n L e m m a 2 zutrifft. Sei also d irgendein positiver Teiler y o n p. D a n n gilt eine G l e i c h u n g p = d d ' mit d ' e N . Dies b e d e u tet p l d d ' . N a c h V o r a u s s e t z u n g folgt p l d o d e r p l d ' . D a 1 < d < p und 1 < d ' < p, so folgt d = p o d e r d ' = p, d.h. d = p o d e r d = 1. M i t h i n hat p n u r die positiven Teiler 1 u n d p, ist also eine P r i m z a h l . [] Die E i g e n s c h a f t ii) des Satzes n e n n t m a n (im U n t e r s c h i e d z u r U n z e r l e g b a r k e i t s eigenschaft) Primeigenschaft. W i r k 6 n n e n den Satz also so f o r m u l i e r e n : Eine natiirliche Z a h l p > 1 ist genau dann unzerlegbar, wenn sie die Primeigenschafi besitzt. Wir werden diese beiden Eigenschaften in Kapitel 3 ffir Elemente beliebiger Ringe noch ausffihrlich studieren; im Vorgriff sei hier bereits angemerkt, dab sich dabei die Primeigenschaft als eine im allgemeinen echt st/irkere Bedingung als die Unzerlegbarkeitseigenschaft herausstellt.

28

Der Hauptsatz der elementaren Zahlentheorie

1.2

Aufgaben: 1) Seien a,b,c Ziffern aus der M e n g e {0, 1 , 2 , . . . ,9} und a r 0. Zeigen Sie: 13 teilt die nattirliche Zahl

abcabc

(Zifferndarstellung).

2) Sei n e i n e nattirliche Zahl, n > 1. Beweisen Sie: Aus n I((n - 1 ) ! + 1) folgt n E P . 3) Sei p~, die n-te Primzahl, d.h. Pl

2, P2

3 usw. Zeigen Sie: p~, __<2 (2' 1) ftir alle

n_>l.

4) SeipeinePrimzahl. BeweisenSie:pisteinTeilervon(P)

f~rl<-v<-p-l.

5) Seien p E P , n E IN • und a,b E Z. Zeigen Sie dutch Induktion nach n: p ist ein Teiler von

( (a + b) '/' - (d/' + b'/') ).

6) Sei n > 2 eine nattMiche Zahl. Zeigen Sie: n 4 + 4 ~' ist keine Primzahl.

w2

Der Hauptsatz der elementaren Zahlentheorie

Wir beweisen in diesem Paragraphen den Hauptsatz der elementaxen Zahlentheorie. Dazu pr~izisieren wit zun~ichst die dutch Probieren gewonnene Einsicht, daB man jede nattirliche Zahl so lange in Faktoren zerlegen kann, bis man bei lauter unzerlegbaren Faktoren, bei ,,Primfaktoren", angelangt ist. Der Weg, auf dem man solche ,,Primzerlegungen" herstellt, ist nicht kanonisch, so kann man z. B. ftir die Zmhl 60 wie folgt vorgehen 60

6.10

2.3.2.5

oder

60

4.15

2.2.3.5.

In beiden Fallen ergeben sich bis auf die (willktirliche) Reihenfolge der Primfaktoren dieselben Zerlegungen. Wit sind v o n d e r Schule her gewohnt, dies als etwas ganz Selbstverst~indliches zu betrachten: B u m multiplikativen Abbau einer Zahl ergeben sich am SchluB als letzte Bausteine stets dieselben Primfaktoren. Es ist Max, dab diese Eindeutigkeit der Primzerlegung bewiesen werden muB. Bei gr6Beren Zmhlen verschwindet auch bald das Geftihl der Sicherheit: Hat man etwa 30031 glticklich in die beiden Primfaktoren 59.509 zerlegt, so kann man die bohrende Frage eines Skeptikers, ob es nicht doch noch andere Primzahlen auBer 59 und 509 giN, die in 30031 aufgehen, nut mit einem vagen ,,es muB so s u n " beantworten. Es ist eine wundersame Ftigung, dab die griechischen Mathematiker die Notwendigkeit versptirt haben, die in Rede stehende Eindeutigkeit der Primzerlegung nachzuweisen. Bereits EUKLID bewies urn 300 v. Chr. korrekt die notwendigen Schritte! Unser Beweis der Eindeutigkeit in Abschnitt 2 basiert auf dem Korollax zum Fundamentallemma 1.4, also letztlich auf der Division mit Rest. Daneben ftihren wit in Abschnitt 3 eine von Ernst ZERMELO herrtihrende kunstvolle, indirekte SchluBweise an, die nut ganz einfache Eigenschaften der nattirlichen Zahlen heranzieht. Im Kapitel 3 werden wit einen weiteren, mehr begrifflichen Beweis geben, der auch ftir allgemeinere Ringe als Z funktioniert.

1.2.1 Existenz einer Primzerlegung

29

1. Existenz einer Primzerlegung. Ist a > 1 eine natfirliche Zahl, so heil3t jede P r i m z a h l p, die a teilt, ein P r i m t e i l e r o d e r auch ein P r i m f a k t o r yon a. Jede Darstellung a = P i P 2 9 ... " P ,

von a als P r o d u k t v o n endlich vielen P r i m z a h l e n P l, P2, .-., P,, heiBt eine P r i m z e r l e g u n g yon a (genauer w~re: P r i m f a k t o r z e r l e g u n g

yon a).

Es erweist sich als zweckm~il3ig, auch P r o d u k t e mit null F a k t o r e n zuzulassen (leere Produkte). D a z u treffen wit folgende formale K o n v e n t i o n : Ein P r o d u k t P x P 2 " . . . "Pn aus n F a k t o r e n hat im Spezialfall n = 0

den Weft 1. Diese K o n v e n t i o n ist in Analogie zur V e r a b r e d u n g bei S u m m e n zu sehen, wo m a n unter einer S u m m e cl + ... + c, von n S u m m a n d e n im Spezialfall n = 0 fiblicherweise den Wert 0 versteht (leere Summe). Gem/ii3 unserer K o n v e n t i o n besitzt auch die Z a h l 1 eine P r i m z e r l e g u n g mit 0 P r i m f a k t o r e n . Wir zeigen nun die

Existenz einer Primzerlegung:

J e d e natiirliche Z a h l a >= 1 b e s i t z t eine P r i m z e r l e -

gung a = PlP2 " ... "P,. D a b e i k a n n m a n f f i r P l s p e z i e l l den k l e i n s t e n P r i m t e i l e r t yon a wdhlen.

Wir schlieBen induktiv. Ffir a : = 1 trifft die B e h a u p t u n g zu (leeres Produkt). Sei a > 1, und sei vorausgesetzt, d a b die B e h a u p t u n g fiir alle natfirlichen Zahlen a' mit 1 = a' < a richtig ist. N a c h Satz 1.2 besitzt a einen kleinsten Primteiler t. Es besteht d a n n eine G l e i c h u n g Beweis:

a=tb

mit

1
(wegen I < t < a ) .

N a c h I n d u k t i o n s v o r a u s s e t z u n g hat b eine P r i m z e r l e g u n g b = P2 9 ... "P,Setzt m a n p l " = t, so ergibt sich ffir a folgende P r i m z e r l e g u n g a =plp2.....p~.

2. Eindeutigkeit der Primzerlegung. D i e P r i m z e r l e g u n g einer j e d e n natiirlic h e n Z a h l a >= 1 ist bis a u f die R e i h e n f o l g e der P r i m f a k t o r e n eindeutig. G e n a u e r : S i n d a = P l " . . . " P , und a = ql " . . . " qm z w e i P r i m z e r l e g u n g e n yon a m i t P r i m z a h len P l , . . . , Pn, ql . . . . , q,,, so gilt m = n, und m a n k a n n die P r i m z a h l e n der z w e i t e n Z e r l e g u n g so (urn)numerieren, daft gilt: P l = ql . . . . . P, = q,. B e w e i s : Wir ffihren I n d u k t i o n nach n. Ffir n = 0 ist a = 1 und d a m i t notwendigerweise auch m = 0. Sei die B e h a u p t u n g nun ffir alle positiven natfirlichen

30

Eindeutigkeit der Primzerlegung

1.2.2

Zahlen bewiesen, die eine P r i m z e r l e g u n g mit n - 1 P r i m f a k t o r e n zulassen, wobei n > 1. Sind d a n n a = Pl ' -.. "P, und a = q~ . . . . . qm zwei P r i m z e r l e g u n g e n von a, so besagt die G l e i c h u n g P l 9 . . . " P , = q l " . . . 9 qm speziell Pl J q~ " ... ' qm" Mit dem K o r o l l a r zum F u n d a m e n t a l l e m m a 1.4 folgt d a r a u s P l l q j for einen Index j, 1 < j < m, wobei m a n nach U m n u m e r i e r e n von q~ . . . . . q,~ ohne Einschrfinkung j = i a n n e h m e n kann. D a ql eine P r i m z a h l ist, ergibt sich nun t)~ = q~ aus L e m m a 1.2 wegen p l > 1. Aufgrund der K 0 r z u n g s r e g e l 0.i besitzt die Zahl a' : = P 2 " . . - ' P , also die beiden P r i m z e r l e g u n g e n P 2 ' . . . " P , und q 2 " . . . " q , , , wobei erstere aus n 1 P r i m f a k t o r e n besteht. N a c h der I n d u k t i o n s v o r a u s s e t z u n g folgt d a n n n - 1 = m - 1 und, nach geeignetem U m n u m e rieren, P2 = q2 . . . . . Pn = q,' Somit ist die Eindeutigkeit der Primzerlegung bewiesen.

B e m e r k u n g : Der soeben gef6hrte Eindeutigkeitsbeweis benutzt versteckt (beim Verwenden der Division mit Rest im Beweis des F u n d a m e n t a l l e m m a s t.4), a b e t entscheidend die additive S t r u k t u r yon N . I m Beweis der Existenz einer P r i m zerlegung wird die additive S t r u k t u r von N nicht herangezogen. D a Primzerlegungen n u t die multiplikative S t r u k t u r von N betreffen, wird m a n fragen, ob auch ein Eindeutigkeitsbeweis m6glich ist, der n u t die multiplikative S t r u k t u r verwendet. Die Antwort ist n e i n . Wit geben dazu ein ebenso einfaches wie eindrucksvolles Beispiel, welches zugleich iiberzeugend darlegt, d a b der G l a u b e an die logische Selbstverstfindlichkeit der Eindeutigkeit der Primzerlegung ein I r r g l a u b e ist. Wir betrachten die Menge D aller nat6rlichen Zahlen, die , b e i Division d u t c h 3 den Rest I h a b e n " , d.h. D : = {3k + 1 : k e N } . Wir b e m e r k e n als erstes: D ist m u l t i p l i k a t i v a b g e s c h l o s s e n , d. h. mit endlich vielen Elementen a 1 . . . . . a, e D liegt auch a t 9 ... 9a,, in D. Dies ist klar ftir n = 0 und n = 1. F i i r n = 2 ist dies richtig, da stets gilt: (3k~ + 1)(3k 2 + 1) = 3 ( 3 k l k 2 + k 1 q- k2) q- 1; fiir beliebige n > 2 folgt die B e h a u p t u n g nun induktiv. Wie in ~ nennen wir in D eine Z a h l c c D u n z e r l e g b a r (wir vermeiden aber das Wort ,,Primzahl"), wenn c > 1 und wenn aus c = a b mit a, b e D folgt: a = 1 oder b = 1. Die ersten unzerlegbaren Zahlen aus D sind 4, 7, 10, 13, 19,22, 25, 31; wegen 16 = 4 . 4 und 28 = 4 . 7 sind 16 und 28 nicht unzerlegbar. M a n zeigt leicht durch I n d u k t i o n (analog wie im Beweis der Existenz einer Primzerlegung): J e d e Z a h l a 9 D ist a l s e n d l i c h e s P r o d u k t a = c 1 9 . . . 9G yon in D unzerlegbaren

Zahlen

c l , . . . , c. 9 D

darsrellbar.

Die vielleicht erwartete Eindeutigkeit der D a r s t e l l u n g gilt aber nicht mehr; so hat die Zahl 100 9 D die beiden Zerlegungen 100 = 4 9 25 und 100 = 10 - 10 in unzerlegbare F a k t o r e n , die sich nicht nur in der Reihenfolge der F a k t o ren v o n e i n a n d e r unterscheiden! Definiert m a n in D Teilbarkeit und Primeigenschaft a n a l o g wie in 27, so gilt in D, d a b 4110- 10, aber 4 X 1 0 , d.h., die in D unzerlegbare Zahl 4 besitzt nicht die Primeigenschaft (vergleiche hierzu auch Kapitel 3).

!.2.2 Eindeutigkeit der Primzerlegung

31

Man sieht an diesem Beispiel, dab in jedem Beweis der Eindeutigkeit der Primzerlegung notwendig fiber die multiplikative Struktur von N hinausgehende Eigenschaften der natfirlichen Zahlen herangezogen werden mfissen, die die Menge D nicht besitzt, wie etwa die additive Abgeschlossenheit von N, die ffir D nicht richtig ist: 4 ~ D, aber 8 = 4 + 4 ~ D, oder allgemeiner: Mit 3ba + I ~ D und 3b2 + 1 ~ D gilt stets: (3b I + 1) + (3b 2 + 1) = 3(b 1 + b2) + 2 ~ D. Die Primfaktoren in der Primzerlegung einer natfirlichen Zahl sind i.a. nicht paarweise voneinander verschieden. Wir treffen folgende

Vereinbarung: 1) Gleiche P r i m f a k t o r e n p,. in einer P r i m z e r l e g u n g a = P l P 2 " . . . "P, werden zu P o t e n z e n p~v zusammengefaflt (dabei miflt m v die VielJachheit des Vorkommens von p~ als F a k t o r in der Primzerlegung). 2) Die ReihenJolge der P r i m z a h l p o t e n z f a k t o r e n pray in einer P r i m z e r l e g u n g yon a wird gemd/3 der natiirlichen A n o r d n u n g 2 < 3 < 5 < 7 < 11 < ... der P r i m z a h l e n normiert (also Pl < P2 < ...). Korollar: J e d e natfirliche Z a h l a :# 0 besitzt genau eine P r i m z e r l e g u n g ml

m2

a = p l P2 " . . . " P7~ mit P r i m z a h l e n p~ < P2 < ... < P~ und E x p o n e n t e n ml > 1. . . . . m r > 1. Beweis. Klar auf Grund der vorangegangenen S/itze und der soeben getroffenen

Vereinbarung. Wir haben in der Formulierung des Korollars bewul3t die Primzahlen von 1 bis r u n d nicht mehr von 1 bis n numeriert, da die Zahl n der Faktoren aus dem Existenzsatz bei Faktorenzusammenfassung i.a. verkleinert wird. ~.311,531 = 3 2 . 5 9 1 , 1 0 0 0 = 2 3 . 5 3 .

Beispiele:372=22.3

Es lassen sich nun sofort alle ganzen Zahlen in die Betrachtungen einbeziehen im

Hauptsatz der elementaren Zahlentheorie: J e d e g a n z e Z a h l a ~ 0 besitzt genau eine Darstellung a = e,p lml P2m2

.

. . . . pmrr = e -f i- p o ~ Q=I

m i t e = +_ 1, P r i m z a h l e n P l < P2 < ... < Pr und E x p o n e n t e n m~ > 1 . . . . . m r > 1. Beweis: Klar auf Grund des Korollars, da ffir jede negative ganze Zahl a + 0 gilt:

a=(--1).(--a)mit

-a~N.

D

Es sei wiederholt, dal3 auch der Fall r -- 0 des leeren Produktes 1 zugelassen ist, also a = _+ 1. Man nennt die durch den Hauptsatz gegebene Zerlegung von a die kanonische P r i m z e r l e g u n g yon a.

32

Kritische Bemerkungen

1.2.4

3*. Der Eindeutigkeitsbeweis von ZERMELO. Wir geben eine auf Ernst ZERMELO ( / 8 7 1 - 1953) zurOckgehende Beweisversion ffir die Eindeutigkeit der Primzerlegung an, die nur die Rechen- und A n o r d n u n g s r e g e l n ffir natOrliche Zahlen und das Prinzip der vollstfindigen I n d u k t i o n verwendet, nicht abet die Division mit Rest: In der Situation des Eindeutigkeitssatzes von Abschnitt 2 f0hren wit diesmal I n d u k t i o n nach a. Ffir a = 1 ist die B e h a u p t u n g richtig (leere P r o d u k t e mit re=n=0). Sei a > 1 und die B e h a u p t u n g ffir alle a' mit 1 < a ' < a bewiesen. Sei ohne Einschrfinkung p : = p t die kleinste unter allen Primzahlen P x , . . . , P , , q l . . . . . % . Wit setzen b ' = P2 ' ' . - ' Pn, also a = p b . Wir ffihren zunfichst folgende A n n a h m e zum W i d e r s p r u c h : Es giltp 4= q , ffir alle l~ = 1. . . . . m. Dazu setzen wit q ' = ql, c ' = q2 " ..- ' qm, also a = q c . N a c h Ann a h m e fiber p gilt p < q. Definieren wir a " = a - pc:, so gilt 1 < a' < a wegen p c < q c = a. Die Zahl a' gestattet wegen a = p b = q c Faktorisierungen d = p ( b - c) = (q - p ) c dabei sind auch die F a k t o r e n q - p, b - c u n d c natfirliche Zahlen > 1 und < a. N a c h I n d u k t i o n s v o r a u s s e t z u n g haben also a', q - p, b - c, b und c sfimtlich eindeutige Primzerlegungen. Die Gleichung a' = p ( b - c) zeigt, dab p in d e r Primzerlegung yon a' v o r k o m m t . Wegen der Eindeutigkeit folgt daher aus der Gleichung a' = (q - p) c, dab p in d e r Primzcrlegung yon q - p oder c v o r k o m m e n muB. D a c = q 2 . . . " q,, d i e Primzerlegung von c ist und da p nach A n n a h m e von allen q2 . . . . . q,, verschieden ist, tritt p in d e r Primzerlegung yon q - p a u f . Es gibt also eine natfirliche Zahlkmitq-p=pk, d . h . q = p ( k + 1),d.h. p l q , u n d d i e s i s t w e g e n l < p < q ein Widerspruch zur Primzahleigenschaft von q. Dieser Widerspruch zeigt, dab es einen Index.j, 1 < j < m, geben muB m i t p = q,i" Wir numerieren die q, so, dab gilt: p~ = p = ql. Aus der Kfirzungsregel folgt nun: b = P2 9 -.. "P,, = q 2 " . . . " qm" Da auch, wie oben bemerkt, die Primzerlegung von b eindeutig ist, so gilt n - 1 = m - 1 und q2 = P 2 . . . . . qm =Pm (bei geeigneter N u m e r i e r u n g der q2 . . . . , qm). D a auch pl = q~, ist der Eindeutigkeitssatz bewiesen. Der obige Beweis ist nicht nur vom F u n d a m e n t a l l e m m a 1.4 unabhS, ngig, sondern m a n k a n n dieses sogar umgekehrt aus der Eindeutigkeit der Primzerlegung folgern. Der Leser lege sich dazu selbst einen Beweis zurecht.

4*. Kritische Bemerkungen. Der Zermelosche Z u g a n g zum H a u p t s a t z der elementaren Zahlentheorie ist wohl der eleganteste und ,,6konomischste", aber gewiB nicht unbedingt der didaktisch beste. NatOrlicher scheint der von uns eingeschlagene Weg zu sein, zunfichst das F u n d a m e n t a l l e m m a 1.4 zu beweisen und anschlieBend den H a u p t s a t z zu folgern. ,,In einer Anffingervorlesung wfirde ich es fibrigens doch vorziehen, die Division mit Rest voranzustellen, erstens, weil man sie nachher doch braucht .... zweitens aber vor allem darum, weil die indirekte (Zermelosche) Beweismethode psychologisch nun einmal

1.3.1 Anzahl aller positiven Teiler

33

weniger iiberzeugend ist . . . . AbschlieBend mGchte ich sagen . . . . daB Z e r m e l o s Beweis ... im U n t e r r i c h t woh! erst da a m Platz ist und auch erst da v o m L e r n e n d e n richtig gewfirdigt werden k a n n , wo die A u f m e r k s a m k e i t d a r a u f gerichtet ist, den Satz v o n d e r eindeutigen Zerlegung in P r i m e l e m e n t e von d e m Bereich der natiirlichen Z a h l e n auf andere Bereiche der Z a h l e n t h e o r i e o d e r Algebra zu /.ibertragen." (Aus einem Brief von E. BESSEL-HAGEN an H. ULM, auszugsweise a b g e d r u c k t in den Semesterberichten Mfinster 11 (1937/38), S. 123-126). Schon EUKLID bewies zunfichst das F u n d a m e n t a l l e m m a , wobei er a u f d e m heute nach i h m b e n a n n t e n Euklidischen A l g o r i t h m u s a u f b a u t e (vgl. 2.1.2). D e r in 1.4 gegebene kurze und recht einfache Beweis geht auf GAUSS ( D i s q u i s i t i o n e s A r i t h m e t i c a e , Art. 13, 14) zurfick, fand j e d o c h in der Folgezeit wenig Beachtung. ,,Es ist historisch merkwiirdig, daB dieser einfache Beweis in Vergessenheit geriet. DIRICHI.ET knfipfte in seinen Vorlesungen wieder an EUKLID und den Euklidischen A l g o r i t h m u s an, und so setzte sich die M e i n u n g fest, d a b der Euklidische A l g o r i t h m u s ... die wesentliche G r u n d l a g e ffir a n a l o g e Beweise in hGheren Z a h l e n g e b i e t e n bilden mfisse . . . . So hat in diesem einen P u n k t e ausn a h m s w e i s e DIRICHLET die Z a h l e n t h e o r i e zuri.ickgebracht; hGchst w u n d e r b a r bei allem, was er sonst fiir die Z a h l e n t h e o r i e an unvergleichlich SchGnem geschaffen hat." (Aus d e m schon zitierten Brief von E. BESSEL-HAGEN an H. ULM.) Aufgaben:

1) Folgern Sie aus der Eindeutigkeit der Primzerlegung das Fundamentallemma 1.4. 2) Ffihren Sie ffir die Menge E : = {4k + 1 : k e N } entsprechende Betrachtungen durch wie ffir die Menge D aus der Bemerkung in Abschnitt 2. Zeigen Sie insbesondere, daB in E die Zerlegung in in E unzerlegbare Elemente nicht eindeutig bis auf Reihenfolge ist. 3) Seien a und b positive natfirliche Zahlen mit der Eigenschaft, daB es keine Primzahl gibt, die zugleich a und b teilt. Beweisen Sie: Gibt es ein c ~ N mit ab = c 2, so existieren x, y ~ N mit a = x 2 und b y2. 4) ES seien a, b natfirliche Zahlen, ffir die gilt: a l b 2, b 2 ]a 3, a 31 b4, b41 a 5..... =

Zeigen Sie: a = b.

w3

Anwendungen des Hauptsatzes

Wir geben in diesem P a r a g r a p h e n signifikante A n w e n d u n g e n , die auch in der historischen E n t w i c k l u n g der e l e m e n t a r e n Z a h l e n t h e o r i e eine groBe Rolle gespielt haben. 1. Anzahl aller positiven Teiler. D e r H a u p t s a t z liefert sofort ein wichtiges

Teilbarkeitskriterium:

Es

sei

a > 1

eine

a = p"~' 9p ~ : 9 . . . 9p r~ i h r e k a n o n i s c h e P r i m z e r l e g u n g .

natfirliche

Zahl

und

Dann sind folgende Aussa-

Anzahl aller positiven Teller

34 gen iiber eine natiirliche

i)

Zahl

1.3.1

b > 1 a'quivalent:

bla.

ii)

E s g i l t b = p"~' 9 p ~

9 . . . . p " ~ " m i t 0 <= IJo <_<_m o fi~r a l l e C = 1 . . . . .

r.

B e w e i s : i) ~ ill: Es gibt ein v c N mit a -

b y . In der P r i m z e r l e g u n g von b k6nnen also wegen der Eindeutigkeit h6chstens die P r i m f a k t o r e n P l , - - - , P ~ und keine anderen auftreten. Tritt po in der Potenz p~o auf, so gilt p~"oI b und also auch p~o I a, d.h. a = p ~ w mit w e N . Dies hat wegen a = p T * . . . . . p ~ . . . . . p T r die Ungleichung 0 < go < mo zur Folge. ii) ~ i): Setzt m a n

~: = p,,,

,,p,2~

,2.....

p;,.. ,,r,

so gilt v c N wegen m~ - ll~ > 0, ~o = 1. . . . . r, und welter rl,tLln//2

b y = t ' t 1"2

,t/r

"''"

" Pr

.

p~lI

]/1

??12

112

P2

mr

" ' ' ' " Pr

Ilr

ml

nz2

= P t 1)2

9

....p'["

= a, []

also b la.

Bezeichnen wir ftir jede nattirliche Zahl a > I mit r(a) die Anzahl aller positiyen Teller von a, so ist r(a) stets endlich (nach Satz 1.1). Bereits PLATON (427 348/347 V. Chr.) wuf3te, wie m a n im 5. Buch seiner G e s e t z e lesen kann, d a b die Z a h l 5040 g e n a u 60 positive Teller hat: r ( 5 0 4 0 ) = 60. I m 16. und 17. J a h r h u n d e r t erwachte das Interesse ffir die Teileranzahl; so b e m e r k t e CARDANO (1501 1576) im Jahre 1537, d a b ein P r o d u k t a v o n r verschiedenen P r i m z a h l e n genau 2 r - 1 positive Teller < a hat. Mit Hilfe des Teilbarkeitskriteriums ist es leicht, eine F o r m e l fiir r(a) anzugeben, die es erm6glicht, z ( a ) mittels der Primzerlegung von a auszurechnen. Satz: E s s e i a >= 1 e i n e n a t i i r l i c h e Z a h l u n d a = p,r . p,~2 . . . . . P"r'" i h r e k a n o n i s c h e Primzerlegung.

Dann gilt

r(a) = I "] (m,, + 1),

insbesondere

o=1

T(p~'~ . p T ~ . . . . ' p 7 r) = ( I

o=1

r(p~~

(durch I n d u k t i o n nach der Anzahl r der verschiedenen P r i m f a k t o r e n ) ' Falls r = 1, so sind auf G r u n d des Teilbarkeitskriteriums genau die (m~ + 1) Zahlen 1 , p ~ , p 2 . . . . . p ' ~ die positiven Teller von p]". Es folgt t ( p ] " ) = m~ + 1. Sei nun r > 1. D a n n gilt" Beweis

a = b p ' } '~

mit

b'=p~".....pr

"'1'.

N a c h I n d u k t i o n s v o r a u s s e t z u n g ist r ( b ) = ( m 1 + 1 ) . . . . . (mr 1 + 1). A u f G r u n d des Teilbarkeitskriteriums erhfilt m a n alle positiven Teller von a, wenn m a n s/imtliche positiven Teller von b n a c h e i n a n d e r mit 1, Pr, p2 . . . . , pTr multipliziert.

1.3.2

Produkt aller positiven Teiler

35

Dies bedeutet r

r(a)=r(b).(m

r + 1)= H

~o=1

(me+

1).

dieser e pliziten ormel ist die O,eichung (o01

= [I

"c(p~'~) e n t h a l -

0 =1

ten.

[]

B e i s p i e l e : / ) 120 = 23 93 9 5, T(120) = (3 + 1) (1 + 1) (1 + 1) = 16; 2) 1 0 2 4 = 2 TM, r ( 1 0 2 4 ) = 10 + 1 = 11; 3) 5 0 4 0 = 2'* 9 32 - 5 9 7, r ( 5 0 4 0 ) = 5 93 92 92 = 60 (PLATON); 4) a = P l P 2 " . . . "Pr, z(a) = 2 92 - ... 92 = 2 r

Produkt

(CARDANO).

2. Produkt aller positiven Teiler. M i t H i l f e d e r A n z a h l r ( a ) lfiBt s i c h d a s P(a) aller positiven Teiler von a > 1 einfach angeben.

S a t z : Fiir das P r o d u k t P ( a ) aller p o s i t i v e n Teller einer natiirlichen Z a h l a > 1 g i l t P ( a ) = a r(a)/2. Beweis: Wir ordnen die positiven Teiler d von a der Gr6Be nach, etwa 1 = d 1< d2 < Dann

...

< d s_ 1 < ds : = a,

wobei

s:=

erhfilt

man

r(a).

gilt jeweils: d I d s = a, d 2 d s 1 = a . . . . .

Wir unterscheiden

zwei Ffille:

1. F a l l : s ist g e r a d e , d l d t + t = a. E s f o l g t :

etwa

P(a) = did 2 .....

s = 21. D a n n

d s = (dl ds) (d2d s 1 ) ' . . . "

als l e t z t e

Gleichung

(dtdl+ l) = a I = az(a)/2.

2. F a l l : s ist u n g e r a d e , e t w a s = 21 + 1. D a n n e r h a l t e n w i r als l e t z t e G l e i c h u n g e n dl dz + 2 a, d I + t dl+ 1 = a. J e t z t f o l g t : =

P ( a ) = (d l ds) . . . . . (dtdl+ 2) d t + l = al dt+ l. 1

D a dz+ , = a 2, s o f o l g t w e g e n l + g1 = 51 s u n d s

=

r(a)

wieder:

1

P(a)

=

a t+~

=

arla)/2

"

[] 1

I m e b e n d i s k u t i e r t e n 2. F a l l h a b e n w i r n u r f o r m a l m i t d e r W u r z e l a5 g e r e c h n e t ,

1

d a j a a 5 = d 1+1 9 N . B e i s p i e l e : 1) 20 = 22 9 5, r ( 2 0 ) = 3 9 2, P ( 2 0 ) = 203 = 8000. 3

2) 25 = 52 , r ( 2 5 ) = 3, P ( 2 5 ) = 255 = 53 = 125. 3) Sei a : = p3 m i t p 9 •. D a n n g i l t r ( a ) = 4 u n d P ( a ) = a 2. Sei a : = p q m i t p, q 9 IP, p 4= q. D a n n g i l t w i e d e r z(a) = 2 92 u n d P ( a ) = a 2.

36

Summe aller positiven Teiler

1.3.3

Es lfil3t sich zeigen, dab die eben betrachteten Ffille a = p3 und a = p q sowie a = 1 die einzigen Ffille mit P(a) = a 2 sind. 3. Summe aller positiven Teiler. Ffir jede natfirliche Zahl a => 1 bezeichnen wir mit a(a) die S u m m e aller positiven Teiler von a. Wir schreiben aia) = Z d,

ara

wobei

wir

verabreden,

dab

Z immer S u m m a t i o n fiber alle positiven ala ( = natfirlichen) Teiler yon a bedeutet. R. DESCARTES (1596 1650) bemerkte 1638, dab ffir jede Primzahl p und jeden E x p o n e n t e n m = 1 die S u m m e aller positiven Teiler yon p m die kleiner als pm sind, den Wert pm __ I hat. J. WALLlS (1616--1703) kannte 1658 den folgenden p-I Satz: Es sei a = Plm 1 P21'112 . " " ' P r191r eine positive natiirliche Z a h l in kanonischer Primzerlegung. Dann gilt a(a) = [ I P o - 1 o =l P o - 1 '

insbesondere a

P \Q=x

/

= [ I a(p'~9. o=1

Beweis: Die positiven Teller yon a sind laut Teilbarkeitskriterium 1 genau s~mtlichc Zahlen p ~ , p ~ 2 . . . . p ~ , , mit 0 < #o < mo, ~o = 1 . . . . . r. Ihre S u m m e ist ml

0.(a)=

.....

Z

mr

l i t . . . . . tt,-= 0

P~''...'P~=

ml

m2

Z

Y~ ... Y~ P ~ ' P ~ : ' . . . ' P ~ " .

/tl=0

mr

tL2 = 0

~tr = 0

Aus den Regeln ffir das Rechnen mit endlichen S u m m e n folgt:

Mittels der Summenformel

,no

y~ p ~ =

p ~ e + l __ 1

ffir die endliche geometrische

Reihe (vgl. 02 und beachte Po # 1) folgt die Behauptung. 24_1

Beispiele: 1) 7 2 = 2 3 - 3 2 , a ( 7 2 ) = 2 -

2) 9 7 = 9 7 1 , o - ( 9 7 ) -

972-

1

97-

1

33_1 I " 3-1

-97+

1 =98;

24--I

32--1

3) 1 2 0 = 2 3 . 31" 51 , o-(120)= 2 - - 1 4) a = p", a ( p m) =

pm + i p-I

_

_

1

= 15.13=

-

pm p--I

3--1

1

+ p"

52--1

3-1

I~ 195;

- 15.4.6=360;

(DESCARTES).

1.3.4 Vollkommene Zahlen

37

4. Vollkommene Zahlen. Ein besonderes Interesse hat m a n seit jeher den , , v o l l k o m m e n e n " Zahlen entgegengebracht. Dabei heiBt eine natiirliche Zahl a > 1 v o l l k o m m e n , wenn gilt: o-(a) = 2a. So sind z. B. 6 und 28 v o l l k o m m e n . Bereits im Alten Testament soll die Vollkommenheit der Zahl 6 erw/ihnt w o r d e n sein; L. E. DICKSON verweist im Band 1 von [3] a u f das Buch der K6nige II, 13, 19.* Die Auffassung, diese Zahlen seien , , v o l l k o m m e n " , wird besser verst/indlich, wenn m a n weiB, dab im A l t e r t u m die Zahl a selbst nicht mit zu ihren Teilern gez/ihlt wurde, und also die v o l l k o m m e nen Zahlen a durch Z d = a gekennzeichnet sind (vgl. EUKLID, E l e m e n t e , dla, d ~ a

Buch VII, Definition 22). AUGUSTINUS (354-430) sagt, dab G o t t die Welt in 6 Tagen schuf, well G o t t e s Sch6pfung und 6 v o l l k o m m e n sin& Auch die 28-tfigige D a u e r des M o n d z y k l u s wurde immer gern mit der Vollkommenheit yon 28 in Z u s a m m e n h a n g gebracht. Das Problem, alle v o l l k o m m e n e n Zahlen zu bestimmen, ist bis heute ungel6st. Es lassen sich aber alle g e r a d e n v o l l k o m m e n e n Zahlen angeben. Jede gerade Zahl a > 2 schreibt sich eindeutig in der F o r m a = 2 ~- 1 b, wo s > 2 und b ungerade ist. Wir zeigen folgende .

Charakterisierung der geraden vollkommenen Zahlen: F o l g e n d e A u s s a g e n fiber eine natfirliche Z a h l a = 2 ~ 1 b, s >= 2, b ungerade, sind dquivalent:

i) ii)

b ist P r i m z a h l , und es gilt: b = 2 ~ - 1. a ist vollkommen.

B e w e i s : i) => ii): N a c h Voraussetzung ist b 4= 2 Primzahl und also a = 2 s ~ 9b die

Primzerlegung von a. N a c h Satz 3 gilt daher: =

2~_1

b2_1

-

1 ) . (b + 1).

D a b + 1 = 2 ~ -- 2 92 ~ 1 nach Voraussetzung gilt, so folgt: a(a)=2.2

~-1.(2 ~_1)=2a.

ii) => i): D a b ungerade ist, k o m m e n in der kanonischen Primzerlegung yon b nur Primzahlen 4= 2 vor. Fiir a = 2 ~- 1. b gilt d a h e r nach Satz 3: 2Sb = 2a = 6(a) = a(2 s - x ) . a(b) = (2 s -

1) a(b).

Hieraus folgt: a(b) *

25 b = b + c 2s - 1

mit

c:---

b >0. 25- 1

PLATON verwendet im S t a a ! den Begriff ,,vollkommene Zahl" anders als oben deft-

niert, ebenso ARISTOTELES(384--322 V.Chr.) in der Metaphysik.

38

Vollkommene Zahlen

1.3.4

Wegen a(b) e N und b c N gilt c e ~, also c ~ N • Die Gleichung b = c(2 s - 1) lehrt, d a b c ein positiver Teiler von b ist. Wegen o ( b ) = b + c sind d a n n b und c die einzigen positiven Teiler v o n b. D a b = (2 s - 1) c > 3 wegen s > 2 und c > 1, m u g b eine P r i m z a h l sein, und es m u g gelten c = 1, d.h. b = 2 ~ - 1 ~IP. Bemerkung: Die V o l l k o m m e n h e i t aller Z a h l e n 2 ~ ~ 9 (2 ~ - 1), wo der zweite F a k tor P r i m z a h l ist, war bereits EUKLID bekannt. Wir wollen prfifen, was sich ffir s = 2, 3, 4 . . . . ergibt:

s=2:b=22-1

=

3elP,

a=

2

s=3:b=23-1

=

7tiP,

a=

4

s=4:b=24-1=

15~IP,

a=

s=5:b=2S-1

=

31elP,

a-16

s=6:b=U'-l= s= 7:b=27-1

63~1P, = 127elP,

a=32 a=64

3 =

6,

vollkommen

7 =

28,

vollkommen

15,

8

31=

unvollkommen 496,

63, 127 = 8128,

vollkommen unvollkommen vollkommen.

Die ersten vier geraden v o l l k o m m e n e n Zahlen sind also 6, 28, 496, 8128; diese waren schon den Griechen vertraut. Die Frage, ob es a u g e r den von EUKHD a n g e g e b e n e n geraden v o l l k o m m e n e n Zahlen noch weitere solche Zahlen gibt, wurde erst 2000 J a h r e nach EUKLID von EULER negativ b e a n t w o r t e t : Er gab den ersten Beweis der I m p l i k a t i o n i i ) ~ i). Wfihrend die F r a g e nach den geraden v o l l k o m m e n e n Zahlen durch das obige Ergebnis grundsfitzlich gcl6st ist, hat m a n n o c h keine u n g e r a d e n v o l l k o m m e n e n Zahlen angeben k6nnen. Der naheliegende Versuch, die Gleichung a(a) = 2 a in der P r o d u k t g e s t a l t

h P o=1

+1-1-2 Hr Po - 1

o=l

,.o

wo also

Po '

2 < Pl < ... < Pr,

zu bezwingen, fiihrt schnell in ein L a b y r i n t h von Teilbarkeitsbedingungen, das zu Depressionen Anlal3 gibt. I m m e r h i n hat m a n folgendes zeigen k6nnen" Eine ungerade vollkommene Z a h l a hat mindestens 8 verschiedene Primteiler (d. 1l. r>8). Es gibt keine ungerade vollkommene Z a h l a m i t a < 10 s~

Als Probe, wie m a n diese Frage anpackt, b e m e r k e n wir, d a b u n g e r a d e v o l l k o m mene Zahlen zwei verschiedene Primteiler h a b e n miissen: Eine Z a h l a = p " ist nfimlich niemals v o l l k o m m e n , da wit wissen (DESCARTES): pm a(a) =

__

I

p -- 1

4- t )m --

a

--

1

p -- 1

+a
(I

+a~a+a=2a.

1.3.5

Mersennesche P r i m z a h l e n

Als Verallgemeinerung

dieser Abschfitzung

39 lfigt s i c h f o l g e n d e A u s s a g e b e w e i s e n :

Fi~r j e d e u n g e r a d e nati~rliche Z a h l a -_ P l?r P2m 2 m i t g e n a u 2 (verschiedenen) P r i m teilern gilt: a(a) < 2 a . Bereits im A l t e r t u m n a n n t e m a n eine natfirliche Z a h l a > 1 defizient bzw. abundant, wenn gilt a(a) < 2a, bzw. a(a) > 2a. In den eben formulierten Aussagen wird also behauptet, d a b alle u n g e r a d e n natfirlichen Zahlen, die h 6 c h s t e n s 2 verschiedene Primteiler haben, defizient sind. Die Z a h l 12 ist a b u n d a n t , da wegen 12 = 21 . 3 gilt: i(12)

= (23 - - 1) 94 =

28 > 24.

Wir zeigen n u n noch, d a b es extrem a b u n d a n t e Z a h l e n gibt. S a t z : Sei n ~ N , n > 1, und sei a : =

i(a) a

1

>1+

+

1

+

1

+

=

n!. Dann gilt

+ "'"

1

.

n

Speziell gibt es zu jeder (noch so groflen) natiirlichen Zahl N eine natiirliche Zahl a > 1, so daft gill : a(a) > N ' a. Beweis: Fiir jedes a _> 1 gilt laut Definition: a(a) = Z d, also a(a) a

dla

d

--~. d]a a

.

N u n geh6rt zu jedem Teiler d yon a der s o g e n a n n t e komplementdre Teiler d':

a

~. Durchl/iuft

d alle positiven Teiler von a, so durchl/iufl auch d' alle positiven Teiler yon a. D a h e r folgt: if(a)

a

1

1

Y d'

7'

d'la

wobei wir zuletzt einfach wieder d statt d' geschrieben haben. W/ihlt m a n n u n speziell a = n!, so sind sicher alle Z a h l e n 1, 2, 3 . . . . . n - 1, n positive Teller von a. D a h e r ist in diesem Fall

i(a) a

>1+ =

1 2

+

1 3

+

1 4

+

"'"

+

1 n

.

Hier steht rechts eine P a r t i a l s u m m e der h a r m o n i s c h e n Reihe. Wir fibernehmen n u n aus der Infinitesimalrechnung den Satz, d a b diese P a r t i a l s u m m e d u r c h geeignete Wahl yon n beliebig grol3 gemacht werden k a n n (Divergenz der h a r m o n i s c h e n Reihe). Speziell gibt es d a h e r zu j e d e m N > 1 ein n > 1, so d a b gilt

i(n!) >N. n! 5. M e r s e n n e s c h e P r i m z a h l e n . D u r c h d i e C h a r a k t e r i s i e r u n g gerader vollkommener Zahlen im vorigen Abschnitt wird man automatisch zu folgender F r a g e g e f f i h r t : Fiir w e l c h e E x p o n e n t e n s > 1 ist 2 ~ -- I eine P r i m z a h l ? W i r s e t z e n z u n f i c h s t M s : = 2 s - - 1 e N • f f i r j e d e n a t f i r l i c h e Z a h l s > 1. F a l l s M s ~ IP, s o heil3t M~ eine M e r s e n n e s c h e Primzahl.

40

Mersennesche Primzahlen

1.3.5

Mit dieser Bezeichnung wird der franz6sische F r a n z i s k a n e r m 6 n c h M. MERSENNE (1588 1648) geehrt, der grol3e Anstrengungen unternahm, solche Primzahlen zu finden, und z.B. mit den franz6sischen M a t h e m a t i k e r n P. FERMAT (1601 -1665) und R. DESCARTES (1596 1650) dariiber korrespondierte. Es lfil3t sich sofort zeigen: Satz: Die Zahl M~ = 2 ~ - I ist hdchstens dann eine Mersennesche Primzahl, wenn der Exponent s selbst eine Primzahl ist. Beweis. Ist nfimlich s ein P r o d u k t s = u t~'aus natiirlichen Zahlen u > 1, ~ > 1, so hat man die Faktorisierung (endliche geometrische Reihe!)

2 ~ - 1 = (2u)''

1 = (2 u - 1} (1 + 2" + (2") 2 +

.

.

.

+ (2")~'-1),

in der beide F a k t o r e n rechts > 1 sind. In diesem Fall ist also auch M, zerlegbar. Wir haben in Abschnitt 4 bereits gesehen, dab in den F~illen p = 2, 3, 5, 7 in der Tat die Zahlen Mp = 3, 7, 31,127 Mersennesche Primzahlen sind. Es ist nun aber keineswegs so, dal3 jede Primzahl p zu einer Primzahl 2 p - 1 ftihrt, wie vide Mathematiker, d a r u n t e r kein geringerer als G.W. LEIBN1Z (1646 1716), geglaubt haben. Schon f/Jr p = 11 erhfilt man die zusammengesetzte Zahl M l l =211 - 1

=2047=23-89

Ftir p = 13, 17, 19 ergeben sich wieder Primzahlen; zu p = 23 geh6rt erneut eine zusammengesetzte Z a h l So werden wit in 5.1.1 mittels K o n g r u e n z e n zeigen, dab 47 ein Teiler von Mz3 ist. MERSENNE selbst hat alle Zahlen Mr, wobei p die Primzahlen < 257 durchlfiuft, untersucht; allerdings enthalten seine Rechnungen Fehler. Heute weil3 man: Es sei p < 257 eine Primzahl. Dann ist Mp genau dann eine Mersennesche Primzahl, wenn p eine der folgenden zw6(f Zahlen ist:

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127. Es gilt z.B.: 471M23, 2 3 3 t M 2 9 , 2231 M 3 7 , 4 3 1 1 M 4 3 , 1671Ms3. Inzwischen hat man mit Hilfe elektronischer Rechenanlagen noch weitere ,,sehr grol3e" Primzahlen p > 257 gefunden, die Mersennesche Primzahlen liefern; so fand man z.B. 1963 mit dem ILLIAC C o m p u t e r der University of Illinois, dab zu p ' = 11 213 die 23-te Mersennesche Primzahl geh6rt; die zugeh6rige vollkommene Zahl 211212(211213 - - 1 ) besteht aus 6751 Ziffern. Das P o s t a m t in Urbana, 111., tat der Welt dieses Resultat d u t c h einen Poststempel kund:

11213_ l FE,--',,

IS

PRIME

\

J

P.B.'t;21 I NeTIEE

-.0

0 .

I:

]" 1: 9

1.3.6 Fermatsche Primzahlen

41

Mittlerweile kennt man noch gr613ere Mersennesche Primzmhlen, vgl. 2.2.4; dessen ungeachtet ist die prinzipielle Frage, ob unendlich viele Mersennesche Primzmhlen (und entsprechend unendlich viele gerade vollkommene Zahlen) existieren, bis heute unbeantwortet geblieben. 6. F e r m a t s c h e P r i m z a h l e n . In diesem Abschnitt behandeln wir Fermatsche Primzahlen, d.h. Primzahlen der Form 2 S + 1 mit s E IN • . Diese Primzmhlen haben zwax nichts mit vollkommenen Zahlen zu tun, stehen aber in einem engen formalen Zusammenhang mit Mersenneschen Primzmhlen und spielen eine groge Rolle in der Theorie der Kreisteilung; ihr Name ist zu Ehren des grogen franz6sischen Zmhlentheoretikers Pierre de FERMAT gewSahlt. Wir zeigen sofort: Satz: Die Zahl 2 ~ + 1 ist hOchstens dann eine Fermatsche Primzahl, wenn der Exponent s eine Zweierpotenz ist." s U, t E IN. Beweis: Es gilt s k v mit k U, t E IN, und einer ungeraden nattirlichen Zahl v. Wegen ( - 1 ) v - 1 ist dann: 1 + U 1 - ( - 2 ~ f f . Die Summenformel

1-x ~

(l-x)(1 +x+x2+...

+ x ~ 1)

ffir die endliche geometrische Reihe liefert (mit x : 1+2 s

- 2 ~)

(1 +2~)(1 _ 2 ~ + 2 2 ~ _ 23~ + . . . +2(v 1)~).

Im Falle v > 1 gilt k < s und also 1 < 1 + 2 ~ < 1 + 2 s. Dann stehen rechts zwei Faktoren > 1, und man hat eine echte Zerlegung von 2 ~ + 1. Soll 2 S + 1 eine Primzmhl sein, so mug daher notwendig v 1 gelten, d.h. s mug Zweierpotenz sein. [] Man kennt nur ftinf Fermatsche Primzahlen, und zwar 22t + 1

3,5, 17,257, 65537

mit

t

0,1,2,3,4.

FERMAT selbst hat noch vermutet (Sahnlich wie LEIBNIZ von den Mersenneschen Primzmhlen), dab ftir jedes t E IN wirklich eine Primzmhl 22t + 1 entsteht. Doch bereits f i i r t 5 ist 225 + 1 232 + 1 durch 641 teilbax, wie wir in 5.1.1 mittels Kongruenzenrechnung sehen werden. Die Fermatschen Primzmhlen sind von grol3er Bedeutung in der Theorie der Kreisteilung. GAUSS hat n~imlich folgendes bewiesen: Es sei m > 3 eine ungerade natiirliche Zahl. Dann ist das reguldre m-Eck genau dann mit Zirkel und Lineal konstruierbar (d. h. die m-Teilung des Kreises ist mOglich), wenn m ein quadratfreies Produkt Fermatscher Primzahlen ist. Die gr613te bisher bekannte solche Zmhl m ist 3 . 5 . 1 7 . 257. 65537 232 - 1. Wir haben in diesem Paragraphen drei Fragen behandelt, die ungel6st sind: 1) Gibt es ungerade vollkommene Zahlen ? 2) Gibt es unendlich viele Mersennesche Primzahlen 2 p - 1, p E P ? 3) Gibt es unendlich viele Fermatsche Primzahlen 22~ + 1, t E IN?

42

Primzerlegung in Q

1.4.1

Wie keine andere m a t h e m a t i s c h e Theorie ist die elementare Z a h l e n t h e o r i e reich an solchen P r o b l e m e n , die einem N i c h t m a t h e m a t i k e r verst/indlich g e m a c h t werden k6nnen, deren L 6 s u n g jedoch bis heute trotz der A n s t r e n g u n g e n vieler ausgezeichneter M a t h e m a t i k e r nicht gelungen ist. AL~aben: 1) Sei a e N ~. Zeigen Sie: a ist genau dann eine Quadratzahl, wenn r(a) ungerade ist. 2) Zeigen Sie fiir eine natfirliche Zahl a > 1: Es gilt P(a) - a 2 genau dann, wenn entweder a = p3 oder a = pq, p, q e P, p 4= q, ist. 3) Sei a > 1 eine ungerade natfirliche Zahl, a - p'~"'p~ ihre kanonische Primzerlegung. Zeigen Sie: a(a) < 2a. ! 4) Sei a _> 1 eine vollkommene Zahl. Zeigen Sie: ~ ~ = 2. dla

5) Sei /:;,:- 22"+ 1 ffir h e N • Zeigen Sie ffir k E N • F,,ist ein Teiler von k;,+k 2. 6) Sei neine gerade vollkommene Zahl. Zeigen Sie: Die letzte Ziffer (der Dezimaldarstellung) von n ist 6 oder 8. w4

Zahlentheorie im K6rper Q

Wir h a b e n im v o r a n g e h e n d e n P a r a g r a p h e n bereits sowohl bei der F o r m u l i e r u n g als auch beim Beweis von S~itzen Bruchdarstellungen verwendet (z.B. im Satz 3.3 und im Beweis yon Satz 3.4). W i t sind also, obwohl wir U n t e r s u c h u n g e n im Ring 7Z der ganzen Zahlen anstellten, in den K 6 r p e r Q der rationalen Zahlen ausgewichen. Es ist d a h e r nicht mfiBig, wenn wir uns nun etwas n/iher mit Bruchdarstellungen an sich besch/iftigen. Unser H a u p t a n l i e g e n hier ist die Erweilerung des F u n d a m e n t a l s a t z e s der e l e m e n t a r e n Zahlentheorie v o n ~ auf Q. Wir d e m o n s t r i e r e n die K r a f t dieses Satzes ffir Q, indem wit einige Irrationalit'/itsbeweise ffir Wurzeln ftihren. Eine besonders elegante F o r m des H a u p t s a t z e s der elementaren Z a h l e n t h e o r i e gewinnt man, wenn m a n die Vielfachheitsfunktion w , ( a ) einffihrt. W i t diskutieten diese Dinge nut soweit, wie sie z u m Verst/indnis der e l e m e n t a r e n Zahlentheorie unbedingt notwendig sind; der ,,h6here S t a n d p u n k t " , der u.a. zur allgemeinen Bewertungstheorie ffihrt, k a n n nur angedeutet werden. W i t beschliel3en diesen P a r a g r a p h e n mit einer kurzen Diskussion der figyptischen Bruchdarstellungen. D a b e i beweisen wir auf gfinzlich elementare Weise die Existenz der s o g e n a n n t e n Fibonaccidarstellung. 1. Primzerlegung in @. Die Tatsache, d a b jede rationale Zahl 7 + 0 ein Bruch mit ganzzahligem Z'/ihler und positivem N e n n e r ist, f~ihrt schnell zu folgender Verallgemeincrung des H a u p t s a t z e s der elementaren Z a h l e n t h e o r i e ffir ~.

Hauptsatz der elementaren Zahlentheorie fiir @: J e d e r a t i o n a l e Z a h l 7 4= 0 b e s i t z t g e n a u eine D a r s t e l l u n g

1.4.1 Primzerlegung in Q rll I

rtl 2

,

43

mr

Pl P2 "" "Pr ql/11 q2n 2 " ".. " q~s mit f o l g e n d e n Eigenschaften: 1) Es

2)

gilt

e=_+l;

r, s E N ;

Pl,...,Pr,

ql,...,qs~lP;

ml,...,mr,

r/I~...~HsE]N • Pl . . . . , Pr, q l , . . . , qs sind paarweise verschieden; es gilt: Pl < P2 < ... < Pr und ql < q2 < ... < qs. (1

Beweis: E x i s t e n z der Darstellung: Sei 7 = ~ mit a ~ Z, b ~ N ~. D a b 4= 0 und a 4= 0 wegen 7 4: 0, h a b e n a und b Primzerlegungen in 7/. Schreiben wir diese Zerlegungen hin und ktirzen wir nach den Rechenregeln fiir Brtiche die gemeinsamen P r i m f a k t o r e n aus Z/ihler und N e n n e r weg, so gewinnen wit eine Darstellung P 7=e~ ,,2. . . . ' P ~ r , Q = q ] , q ~ 2 . . . . , , wo e = -+ 1 ist und P = Pl,,1 P2 q,,, Primzerlegungen sind mit m 1.... , mr, nl ..... ns ~ N • u n d p~ ..... Pr, qa ..... qs ~ P paarweise verschieden. D u r c h U m n u m e r i e r e n k 6 n n e n wir n o c h erreichen, d a b gilt p~ < P2 < ... < Pr u n d q~ < q2 < ... < qs. Eindeutigkeit der Darstellung: Sei neben der eben gefundenen Darstellung P ~, P ' ;, = t: Q noch eine zweite Darstellung 7 = Q, vorgelegt mit d = _+ 1, wo die P r i m f a k t o r e n von P ' von den P r i m f a k t o r e n von Q' d u r c h w e g verschieden sind. P = r.' P ' Aus ~ Q ~ erhalten wir d u r c h Multiplikation mit Q 9 Q' eine Gleichung im Ring 7 / d e r ganzen Zahlen: ePQ'=e'P'Q. Wegen der Eindeutigkeit der Primzerlegung in 7Z folgt hieraus zun/ichst r. = ~' und weiter, dab die P r i m f a k t o r e n von P, weil sie s/imtlich von denen von Q verschieden sind, unter den P r i m f a k t o r e n von P' (mit mindestens denselben Exponenten) v o r k o m m e n . Ebenso e n t n e h m e n wir obiger Gleichung, dab die P r i m f a k t o r e n von P', da sie alle von denen von Q' verschieden sind, unter den P r i m f a k t o r e n von P (mit mindestens denselben Exponenten) v o r k o m m e n . Dies impliziert die Gleichheit der beiden Darstellungen. []

Beispiel:

594 2 . 3 3 9 11 32 9 1| 2550 - 2 . 3 - 52 9 17 - 52 - 17"

I m soeben bewiesenen Satz ist insbesondere der Satz yon der Existenz und Eindeutigkeit der Darstellung jedes von 0 verschiedenen Bruches als ,,un-

44

Irrationalit~itsaussagen 1.4.2

ktirzbarer Bruch mit teilerfremden Z~ihler und Nenner" enthalten. Der Begriff,,teilerfremd" wird im Kapitel 2 eingeftihrt und ausftihrlich besprochen; wir gehen dann auch auf das Problem der Bruchdarstellung erneut ein. Wir wollen den Hauptsatz eleganter fassen, indem wir die Nennerfaktoren als ZSahlerfaktoren mit negativen Exponenten schreiben. Wir machen hier und auch weiterhin v o n d e r Konvention y n : ( y l ) n ftir alle y/~ 0 aus Q Gebrauch. Wir bezeichnen, um die Konsistenz mit dem Hauptsatz der elementaren Zahlentheorie for Z zu wahren, die vorkommenden Primzahlen wieder mit P l , . . . , Pr (dies sind also alle pj und q~ aus dem Satz, insbesondere hat r jetzt eine andere Bedeutung).

Hauptsatz der elementaren Zahlentheorie fiir Q, zweite Fassung: Jede rationale Zahl 7 7~ 0 besitzt genau eine Darstellung 7

ml

m2

ePl P2 . . . . . p ~ r

mit folgenden Eigenschafien: 1) e -t-1;rEIN;pl,...,prEP;ml,...,mrEZ\{O}. 2) Pl < P2 < ... < Pr. Zum Beweis ist nichts zu sagen; wir nennen die Gleichung 7 wieder die (kanonische) Prim(faktor)zerlegung yon 7 (in Q).

Beispiel: Die kanonische Primzerlegung von ~

e P~ 1 "..." P~r

ist 3 2. 5 2.11 917 1.

Der einzige formale Unterschied zwischen den Haupts~itzen der elementaren Zahlentheorie ftir Q und Z besteht darin, dab die Exponenten m l , . . . , mr nicht mehr notwendig positiv sind. Vielmehr gilt ml > 0 . . . . . mr > 0 ersichtlich genau dann, wenn die zugehOrige Zahl 7 zu Z gehOrt. Diese auf der Hand liegende Kennzeichn u n g d e r ganzen Zahlen unter allen rationalen Zahlen soil ihrer grunds~itzlichen Bedeutung wegen hervorgehoben werden als

Ganzheitssatz: Sei 7 E Q, 7 ~ O; sei 7 e pl/7~tl P2/7~t2 "..." P ~ die kanonische Primzerlegung yon 7. Dann sind folgende Aussagen diquivalent: i) 7 E Z . ii) Alle Exponenten ml, .. . ,mr sind positiv. 2. Irrationalitiitsaussagen. In der Schule lernt man, dab die positive reelle ZaJal ~/-2, deren Quadrat 2 ist und die wir auf Grund des Satzes von PYTHAGORAS als L~inge der Diagonale im Einheitsquadrat vor uns sehen, nicht rational ist. Reelle Zmhlen, die nicht dem K6rper Q angeh6ren, heiBen irrational. Die Wahl des Wortes ,,irrational" ist glticklich-unglticklich zugleich: Einerseits weist diese WortwaJal sehr gut auf die Problematik hin, die mit der Einftihrung dieser ZaJalen verbunden ist; andererseits suggeriert diese WortwaJal Vorstellungen, die zu metaphysischen Spekulationen verleiten und zu nichts ftihren*. Die Existenz von Strecken mit irrationalem L~ingenverh~iltnis war bereits den Griechen bekannt; einer vielzitierten - wenn auch unwahrscheinlichen - Geschichte zufolge soil PY-

1.4.2

Irrationalit~itsaussagen

45

THAGORAS im 6. Jahrhundert v. Chr. ihre Entdeckung mit dem Opfer von 100 Ochsen gefeiert haben. Die allgemeine Idee der Irrationalzmhl ist aber erst am Ende des 16. JaJarhunderts im Zusammenhang mit der Einfiihrung von Dezimalbrtichen aufgetreten (vgl. hierzu auch Kapitel 4). Wir werden im folgenden als Anwendung des Satzes von der Primzerlegung rationaler Zmhlen zeigen, dab neben ~ viele weitere reelle Wurzeln notwendig irrational sin& Wir stellen die Frage, wann zu vorgegebenen Zmhlen n E IN • , 7 E Q, 7 > 0, eine rationale und insbesondere eine nattirliche Zmhl x existiert, so dab gilt: x~ 7. Wir beweisen folgendes Rationalitiitskriterium: E s sei n E IN • 7 E Q, 7 > O; es sei 7

ml

m2

P l P2 die P r i m z e r l e g u n g y o n 7. D a n n sind f o l g e n d e A u s s a g e n d q u i v a l e n t :

i) E s g i b t eine p o s i t i v e r a t i o n a l e Z a h l x m i t x n ii) n teilt j e d e n E x p o n e n t e n m o, p 1 , . . . , r.

" """ p~r

7.

I s t 7 ganz, so ist (ira Fall d e r E x i s t e n z ) a u c h x n o t w e n d i g ganz. B e w e i s : i) ~ ii): S e i x

Gleichung x1/

ql1/1q21/2.... 9qs1/s die kanonische Primzerlegung von x. Die 7 schreibt sich wie folgt

1/1/1 1/1/2

1/1/s

ml

m2

ql q2 " ' " ' q s Pl P2 " ' " ' P ~ r " Die Eindeutigkeitsaussage des Hauptsatzes 1 impliziert s r, ql Pl . . . . . qr Pr und n n l m l . . . . . nnr mr. Die letzten Gleichungen besagen zum einen n ] m o ffir 1 __