Mathematik: Zahlentheorie: Fundamentalsatz der Arithmetik

Kapitel 1: Fundamentalsatz der Arithmetik

Überblick über das Kapitel:

Teilbarkeit
Primzahl/
unzerlegbare Zahl
Satz von Euklid
Fundamentalsatz
der Arithmetik
Primfaktorzerlegung

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:

  1. Für jedes ganze a gilt:  ,   und  .
  2. Gilt  , so gilt auch   und  .
  3. Für   gilt:  .
  4. Gilt   und  , so gilt auch  .
  5. Gilt   und  , so gilt auch  .
  6. 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

Bearbeiten

Wenn 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

Bearbeiten

Wie 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

Bearbeiten

Inzwischen 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 Faktor

Bearbeiten

Wenn 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