Mathematik: Zahlentheorie: Fundamentalsatz der Arithmetik
Kapitel 1: Fundamentalsatz der Arithmetik
Überblick über das Kapitel:
|
Eine sehr zentrale Eigenschaft der natürlichen Zahlen ist die, dass sich jede natürliche Zahl als Produkt von Primzahlen darstellen lässt, und dass diese Darstellung im Wesentlichen sogar eindeutig ist. Dieses Resultat nennt man den Fundamentalsatz der Arithmetik.
Natürlich benötigt man hierfür den (in der Zahlentheorie zentralen) Begriff der Primzahl. Eine Definition der Primzahl könnte lauten: Eine Primzahl ist eine Zahl, die genau zwei natürliche Teiler hat, nämlich 1 und sich selbst. Wir werden Primzahlen anders definieren, da sich dies später bei Verallgemeinerungen als praktisch erweisen wird. Zahlen, die genau zwei natürliche Teiler haben, nennen wir irreduzible Zahlen. Wir werden dann sehen, dass beide Definitionen die gleiche Zahlenmenge definieren.
Im Zusammenhang mit den Primzahlen werden wir noch kurz auf ein weiteres Resultat eingehen, nämlich die Tatsache, dass es unendlich viele Primzahlen gibt. Dies wird als der Satz von Euklid bezeichnet.
Bevor wir aber zu den Primzahlen kommen, müssen wir etwas Vorarbeit leisten und uns den Teilbarkeitsbegriff anschauen.
Teilbarkeit
Bearbeiten- Definition
- Findet man zu zwei Zahlen eine weitere Zahl mit der Eigenschaft, dass , so sagt man, die Zahl teilt die Zahl und schreibt . Weiterhin sagt man auch, ist ein Vielfaches von : Teilbarkeit
Hier ein paar Regeln für die Teilbarkeit, die sich leicht beweisen lassen:
- Für jedes ganze a gilt: , und .
- Gilt , so gilt auch und .
- Für gilt: .
- Gilt und , so gilt auch .
- Gilt und , so gilt auch .
- Gilt und , so gilt für alle die Relation .
Die zweite Regel besagt offenbar, dass man sich bei der Untersuchung von ganzen Zahlen auf die Teilbarkeit der natürlichen Zahlen beschränken kann. Hierzu benutzt man noch die folgende Redeweise: Eine Zahl ist ein echter Teiler von , falls und gilt.
Primzahlen
BearbeitenWenn man jemanden auf der Straße fragt, was Primzahlen sind, erhält man viele verschiedene Antworten, insbesondere die Frage, ob eine Primzahl ist, wird kontrovers beantwortet. In der Mathematik gibt es zwei etwa gleich weit verbreitete Definitionen, die äquivalent sind. In beiden Fällen ist keine Primzahl. Wer sich dafür interessiert, warum dies so ist, kann dies unter Warum 1 keine Primzahl ist nachlesen.
Wir beginnen hier mit der dem Laien eher unbekannteren Definition, da diese später für die Definition von Primelementen (das ist eine Verallgemeinerung von Primzahlen) benutzt wird. Anschließend zeigen wir, dass diese zur zweiten Definition (Primzahl ist, was genau zwei Teiler hat) äquivalent ist.
- Definition
- Eine Primzahl ist eine natürliche Zahl für die gilt: Falls eine Zahl teilt, so teilt auch einen der Faktoren oder . → Wikipedia:Primzahl
- Beispiele
- ist keine Primzahl, denn: teilt , aber teilt weder noch .
- ist eine Primzahl, denn: Seien und beliebige Zahlen, so dass ein Teiler des Produktes ist. Dann gibt es eine Zahl mit .
Es ist zu zeigen, dass ein Teiler von oder ist. Ist durch teilbar, so sind wir fertig. Ist dagegen nicht durch teilbar, so gibt es eine Zahl mit . Zusammen ergibt sich: und damit . Somit ist ein Teiler von . → Details
Wie führen jetzt die "zweite Definition" von Primzahlen an. Um diese beiden Definitionen auseinander zu halten, nennen wir die Primzahlen hier unzerlegbare Zahlen. (Achtung: Diesen Begriff führen wir hier nur der Übersichtlichkeit halber ein. In der Mathematik ist der Begriff nur in seiner Verallgemeinerung "unzerlegbares Element" bekannt.)
- Definition
- Eine unzerlegbare (irreduzible) Zahl ist eine natürliche Zahl , die keine echten Teiler hat. → Wikipedia:Irreduzibles Element
Wie schon erwähnt sind Primzahlen und unzerlegbare Zahlen genau die gleichen. Die Unterscheidung wird aber interessant, wenn man zu allgemeineren Ringen übergeht und dort analog Primelemente und irreduzible Elemente definiert. Hier fallen die beiden Begriffe nicht immer zusammen.
Wir werden hier erst mal nur zeigen, dass jede Primzahl eine unzerlegbare Zahl ist. Damit der Beweis der Umkehrung nicht unnötig kompliziert wird, benötigen wir das Konzept des größten gemeinsamen Teilers, welches erst im nächsten Kapitel eingeführt werden wird.
- Satz
- Jede Primzahl ist eine unzerlegbare Zahl.
- Beweis
- Sei Primzahl. Angenommen, es gäbe einen Teiler von , dann gilt . Da Primzahl ist, teilt mindestens eine der beiden Zahlen und . Sicherlich teilt nicht , da und ein Teiler von ist. Also gilt , das heißt, es existiert eine Zahl mit . Setzen wir diese Formel für in ein, so erhalten wir und damit woraus folgt. Dies ist aber ein Widerspruch zur Annahme, dass ist.
Im Folgenden benutzen wird die Begriffe "unzerlegbare Zahl" und "Primzahl" synonym, auch wenn wir die Umkehrung des obigen Satzes erst im nächsten Kapitel zeigen werden.
Satz von Euklid
BearbeitenWie viele Primzahlen gibt es? Bereits Euklid wusste ca. 300 Jahre vor unserer Zeitrechnung, dass es unendlich viele Primzahlen gibt. Bevor wir den nach ihm benannten Satz formulieren werden, wollen wir ein Lemma beweisen, welches wir dort benötigen:
- Lemma
- Der kleinste Teiler einer natürlichen Zahl , der größer als ist, ist eine Primzahl.
- Beweis
- besitzt auf alle Fälle einen Teiler, der größer als ist, nämlich selbst, somit auch einen kleinsten solchen. Sei der kleinste Teiler von , der größer als ist. Wir behaupten, ist eine Primzahl. Angenommen, sei keine Primzahl, dann gibt es einen echten Teiler von . Dieser ist aber auch ein Teiler von und größer als , was ein Widerspruch zur Voraussetzung, dass der kleinste solche Teiler sei, ist.
- Satz (von Euklid)
- Es gibt unendlich viele Primzahlen. → Wikipedia:Satz von Euklid
- Beweis
- Angenommen, es gäbe nur endlich viele Primzahlen und diese seien so betrachtet man die Zahl . Da diese beim Teilen durch den Rest lässt, ist sie durch keine der Zahlen teilbar. Dies bedeutet aber, dass der kleinste Teiler von , welcher nach dem Lemma eine Primzahl ist, eine weitere noch nicht aufgeführte Primzahl sein muss.
- Beispiel
- Nehmen wir einmal an, und seien die einzigen Primzahlen, dann erhalten wir nach dem Beweis des Satzes, die Zahl . Der kleinste Teiler von ist selbst und wir haben eine neue Primzahl gefunden.
Achtung: Die Zahl aus dem Beweis muss selbst nicht unbedingt eine Primzahl sein. Nimmt man etwa an, und seien die einzigen Primzahlen, so ist und ist keine Primzahl. Wohl aber , ihr kleinster Teiler.
Fundamentalsatz der Arithmetik
BearbeitenInzwischen haben wir alles zusammen, um den Fundamentalsatz zu beweisen. Bevor wir dies aber machen, wollen wir noch kurz auf die Frage eingehen, warum dieser Satz so wichtig ist, dass er als Fundamentalsatz bezeichnet wird. Zur Erinnerung: Der Satz besagt, dass sich jede natürliche Zahl im Wesentlichen eindeutig als Produkt von Primzahlen darstellen lässt.
Bei vielen zahlentheoretischen Fragestellungen ist es möglich, diese mit Hilfe des Fundamentalsatzes auf Primzahlen, oder oftmals auch auf Primzahlpotenzen, zu beschränken. Das heißt, man kann aus einer Lösung, die nur mit Primzahlen funktioniert, sehr einfach eine Lösung für beliebige Zahlen konstruieren.
Dies ist beispielsweise bei der Berechnung der Anzahl, der zu einer gegebenen Zahl teilerfremden Zahlen der Fall, oder bei Aussagen über den größten gemeinsamen Teiler bzw. das kleinste gemeinsame Vielfache von zwei oder mehreren Zahlen und beim Lösen polynomialer Kongruenzen. Da es noch viele weitere Beispiele gibt, spielt der Fundamentalsatz in der Zahlentheorie eine derart wichtige Rolle.
- Satz
- Jede natürliche Zahl lässt sich als Produkt von endlich vielen Primzahlen darstellen. Ordnet man diese Primzahlen der Größe nach, so ist diese Darstellung sogar eindeutig. → Wikipedia:Fundamentalsatz der Arithmetik
Man spricht in diesem Zusammenhang auch oft davon, dass die Darstellung im Wesentlichen eindeutig ist.
Leere Produkte und Produkte mit nur einem FaktorBearbeitenWenn Sie mal versucht haben, ein paar Beispiele für diesen Satz zu konstruieren (und das sollten Sie, da sowas eine sehr effektive Möglichkeit ist, zu lernen), dann sind Sie möglicherweise auf Zahlen gestoßen, bei denen Sie keine solche Darstellung finden konnten. Bevor Sie deswegen das Studium der Mathematik aufgeben und beschließen doch lieber in die Wüste zu ziehen und dort Kamele zu züchten1), möchten wir hier auf eine mathematische Konvention hinweisen, die vielleicht das Problem löst. Es gibt Produkte mit zwei, drei, vier, oder noch mehr Faktoren. Es liegt nahe, sich da zu fragen, ob es auch Produkte mit einem, oder gar null Faktoren gibt. Da sich dies als äußerst praktisch erwiesen hat, sind die Mathematiker übereingekommen, dass es sowas geben soll. Produkte mit nur einem Faktor sind dann die Zahl selbst und das so genannte leere Produkt mit null Faktoren hat den Wert 1. Warum macht man das so? Die Idee ist einfach die, wenn ich ein Produkt aus drei Faktoren habe, und eine weitere Zahl an das Produkt dran multipliziere, so erhalte ich ein Produkt aus vier Faktoren. Diese Eigenschaft möchte man auch bei Produkten mit nur einem oder null Faktoren behalten und damit kommt man zwangsläufig auf die gerade eben beschriebene Konvention. War das die Lösung des Problems, oder vielleicht doch die Variante mit den Kamelen in der Wüste? —————————
1) Wir möchten an dieser Stelle darauf hinweisen, dass wir das Züchten von Kamelen als einen durchaus ehrenwerten Beruf erachten und uns bei allen Kamelzüchtern für etwaige, aus diesem unzulänglichen Beispiel entstandenen Missverständnisse entschuldigen.
|
- Beweis
- "Existenz": Als erstes wollen wir zeigen, dass zu jeder Zahl eine Darstellung existiert. Wir machen dies durch Induktion. Die lässt sich als leeres Produkt und jede Primzahl als Produkt mit einem Faktor darstellen. Sei nun keine Primzahl und für alle Zahlen kleiner als bereits bewiesen, dass eine Darstellung existiert. Dann hat einen echten Teiler . Damit lässt sich schreiben als . Da aber und kleiner als sind, ist nach Voraussetzung bereits eine Darstellung als Produkt von Primzahlen für diese Zahlen bekannt. Multipliziert man diese beiden Produkte miteinander, so erhält man eine Darstellung für .
- "Eindeutigkeit": Wir zeigen nun, dass die Darstellung im Wesentlichen eindeutig ist. (Im Rest des Beweises werden wir den Zusatz "im Wesentlichen" weglassen.) Angenommen, es gibt natürliche Zahlen, für die die Darstellung nicht eindeutig ist. Dann gibt es auch eine kleinste solche Zahl, die wir nennen wollen. Wir können davon ausgehen, dass gilt, da nur eine Darstellung besitzt. Nach dem Lemma zum Satz von Euklid besitzt einen kleinsten Teiler , der größer als ist. Dieser Teiler ist eine Primzahl. Betrachten wir die Zahl . Diese Zahl ist kleiner als und hat deshalb nach Voraussetzung eine eindeutige Darstellung
- .
- Damit ist
- eine Darstellung von . Da nach Annahme nicht eindeutig dargestellt werden kann, gibt es eine weitere Darstellung, die ebenfalls einen kleinsten Teiler besitzt. muss jedoch ungleich sein, denn sonst wäre die weitere Zerlegung durch die eindeutige Darstellung von bereits vorgegeben und somit gleich der ersten Zerlegung. Wie oben ist auch eine eindeutige Darstellung, bestehend aus den Faktoren .
- .
- Da der kleinste Teiler von ist, müssen und alle größer als sein. Betrachten wir jetzt die Zahl
- .
- Da ein Teiler von ist, ist auch durch teilbar. Durch Einsetzen der -Zerlegung für und Ausklammern ergibt sich:
- .
- Da , existiert dafür ebenfalls eine eindeutige Zerlegung. Da durch teilbar ist, ist einer der Faktoren. ist jedoch nicht im Produkt der enthalten, also muss gelten und damit . Da und Primzahlen sind muss also gelten . Das ist aber ein Widerspruch zu .
Primfaktorzerlegung
Bearbeiten- Definition
- Die im Fundamentalsatz erwähnte, im Wesentlichen eindeutige Darstellung einer natürlichen Zahl nennt man die Primfaktorzerlegung dieser Zahl. → Wikipedia:Primfaktorzerlegung
Damit diese übersichtlicher wird, schreibt man Primzahlen, die mehrfach in der Darstellung vorkommen als Primzahlpotenzen. Ganz allgemein schreibt man das dann in einer der folgenden beiden Schreibweisen.
Bei der ersten Schreibweise sind die pi die k verschiedenen Primteiler von n. Die zweite Schreibweise ist zuerst etwas gewöhnungsbedürftiger, wird aber von eingefleischten Zahlentheoretikern meist lieber benutzt. Hier wird formal ein unendliches Produkt über alle Primzahlen gebildet. Die Zahlen sind aber für fast alle Primzahlen gleich , somit . Der Faktor ändert aber an einem Produkt nichts. Für die Praxis heißt dies, dass nur die Primzahlen betrachtet werden, für die ist.
- Beispiel
Es ist bis heute ein ungelöstes Problem, ob es ein schnelles Verfahren gibt, die Primfaktorzerlegung einer Zahl zu bestimmen. Da bislang kein hinreichend schnelles Verfahren bekannt ist, wird diese Tatsache heutzutage ausgenutzt, um Daten, z.B. im Internet, zu verschlüsseln. Mehr zu dieser Problematik lässt sich in der Wikipedia unter den Stichworten → Wikipedia:Faktorisierungsproblem → Wikipedia:Faktorisierungsverfahren → Wikipedia:Kryptologie nachlesen.
Ohne dass wir das hier beweisen werden, möchten wir noch erwähnen, dass sich die Primfaktorzerlegung auf ganz ausdehnen lässt. Hierzu benötigt man für die negativen Zahlen noch den Faktor und zudem lässt man auch negative Exponenten zu.
- Beispiel