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

Definition

Findet man zu zwei Zahlen $a,b\in \mathbb {Z}$ eine weitere Zahl $c\in \mathbb {Z}$ mit der Eigenschaft, dass $a\cdot c=b$, so sagt man, die Zahl $a\,$ teilt die Zahl $b\,$ und schreibt $a\mid b$. Weiterhin sagt man auch, $b\,$ ist ein Vielfaches von $a\,$:  Teilbarkeit

Hier ein paar Regeln für die Teilbarkeit, die sich leicht beweisen lassen:

1. Für jedes ganze a gilt: $1\mid a$, $a\mid a$ und $a\mid 0$.
2. Gilt $a\mid b$, so gilt auch $-a\mid b$ und $a\mid -b$.
3. Für $b,k\neq 0$ gilt: $a\mid b\Leftrightarrow k\cdot a\mid k\cdot \ b$.
4. Gilt $a\mid b$ und $c\mid d$, so gilt auch $a\cdot c\mid b\cdot d$.
5. Gilt $a\mid b$ und $b\mid c$, so gilt auch $a\mid c$.
6. Gilt $a\mid b$ und $a\mid c$, so gilt für alle $x,y\in \mathbb {Z}$ die Relation $a\mid b\cdot x+c\cdot y$.

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 $a\,$ ist ein echter Teiler von $b\,$, falls $a\neq 1$ und $a\neq b$ gilt.

Primzahlen

Wenn man jemanden auf der Straße fragt, was Primzahlen sind, erhält man viele verschiedene Antworten, insbesondere die Frage, ob $1$ 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 $1$ 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 $p>1$ für die gilt: Falls $p$ eine Zahl $a\cdot b$ teilt, so teilt $p$ auch einen der Faktoren $a$ oder $b$. → Wikipedia:Primzahl

Beispiele

• $21$ ist keine Primzahl, denn: $21$ teilt $15\cdot 35$, aber $21$ teilt weder $15$ noch $35$.
• $2$ ist eine Primzahl, denn: Seien $a$ und $b$ beliebige Zahlen, so dass $2$ ein Teiler des Produktes $a\cdot b$ ist. Dann gibt es eine Zahl $k$ mit $2k=a\cdot b$.

Es ist zu zeigen, dass $2$ ein Teiler von $a$ oder $b$ ist. Ist $a$ durch $2$ teilbar, so sind wir fertig. Ist dagegen $a$ nicht durch $2$ teilbar, so gibt es eine Zahl $n$ mit $a=2\cdot n+1$. Zusammen ergibt sich: $2k=(2n+1)\cdot b=2n\cdot b+b$ und damit $2k-2n\cdot b=2(k-n\cdot b)=b$. Somit ist $2$ ein Teiler von $b$. → 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 $p>1$, 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 $n$ Primzahl. Angenommen, es gäbe einen Teiler $a\neq 1,n$ von $n$, dann gilt $a\cdot b=n$. Da $n$ Primzahl ist, teilt $n$ mindestens eine der beiden Zahlen $a$ und $b$. Sicherlich teilt $n$ nicht $a$, da $a\neq n$ und $a$ ein Teiler von $n$ ist. Also gilt $n\ |\ b$, das heißt, es existiert eine Zahl $c$ mit $n\cdot c=b$. Setzen wir diese Formel für $b$ in $a\cdot b=n$ ein, so erhalten wir $a\cdot n\cdot c=n$ und damit $a\cdot c=1$ woraus $a=1$ folgt. Dies ist aber ein Widerspruch zur Annahme, dass $a\neq 1$ 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

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 $n>1$, der größer als $1$ ist, ist eine Primzahl.

Beweis

$n$ besitzt auf alle Fälle einen Teiler, der größer als $1$ ist, nämlich $n$ selbst, somit auch einen kleinsten solchen. Sei $p$ der kleinste Teiler von $n$, der größer als $1$ ist. Wir behaupten, $p$ ist eine Primzahl. Angenommen, $p$ sei keine Primzahl, dann gibt es einen echten Teiler $a$ von $p$. Dieser ist aber auch ein Teiler von $n$ und größer als $1$, was ein Widerspruch zur Voraussetzung, dass $p$ 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 $p_{1},...,p_{k}$ so betrachtet man die Zahl $n=p_{1}\cdot p_{2}\cdot ...\cdot p_{k-1}\cdot p_{k}+1$. Da diese beim Teilen durch $p_{i}$ den Rest $1$ lässt, ist sie durch keine der Zahlen $p_{1},...,p_{k}$ teilbar. Dies bedeutet aber, dass der kleinste Teiler von $n$, welcher nach dem Lemma eine Primzahl ist, eine weitere noch nicht aufgeführte Primzahl sein muss.

Beispiel

Nehmen wir einmal an, $2,3$ und $5$ seien die einzigen Primzahlen, dann erhalten wir nach dem Beweis des Satzes, die Zahl $n=2\cdot 3\cdot 5+1=31$. Der kleinste Teiler von $31$ ist $31$ selbst und wir haben eine neue Primzahl gefunden.

Achtung: Die Zahl $n$ aus dem Beweis muss selbst nicht unbedingt eine Primzahl sein. Nimmt man etwa an, $3$ und $5$ seien die einzigen Primzahlen, so ist $n=3\cdot 5+1=16$ und $16$ ist keine Primzahl. Wohl aber $2$, ihr kleinster Teiler.

Fundamentalsatz der Arithmetik

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 $n$ 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 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 $1$ lässt sich als leeres Produkt und jede Primzahl als Produkt mit einem Faktor darstellen. Sei nun $n>3$ keine Primzahl und für alle Zahlen kleiner als $n$ bereits bewiesen, dass eine Darstellung existiert. Dann hat $n$ einen echten Teiler $a$. Damit lässt sich $n$ schreiben als $a\cdot b$. Da aber $a$ und $b$ kleiner als $n$ 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 $n$.

"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 $n$ nennen wollen. Wir können davon ausgehen, dass $n>1$ gilt, da $1$ nur eine Darstellung besitzt. Nach dem Lemma zum Satz von Euklid besitzt $n$ einen kleinsten Teiler $p$, der größer als $1$ ist. Dieser Teiler ist eine Primzahl. Betrachten wir die Zahl $m:=n/p$. Diese Zahl ist kleiner als $n$ und hat deshalb nach Voraussetzung eine eindeutige Darstellung

$m=\prod _{i=1}^{k}p_{i}$.

Damit ist

$n=p\cdot \prod _{i=1}^{k}p_{i}$

eine Darstellung von $n$. Da $n$ nach Annahme nicht eindeutig dargestellt werden kann, gibt es eine weitere Darstellung, die ebenfalls einen kleinsten Teiler $q$ besitzt. $q$ muss jedoch ungleich $p$ sein, denn sonst wäre die weitere Zerlegung durch die eindeutige Darstellung von $m$ bereits vorgegeben und somit gleich der ersten Zerlegung. Wie oben ist auch $n/q$ eine eindeutige Darstellung, bestehend aus den Faktoren $q_{i}$.

$n=q\cdot \prod _{i=1}^{l}q_{i}$.

Da $p$ der kleinste Teiler von $n$ ist, müssen $q$ und alle $q_{i}$ größer als $p$ sein. Betrachten wir jetzt die Zahl

$r=n-p\cdot \prod _{i=1}^{l}q_{i}$.

Da $p$ ein Teiler von $n$ ist, ist auch $r$ durch $p$ teilbar. Durch Einsetzen der $q$-Zerlegung für $n$ und Ausklammern ergibt sich:

$r=(q-p)\cdot \prod _{i=1}^{l}q_{i}$.

Da $r<n$, existiert dafür ebenfalls eine eindeutige Zerlegung. Da $r$ durch $p$ teilbar ist, ist $p$ einer der Faktoren. $p$ ist jedoch nicht im Produkt der $q_{i}$ enthalten, also muss gelten $p\ |\ (q-p)$ und damit $p\ |\ q$. Da $p$ und $q$ Primzahlen sind muss also gelten $p=q$. Das ist aber ein Widerspruch zu $q>p$.

Primfaktorzerlegung

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.

$n=\prod _{i=1}^{k}p_{i}^{a_{i}}=\prod _{p\in \mathbb {P} }p^{\nu _{p}}$

Bei der ersten Schreibweise sind die p_i 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 $\nu _{p}$ sind aber für fast alle Primzahlen gleich $0$, somit $p^{\nu _{p}}=p^{0}=1$. Der Faktor $1$ ändert aber an einem Produkt nichts. Für die Praxis heißt dies, dass nur die Primzahlen betrachtet werden, für die $\nu _{p}\neq 0$ ist.

Beispiel

$118776=2^{3}\cdot 3\cdot 7^{2}\cdot 101$

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 $\mathbb {Q}$ ausdehnen lässt. Hierzu benötigt man für die negativen Zahlen noch den Faktor $-1$ und zudem lässt man auch negative Exponenten $\nu _{p}$ zu.

Beispiel

$-25/2541=-1\cdot 3^{-1}\cdot 5^{2}\cdot 7^{-1}\cdot 11^{-2}$

→  nächstes Kapitel

→  Zurück zum Inhaltsverzeichnis "Zahlentheorie"

→  Zur Inhaltsübersicht