% spell checker language
\selectlanguage{german}

\chapter{Teilbarkeit}

\section{Wohin geht die Reise… ?}

In den letzten Vorlesungen ist hoffentlich klar geworden, dass der Begriff
„Minimalpolynom“ schrecklich wichtig ist.  Wir haben aber noch nie darüber
gesprochen, wie man ein Minimalpolynom überhaupt findet.

\begin{problem}
  Gegeben eine Körpererweiterung $L/K$, ein Element $a ∈ L$ und ein normiertes
  Polynom $f∈ K[x]$ mit $f(a)=0$.  Wie kann ich entscheiden, ob $f$ das
  Minimalpolynom ist oder nicht?
\end{problem}

Um solche Probleme anzugehen, untersuchen wir Polynomdivision und
Teilbarkeitsfragen in (Polynom-)Ringen.  Hier kommt ein erster Hinweis, in
welche Richtung die Argumentation geht.

\begin{beobachtung}
  Sei $L/K$ eine Körpererweiterung, sei $a ∈ L$ ein Element, das algebraisch
  über $K$ ist und sei $f∈ K[x]$ das Minimalpolynom von $a$.  Wenn jetzt $g(x) ∈
  K[x]$ irgendein anderes Polynom ist, dann haben wir in der Schule gelernt,
  dass wir das Polynom $g$ mit Rest durch $f$ teilen können.  Am Ende schreibt
  man
  \begin{equation*}
    g(x) = q(x)·f(x)+ r(x),
  \end{equation*}
  wobei $q, r ∈ K[x]$ sind und $\deg r < \deg f$ ist.  Angenommen $g$ hat $a$
  als Nullstelle.  Dann gilt:
  \begin{equation*}
    0 = \underbrace{g(a)}_{=0}=\underbrace{q(a)· f(a)}_{=0}-r(a).
  \end{equation*}
  Also hat $r$ auch $a$ als Nullstelle.  Weil $f$ aber das Minimalpolynom ist,
  und $\deg r < \deg f$, ist muss wohl $r\equiv 0$ gelten.  Als Konsequenz
  lernen wir: Jedes Polynom, das $a$ als Nullstelle hat, ist ein Vielfaches des
  Minimalpolynoms.  Umgekehrt gilt auch: wenn ein Polynom $g$ gegeben ist, das
  $a$ als Nullstelle hat, dann finden wir das Minimalpolynom unter den Teilern
  von $g$.
\end{beobachtung}


\section{Polynome mit Koeffizienten in Ringen}

Wieder müssen wir erst etwas Sprache einführen, bevor wir echte Mathematik
machen können.  Wir hatten in Definition~\vref{def:3-0-2} den „Ring $K[x]$ der
Polynome mit Koeffizienten im Körper $K$“ eingeführt.  Das geht auch mit Ringen
statt Körpern.

\begin{definition}[Polynomring]\label{def:3-0-2r}%
  Es sei $R$ ein kommutativer Ring.  Dann bezeichne mit $R[x]$ den Ring der
  Polynome mit Variable $x$ und Koeffizienten aus $R$.\index{Polynomring!mit
  Koeffizienten aus Ring} Ebenso bezeichnen wir mit $R[x_1, …, x_n]$ den Ring
  der Polynome mit Variablen $x_1, …, x_n$ und Koeffizienten aus $R$.
\end{definition}

\begin{bsp}
  Betrachte den Ring $R = ℤ$.  Dann ist $3·x²-5·x+17 ∈ ℤ[x]$ und $4x²+3xy+y⁷ ∈
  ℤ[x,y]$.
\end{bsp}

\begin{beobachtung}
  Es gelten einige offensichtliche Gleichheiten wie
  \begin{align*}
    R[x,y] &= R[y,x] \\
    R[x,y] &= \bigl(R[x] \bigr)[y],
  \end{align*}
  die wir nicht formal beweisen werden.
\end{beobachtung}

Der Grad von Polynomen ist definiert wie üblich: Das Polynom
$3xy+y+4x ∈ ℤ[x,y] $ hat beispielsweise den Grad $2$.  In Integritätsringen
verhält sich der Grad gut.

\begin{satz}\label{Satz_Polynom_Grad}%
  Sei $R$ ein kommutativer Integritätsring.  Dann gilt für alle
  Polynome\footnote{Das Nullpolynom hat per Definition den Grad $-∞$.  Wir
  verwenden die Konvention $- ∞ + (- ∞) = -∞$ und $-∞ + n = - ∞$ für alle $n ≥
  0$.} $p$ und $q ∈ R[x]$:
  \begin{equation*}
    \deg (p·q) = (\deg p)+(\deg q).
  \end{equation*}
  Insbesondere ist $R[x]$ wieder ein Integritätsring.
\end{satz}
\begin{proof}
  Wir können ohne Beschränkung der Allgemeinheit annehmen, dass $p,q ≠ 0$.  Sei
  $n := \deg p$ und $m := \deg q$.  Dann finden wir Elemente $r_•$ und $s_•$ aus
  $R$ mit $r_n ≠ 0$ und $s_m≠ 0$, sodass wir schreiben können:
  \begin{align*}
    p(x) & = r_0 + r_1·x + \dots + r_n·x^n \\
    q(x) & = s_0+ s_1· x + \dots + s_m· x^m.
  \end{align*}
  Dann ist weiter
  \begin{equation*}
    p(x)·q(x) = r_0·s_0 + (r_1·s_0 + r_0·s_1)·x + \dots + r_ns_m·x^{n+m}.
  \end{equation*}
  Weil $R$ ein Integritätsring ist, ist $r_n·s_m ≠ 0$, und also ist
  $\deg (p·q) =n+m$.
\end{proof}

\begin{kor}
  Ist $R$ ein kommutativer Integritätsring und ist $n ∈ ℕ$, dann ist auch der
  Polynomring $R[x_1, …, x_n]$ ein kommutativer Integritätsring.  Für die Gruppe
  der Einheiten gilt
  \begin{equation*}
    R[x_1, …, x_n]^* = R^*,
  \end{equation*}
  wobei wir die Ringelemente aus $R^* ⊆ R$ als konstante Polynome
  auffassen.
\end{kor}
\begin{proof}
  Die erste Aussage folgt mit Induktion aus Satz~\vref{Satz_Polynom_Grad}.  Die
  zweite Aussage folgt ebenfalls mit Induktion, sobald wir zeigen, dass $R[x]^*
  = R^*$ ist.  Sei also $p ∈ R[x]^*$.  Das bedeutet per Definition: Es existiert
  ein Polynom $q$ mit $p·q = 1$.  Dann folgt aber
  \[
    \deg p ≤ \deg p + \deg q = \deg (p·q) = \deg 1 = 0.
  \]
  Also ist $\deg p = 0$ und somit ist $p$ konstant.
\end{proof}

\begin{bsp}
  Es ist $ℤ[x_1, x_2]^* = ± 1$.
\end{bsp}

\begin{bsp}
  Sei $K$ ein Körper.  Dann ist $K[x_1, …, x_n]^* = K^* = K∖\{0\}$.
\end{bsp}


\section{Teilbarkeit in Ringen}

In der (Grund-)Schule haben wir den Begriff „Teiler“ kennengelernt.  In
allgemeinen Ringen geht das nicht anders.

\begin{defn}[Teiler]
  Es sei $R$ ein kommutativer Ring und es sei $r$, $s ∈ R$.  Man nennt $r$ einen
  \emph{Teiler von $s$}\index{Teiler}, wenn es $q ∈ R$ gibt, sodass $r·q = s$
  ist.  Wir schreiben dann $r|s$.
\end{defn}

\begin{bsp}
  Es gilt $2|16$ in $ℤ$.  Es gilt $(x-1)|(x²-1)$ in $ℝ[x]$.
\end{bsp}

\begin{prop}[Offensichtliche Rechenregeln für Teiler]\label{Satz_Rechenregeln_Teiler}
  Es sei $R$ ein kommutativer Ring und $r$, $s$, $t$, $s_1$, $s_2$, $u$ und $v$
  seien Elemente.  Dann gilt Folgendes.
  \begin{itemize}
  \item Es gilt $r|r$.
    
  \item Aus $r|s$ und $s|t$ folgt $r|t$.
    
  \item Aus $r|s_1$ und $r|s_2$ folgt $r|(s_1+s_2)$.
    
  \item Aus $r|s_1$ und $r|(s_1+s_2)$ folgt $r|s_2$.
    
  \item Aus $r|s$ und $u|v$ folgt $(r·u)|(s·v)$.
  \end{itemize}
\end{prop}
\begin{proof}
  Keine Lust.  Folgt alles direkt aus der Definition.
\end{proof}

Wenn wir in der Schule Teilbarkeitsüberlegungen in $ℤ$ angestellt hatten, war
das Vorzeichnen meist nicht wichtig.  Die folgende Definition formalisiert in
bombastischer Sprache die Phrase „unterscheidet sich nur um ein Vorzeichnen“.

\begin{satzdef}[Zueinander assoziierte Elemente]
  Es sei $R$ ein kommutativer Integritätsring und es seien $r$, $s$ zwei
  Elemente von $R$.  Dann sind folgende Aussagen äquivalent.
  \begin{enumerate}
  \item\label{Satz_assoziiert_1} Es gilt gleichzeitig $r|s$ und $s|r$.
    
  \item\label{Satz_assoziiert_2} Es existiert ein Element $ε ∈ R^*$, sodass
    $ε·r=s$ ist.
  \end{enumerate}
  Sind die Bedingungen erfüllt, nennt man $r$ und $s$ \emph{zueinander
    assoziiert}\index{assoziierte Ringelemente} und schreibt $r \sim s$.
\end{satzdef}
\begin{proof}
  Wir beweisen die Richtung \ref{Satz_assoziiert_2}$⇒$\ref{Satz_assoziiert_1}.
  Wegen $ε· r = s$ gilt $r|s$.  Multiplikation mit $ε^{-1}$ liefert $r =
  ε^{-1}·s$, also gilt $s|r$.  Wir beweisen als Nächstes die Richtung
  \ref{Satz_assoziiert_1}$⇒$\ref{Satz_assoziiert_2}. Nach Annahme existieren
  $u,v∈ R$ mit
  \begin{equation*}
    u· r=s \quad\text{und}\quad v· s=r.
  \end{equation*}
  Also ist
  \begin{equation*}
    v·(u· r) = v·s \:⇒\: v· u· r= r \:⇒\: (v· u-1)·r = 0,
  \end{equation*}
  und weil $R$ ein Integritätsring ist, folgt $v· u =1$, also sind $v$ und
  $u$ Einheiten in $R$.
\end{proof}

Wie in $ℤ$ gibt es in beliebigen Integritätsringen echte und nicht-echte
Teiler.

\begin{definition}[Echte Teiler, irreduzible Elemente]
  Es sei $R$ ein kommutativer Integritätsring und $r$, $s ∈ R$ seien zwei
  Elemente.  Dann ist $r$ ein \emph{echter Teiler von $s$}\index{echter
    Teiler}\index{Teiler!echter}, wenn alle der folgenden Bedingungen gelten.
  \begin{itemize}
  \item Es gilt $r|s$.
    
  \item Das Element $r$ ist keine Einheit im Ring $R$.
    
  \item Die Elemente $r$ und $s$ sind nicht zueinander assoziiert.
  \end{itemize}
  Ein Element $r$ aus einem Integritätsring heißt
  \emph{irreduzibel}\index{irreduzible Ringelemente}, wenn $r$ nicht Null ist,
  keine Einheit ist und keine echten Teiler hat.
\end{definition}

\begin{notation}
  Wenn $r$ ein echter Teiler von $s$ ist, schreibt man $r||s$.
\end{notation}

\begin{bsp}[Irreduzible Elemente von $ℤ$]\label{bsp:iZ}
  Die irreduziblen Elemente von $ℤ$ sind die Elemente der Form $± p$, wobei
  $p$ eine Primzahl ist.
\end{bsp}

\begin{warnung}
  Beispiel~\ref{bsp:iZ} ist ein bisschen gefährlich.  Wir werden später für
  beliebige Ringe auch noch einen Begriff von „Primelement“ definieren.
\end{warnung}


\section{Zerlegbarkeit von Elementen}

In der Schule wurde die Primfaktorzerlegung von ganzen Zahlen hoffentlich
ausführlich diskutiert: Jede ganze Zahl $m ∈ ℤ$ lässt sich als Produkt von
irreduziblen Elementen (=sogenannte „Primzahlen“) schreiben,
\begin{equation*}
  m= (± p_1)·(± p_2)⋯(± p_n),
\end{equation*}
wobei das Produkt bis auf die Reihenfolge der Faktoren und die Vorzeichen
eindeutig festgelegt ist.  So etwas hätten wir gern auch für beliebige Ringe!

\begin{warning}\label{war:nufd}%
  Zu früh gefreut.  Geht nicht.  Ich behaupte, dass die folgende Menge von
  komplexen Zahlen,
  \[
    R := \{ a+b·\sqrt{5}i ∈ ℂ \:|\: a,b ∈ ℤ\},
  \]
  einen Unterring des Körpers $ℂ$ bildet; dieser wird in der Literatur oft mit
  $ℤ[\sqrt{-5}]$ bezeichnet.  Ich behaupte auch, dass die Elemente
  \[
    3, \quad 2+\sqrt{5}i \quad\text{und}\quad 2-\sqrt{5}i
  \]
  irreduzibel und paarweise nicht zueinander assoziiert sind.  Es gilt aber
  schrecklicherweise
  \[
    3· 3 = 9 = (2+\sqrt{5}i)·(2-\sqrt{5}i).
  \]
  Das Element 9 aus $R$ hat also zwei sehr unterschiedliche Darstellungen als
  Produkt von irreduziblen Elementen.
\end{warning}

\subsection{Existenz von Zerlegungen}

\sideremark{Vorlesung 5}Wir kümmern uns zuerst um die Frage, wann es überhaupt
eine Zerlegung in irreduzible Elemente gibt.  Dazu sind folgende Definitionen
relevant.

\begin{defn}[Teilerkette für Elemente]\label{def:TK}%
  Es sei $R$ ein kommutativer Ring.  Eine \emph{Teilerkette}\index{Teilerkette}
  in $R$ ist eine Folge von Elementen $(r_n)_{n∈ℕ}$ aus $R$, sodass für alle $n
  ∈ ℕ$ gilt: $r_{n+1}|r_n$.
\end{defn}

\begin{defn}[Teilerkettensatz für Elemente]\label{def:TKSE}%
  Es sei $R$ ein kommutativer Ring.  Man sagt \emph{in $R$ gilt der
  Teilerkettensatz für Elemente}\index{Teilerkettensatz!für Elemente}, wenn für
  jede Teilerkette $(r_n)_{n ∈ ℕ}$ ein $n_0∈ℕ$ existiert, sodass für alle $k ≥
  n_0$ gilt: Die Elemente $r_{k+1}$ und $r_k$ sind assoziiert.
\end{defn}

\begin{rem}
  Die Forderung „für alle $k ≥ n_0$ gilt $r_{k+1} \sim r_k$ sind assoziiert“
  lässt sich auch so ausdrücken: Es gibt nur endlich viele $n ∈ ℕ$, sodass
  $r_{n+1}$ ein echter Teiler von $r_n$ ist.
\end{rem}

\begin{bsp}
  In $ℤ$ gilt der Teilerkettensatz, denn wenn $r_n$ eine Teilerkette ist, dann
  gilt $|r_1| ≥ |r_2| ≥ ⋯$ und wenn $r_{n+1}$ ein echter Teiler von $r_n$ ist,
  dann ist $|r_n| > |r_{n+1}|$.
\end{bsp}

\begin{bsp}
  Analog zur Situation in $ℤ$ kann man im Polynomring $K[x]$ über einem Körper
  $K$ schließen, dass der Teilerkettensatz gilt.  Dazu betrachte man den Grad
  von Polynomen anstelle des Betrages.
\end{bsp}

\begin{warnung}
  In der Hausaufgabe werden wir sehen: es gibt Integritätsringe, in denen der
  Teilerkettensatz nicht gilt.
\end{warnung}

Der folgende Satz ist wirklich klassisch, er geht auf
Euklid\footnote{\href{https://de.wikipedia.org/wiki/Euklid}{Euklid von
Alexandria} war ein griechischer Mathematiker, der wahrscheinlich im
3.~Jahrhundert v.~Chr.~in Alexandria gelebt hat.} zurück.  Der Beweis, den wir
hier vorstellen, ist genial-elegant-modern und von Emmy
Noether\footnote{\href{https://de.wikipedia.org/wiki/Emmy_Noether}{Amalie Emmy
Noether} (Emmy war der Rufname; * 23.~März 1882 in Erlangen; † 14.~April 1935 in
Bryn Mawr, Pennsylvania) war eine deutsche Mathematikerin, die grundlegende
Beiträge zur abstrakten Algebra und zur theoretischen Physik lieferte.
Insbesondere hat Noether die Theorie der Ringe, Körper und Algebren
revolutioniert.  Das nach ihr benannte Noether-Theorem gibt die Verbindung
zwischen Symmetrien von physikalischen Naturgesetzen und Erhaltungsgrößen an.}.
Die Beweismethode ist heute als „Noethersche Induktion“ bekannt.

\begin{satz}\label{satz:tksgz}
  Es sei $R$ ein kommutativer Ring in dem der Teilerkettensatz für Elemente
  gilt.  Weiter sei $r ∈ R$ ein Element, welches weder 0 noch eine Einheit ist.
  Dann kann man $r$ als Produkt von endlich vielen irreduziblen Elementen
  $p_i ∈ R$ schreiben.
\end{satz}
\begin{proof}
  \video{5-1}
\end{proof}


\subsection{Eindeutigkeit von Zerlegungen}

Nach dem Kriterium für die Existenz einer Zerlegung kommen wir jetzt zur Frage
der Eindeutigkeit.  Die Primfaktorzerlegung von ganzen Zahlen ist eindeutig bis
auf Vorzeichen (=Multiplikation mit Einheiten) und Reihenfolge.  Zwei
Darstellungen, die sich nur in Reihenfolge und Einheiten unterscheiden, nenne
wir „äquivalent“.

\begin{defn}[Äquivalente Zerlegungen]
  Es sei $R$ ein kommutativer Integritätsring, es sei $r ∈ R$ ein Element und es
  seien
  \[
    r = p_1 ⋯ p_n = q_1 ⋯ q_m
  \]
  zwei Darstellungen von $r$ als Produkt von irreduziblen Elementen.  Die
  Darstellungen heißen \emph{äquivalent}\index{äquivalente Darstellungen}, wenn
  gilt $n = m$ und wenn es eine Permutation $σ ∈ S_n$ gibt, sodass für alle
  Indizes gilt $p_i \sim q_{σ(i)}$.
\end{defn}

\begin{bsp}
  Betrachte $R = ℤ$.  Dann sind $6 = 2·3 = (-3)·(-2)$ zwei äquivalente
  Darstellungen der Zahl $6$.
\end{bsp}

Wir wollen natürlich ein Kriterium dafür finden, dass für alle Elemente eines
Ringes je zwei Darstellungen äquivalent sind.  Die folgende Definition ist dabei
wichtig.

\begin{definition}[Primelemente eines Ringes]
  Es sei $R$ ein kommutativer Integritätsring.  Ein Element $p ∈ R$ heißt
  \emph{prim}\index{Primelement eines Ringes}, wenn $p$ keine Einheit ist,
  $p \neq 0$ gilt und wenn für alle $a,b ∈ R$ mit $p|(a·b)$ schon folgt, dass
  $p|a$ oder $p|b$ gilt.
\end{definition}

\begin{satz}[Regeln im Umgang mit Primelementen]
  Es sei $R$ ein kommutativer Integritätsring und es sei $p ∈ R$.  Dann gilt
  Folgendes.
  \begin{enumerate}
  \item\label{Satz_Prim_1} $p$ ist prim $⇒$ $p$ ist irreduzibel.
  \item\label{Satz_Prim_2} $p$ ist prim und $p \sim s$ $⇒$ $s$ ist prim.
  \item\label{Satz_Prim_3} $p$ und $q$ sind prim und $p|q$ $⇒$
    $p \sim q$.
  \item\label{Satz_Prim_4} $p$ ist prim und $p|(a_1 ⋯ a_n)$
    $⇒$ es existiert ein $i$ mit $p|a_i$.
  \end{enumerate}
\end{satz}
\begin{proof}
  Die meisten Punkte sind klar, es ist nur \ref{Satz_Prim_1} zu zeigen.  Sei $p$
  also prim.  Aus $p = a· b$ folgt dann $p|a$ oder $p|b$, also $p \sim a$
  oder $p \sim b$, das heißt $p$ ist irreduzibel.
\end{proof}

\begin{bsp}[Primzahlen]\label{satz:Zpirr}
  In $ℤ$ ist ein Element genau dann prim, wenn es irreduzibel ist.  Also: die
  Menge der Primelemente sind genau die Primzahlen.  Der Beweis ist erstaunlich
  kompliziert.  Wir argumentieren mit Widerspruch und nehmen an, nicht jedes
  irreduzible Element in $ℤ$ sei prim.  Die irreduziblen Elemente in $ℤ$ sind
  aber gerade $±$ Primzahl.  Also nehmen wir an, dass es eine kleinste
  (positive) Primzahl $p ∈ ℤ$ mit der Eigenschaft gibt, dass es zwei Zahlen
  $a,b ∈ ℤ$ gibt mit $p|(a· b)$ und $p \nmid a$ und $p \nmid
  b$.  Division mit Rest liefert:
  \begin{align*}
    a &= q_1· p+a_1, & 1&<a_1<p,\\
    b &= q_2· p+b_1, & 1&<b_1<p.
  \end{align*}
  Dann gilt $p \nmid a_1$ und $p \nmid b_1$, aber
  \begin{equation*}
    a· b = p(q_1· q_2· p+ q_1· b_1+ q_2· a_1)+a_1· b_1,
  \end{equation*}
  also $p|(a_1· b_1)$.  Betrachte jetzt die kleinste natürliche Zahl, die als
  Produkt $a·b$ geschrieben werden kann, mit $p|(a· b)$ aber $p \nmid a$ und $p
  \nmid b$.  Nach der Untersuchung oben gilt: $1<a<p$ und $1<b<p$ also $1 < a· b
  < p²$.  Sei $h=\frac{a· b}{p}∈ℤ$, also $p· h = a· b$.  Dann gilt $1<h$, weil
  $p$ irreduzibel ist und $h<p$, weil $a· b <p²$.  Sei nun $p^\prime$ ein
  positiver irreduzibler Faktor von $h$ (möglicherweise sogar $h$ selbst, wenn
  $h$ irreduzibel ist).  Dann gilt natürlich auch $p^\prime< p$.  Nach Wahl von
  $p$ (kleinste Zahl, die irreduzibel ist und nicht prim) ist $p^\prime$ prim.
  Da $p^\prime|h$, $h|(a· b)$ folgt $p^\prime|(a· b)$ und daraus folgt
  $p^\prime|a$ oder $p^\prime|b$.
  
  Ohne Einschränkung nehmen wir an, dass $p^\prime|a$ gilt.  Dann ist
  $a=p^\prime· a^\prime$ und $h=p^\prime· h^\prime$ und somit
  \begin{equation*}
    p^\prime· h^\prime· p=p^\prime· a^\prime· b\quad⇒\quad h^\prime· p= a^\prime·b.
  \end{equation*}
  Weil $a^\prime· b< a· b$ ist, folgt $p|a^\prime$ oder $p|b$ nach Wahl
  von $a· b$.  Es folgt $p|a$ oder $p|b$, Widerspruch!
\end{bsp}

\begin{bsp}
  In dem Ring $R = ℤ[\sqrt{-5}] ⊂ ℂ$ ist nicht jedes irreduzible
  Element prim.  Das Element $2+\sqrt{-5}$ ist irreduzibel, teilt $3· 3$,
  aber nicht $3$.  Also ist $2+\sqrt{-5}$ nicht prim.  Wir werden später sehen,
  dass dies exakt der Grund ist, warum die Zerlegung in irreduzible Elemente
  nicht eindeutig ist
\end{bsp}

\begin{satz}[Zentraler Satz über die (eindeutige) Existenz von Zerlegungen]\label{Satz_Zerlegung}
  Sei $R$ ein kommutativer Integritätsring.  Dann sind die folgenden Aussagen
  äquivalent.
  \begin{enumerate}
  \item\label{Satz_Zerlegungen_1} Jedes Element $r∈ R$ mit $r≠ 0$ und
    $r\not ∈ R^*$ hat eine Darstellung als Produkt von endlich vielen
    irreduziblen Elementen von $R$ \emph{und} je zwei Darstellungen von $r$ sind
    äquivalent.
    
  \item\label{Satz_Zerlegungen_2} In $R$ gilt der Teilerkettensatz für Elemente
    und jedes irreduzible Element von $R$ ist prim.
  \end{enumerate}
\end{satz}
\begin{proof}

  ---

  \begin{itemize}
  \item Richtung \ref{Satz_Zerlegungen_1}$⇒$\ref{Satz_Zerlegungen_2}:
    \video{5-2}

  \item Richtung \ref{Satz_Zerlegungen_2}$⇒$\ref{Satz_Zerlegungen_1}:
    \video{5-3} \qedhere
  \end{itemize}
\end{proof}

\begin{definition}[Faktorieller Ring]
  Ein kommutativer Integritätsring heißt \emph{faktoriell}\index{faktoriell},
  wenn er die Bedingungen von Satz~\ref{Satz_Zerlegung} erfüllt.
\end{definition}

\begin{rem}
  In der Literatur findet man statt „faktoriell“ manchmal auch die Adjektive
  \emph{ZPE}\index{ZPE} (= \textbf{Z}erlegung in \textbf{P}rimelemente ist
  \textbf{E}indeutig) oder \emph{UFD}\index{UFD} (= \textbf{U}nique
  \textbf{F}actorization \textbf{D}omain).
\end{rem}

\begin{bsp}
  Der Ring $ℤ$ ist faktoriell, denn wir haben gezeigt, dass jedes irreduzible
  Element prim ist.
\end{bsp}

\begin{bsp}
  Körper sind trivialerweise faktoriell, denn $K ∖ \{0\} = K^*$.
\end{bsp}

Weitere Beispiele lassen sich mit dem folgenden Satz finden.
 
\begin{satz}[Satz von Gauß\footnote{\href{https://de.wikipedia.org/wiki/Carl_Friedrich_Gauss}{Johann Carl Friedrich Gauß} (* 30.~April 1777 in Braunschweig; † 23.~Februar 1855 in Göttingen) war ein deutscher Mathematiker, Statistiker, Astronom, Geodät und Physiker.}]\label{Satz_Satz_von_Gauss}
  Es sei $R$ ein faktorieller Ring.  Dann ist auch der Polynomring
  $R[x_1, …, x_n]$ faktoriell.
\end{satz}

\begin{bsp}
  Die Ringe $ℤ[x_1, …, x_n]$ oder $ℚ[x_1, …, x_n]$ sind faktoriell.
\end{bsp}

Der Beweis des Satzes von Gauß verwendet folgendes Lemma.\sideremark{Vorlesung
  6}

\begin{lem}\label{Lemma_Hilfslemma}%
  Es sei $R$ ein kommutativer Integritätsring.  Ist $p ∈ R$ ein Primelement,
  dann ist $p$ auch im Polynomring $R[x]$ prim.
\end{lem}
\begin{proof}
  \video{6-1}
\end{proof}

\begin{proof}[Beweis von Satz~\ref{Satz_Satz_von_Gauss}]
  \video{6-2}
\end{proof}


\section{Primfaktorzerlegung}

Wenn $R$ ein faktorieller Ring ist, dann haben wir schon gesehen, dass ich jedes
Element auf „nahezu eindeutige Weise“ als Produkt von Primelementen schreiben
kann.  So ist die Zahl $6 ∈ ℤ$ als $6 = 3·2$ oder $6 = (-3)·(-2)$ darstellbar.
Natürlich würde aber niemand freiwillig negative Zahlen verwenden, denn wir
finden positive Zahlen wesentlich angenehmer als negative.  Eine derartige
Konvention kann man auch in beliebigen Ringen verwenden.

Gegeben ein Ring $R$, dann ist die Relation „äquivalent“ eine Äquivalenzrelation
auf der Menge der Primelemente und zerlegt diese Menge deshalb in
Äquivalenzklassen.  Um die Produktdarstellung noch etwas einfacher zu machen,
müssen wir aus jeder Äquivalenzklasse einen Vertreter auswählen.  Dann sind wir
in der folgenden Situation.

\begin{situation}\label{sit:5-5-1}%
  Es sei $R$ ein faktorieller Ring und $(p_i)_{i ∈ I}$ sei ein
  Repräsentantensystem von zueinander assoziierten Primelementen (das bedeutet:
  für jedes Primelement $p ∈ R$ gibt es genau einen Index $i$, sodass $p \sim
  p_i$ ist).
\end{situation}

Ein „Repräsentantensystem von zueinander assoziierten Primelementen“ existiert
wegen des Auswahlaxioms natürlich immer, aber manchmal gibt es besonders
einleuchtende Wahlen.

\begin{bsp}
  Es sei $R = ℤ$ und $(p_i)_{i ∈ ℕ}$ die Menge der \emph{positiven} Primzahlen.
\end{bsp}

\begin{bsp}
  Es sei $K$ ein Körper, es sei $R = K[x]$ und es seien $(p_i)_{i ∈ I}$ die
  Menge der \emph{normierten} irreduziblen Polynome.
\end{bsp}

\begin{satzdef}[Primfaktorzerlegung]\label{Satz_Primfaktorzerlegung}
  In Situation~\ref{sit:5-5-1} besitzt jedes Element $r∈ R∖ \{0\}$ eine (bis auf
  Reihenfolge) eindeutige Faktorisierung
  \begin{equation*}
    r = ε·\prod_{i∈I} (p_i)^{ν_i}
  \end{equation*}
  wobei $ε ∈ R^*$ und $ν_i ∈ ℕ$ sind; außerdem sind alle bis auf endlich viele
  Exponenten gleich $0$.  Diese Darstellung heißt \emph{normierte
    Primfaktorzerlegung}\index{normierte
    Primfaktorzerlegung}\index{Primfaktorzerlegung!normiert} von $r$ zum
  Repräsentantensystem $(p_i)_{i ∈ I}$.
\end{satzdef}
\begin{proof}
  Hier ist nicht viel zu beweisen.  Ist $r ∈ R^*$, so wähle $ε = r$ und setzt
  $ν_i = 0$ für alle $i$.  Ansonsten zerlege $r$ in irreduzible Faktoren,
  $r = p'_{i_1}⋯p'_{i_n}$.  Jeder Faktor $p'_{i_j}$ ist zu einem der $p_{i_j}$
  assoziiert, also gib es $ε_j ∈ R^*$, sodass $p'_{i_j} = ε_j·p_{i_j}$ ist.
  Setze $ε = \prod_{j=1}^n ε_j$ und fasse die Faktoren $p_•$, die mehrfach
  auftauchen, zusammen.  Die Eindeutigkeit ist klar.
\end{proof}

An einer normierten Primfaktorzerlegung kann man Teilbarkeitseigenschaften
sofort ablesen.

\begin{beobachtung}
  In Situation~\ref{sit:5-5-1} seien
  \[
    r = ε_r·\prod (p_i)^{ν_i} \quad\text{und}\quad
    s = ε_s·\prod (p_i)^{μ_i}
  \]
  zwei Elemente zusammen mit ihren normierten Darstellungen.  Dann gilt
  Folgendes.
  \begin{itemize}
  \item Es ist $r|s$ genau dann, wenn für alle $i∈I$ die Ungleichung $ν_i ≤ μ_i$
    gilt.
    
  \item Es ist $r || s$ genau dann, wenn für alle $i∈I$ die Ungleichung
    $ν_i ≤ μ_i$ gilt und wenn zusätzlich ein $j∈I$ existiert, sodass
    $ν_j < μ_j$ ist.
    
  \item Es ist $r \sim s$ genau dann, wenn für alle $i∈I$ gilt, dass $ν_i = μ_i$
    ist.
  \end{itemize}
\end{beobachtung}


\section{ggT und kgV}

Je nach Geburtsjahrgang haben Sie in Kindergarten, Vorschule, Grundschule,
Gymnasium oder Studium den Begriff „größter gemeinsamer Teiler“ und „kleinstes
gemeinsames Vielfaches“ kennengelernt.  Auch diese Begriffe übertragen sich ohne
weiteres auf Ringe.

\begin{defn}[Größter gemeinsamer Teiler]
  Es sei $R$ ein kommutativer Ring mit 1 und es seien $r,s∈ R$ zwei Elemente.
  Ein Element $g ∈ R$ heißt \emph{größter gemeinsamer Teiler\index{größter
      gemeinsamer Teiler} von $r$ und $s$}, wenn Folgendes gilt.
  \begin{itemize}
  \item Es ist $g|r$ und $g|s$.
    
  \item Für alle $t ∈ R$ gilt: $t|r$ und $t|s$ impliziert $t|g$.
  \end{itemize}
  Man schreibt in dieser Situation oft $g = \ggT(r,s)$\index{ggT}.
\end{defn}

\begin{defn}[Kleinstes gemeinsames Vielfaches]
  Sei $R$ ein kommutativer Ring mit 1 und es seien $r,s∈ R$ zwei Elemente.  Ein
  Element $v ∈ R$ heißt \emph{kleines gemeinsames Vielfaches}\index{kleinstes
    gemeinsames Vielfaches} von $r$ und $s$, wenn Folgendes gilt.
  \begin{itemize}
  \item Es ist $r|v$ und $s|v$.
    
  \item Für alle $t ∈ R$ gilt: $r|t$ und $s|t$ impliziert $v|t$.
  \end{itemize}
  Man schreibt in dieser Situation oft $v = \kgV(r,s)$\index{kgV}.
\end{defn}

\begin{definition}[Teilerfremde Elemente]
  Es sei $R$ ein kommutativer Ring mit 1.  Zwei Elemente $r,s ∈ R$ heißen
  \emph{teilerfremd}\index{teilerfremd}, wenn der $1 = \ggT(r, s))$ ist.
\end{definition}

\begin{warnung}
  Obwohl man oft von „dem größten gemeinsamen Teiler“ spricht, ist der größte
  gemeinsame Teiler nicht eindeutig!  Wenn $g$ ein größter gemeinsame Teiler ist
  und $ε ∈ R^*$, dann ist auch $ε·g$ ein größter gemeinsame Teiler!  Mit unserer
  Definition ist sowohl $3 = \ggT(6,9)$ als auch $-3 = \ggT(6,9)$.  Dito für
  $\kgV$.
\end{warnung}

\begin{warnung}
  In den Übungen werden wir sehen, dass größte gemeinsame Teiler in beliebigen
  Ringen im Allgemeinen nicht existieren!
\end{warnung}

In faktoriellen Ringen müssen wir uns über die Existenz von $\ggT$ und $\kgV$
keine Gedanken machen.

\begin{satz}
  Ist $R$ ein faktorieller Ring, dann existiert zu jedem Paar
  $r,s ∈ R ∖ \{0\}$ ein größter gemeinsamer Teiler und ein kleinstes
  gemeinsames Vielfaches.
\end{satz}
\begin{proof}
  Wähle ein Repräsentantensystem $(p_i)_{i ∈ I}$ von zueinander assoziierten
  Primelementen wie in Situation~\ref{sit:5-5-1}.  Schreibe
  \[
    r = ε_r·\prod (p_i)^{ν_i} \quad\text{und}\quad s = ε_s·\prod (p_i)^{μ_i}.
  \]
  Dann ist
  \begin{equation*}
    \ggT(r,s) = \prod (p_i)^{\min(ν_i,μ_i)} \quad\text{und}\quad
    \kgV(r,s) = \prod (p_i)^{\max(ν_i,μ_i)}.  \qedhere
  \end{equation*}
\end{proof}



\subsection{Der Euklidische Algorithmus}

Die Primfaktorzerlegung eines Elementes in einem faktoriellen Ring zu bestimmen,
ist fast immer sehr schwer.  In manchen Ringen kann man aber das kgV bestimmen,
ohne die Primfaktorzerlegung explizit zu kennen.

\begin{bsp}\label{bsp:5-6-7}
  Sei $K$ ein Körper.  Dann kann man im Ring $K[x]$ den \emph{Euklidischen
    Algorithmus\index{Euklidischer Algorithmus}} verwenden.  Seien also
  $f,g∈ K[x]$ gegeben.  Dann betrachte die Kette von Gleichungen, die man durch
  Division mit Rest bekommt
  \begin{align}
    f(x)  &= q_1(x)·  g(x)+r_1(x)&&\text{mit }\deg r_1 < \deg g\label{eq:Euklid_1}\\
    g(x)  &= q_2(x)·r_1(x)+r_2(x)&&\text{mit }\deg r_2 < \deg r_1\label{eq:Euklid_2}\\
    r_1(x)&= q_3(x)·r_2(x)+r_3(x)&&\text{mit }\deg r_3 < \deg r_2 \\
    r_2(x)&= q_4(x)·r_3(x)+r_4(x)&&\text{mit }\deg r_4 < \deg r_3 \\
    r_3(x)&= q_5(x)·r_4(x)+r_5(x)&&\text{mit }\deg r_5 < \deg r_4 \\
    r_4(x)&= q_6(x)·r_5(x)+r_6(x)&&\text{mit }\deg r_6 < \deg r_5 \\
          &\qquad\vdots&&\qquad\vdots\nonumber\\
    \intertext{denn da die Grade immer kleiner werden, muss die Division irgendwann aufgehen}
    r_{n-2}(x) &= q_n(x)· r_{n-1}(x)+r_n(x)&&\text{mit } \deg r_{n} < \deg r_{n-1}\label{eq:Euklid_3}\\
    r_{n-1}(x) &= q_{n+1}(x)· r_n(x)\label{eq:Euklid_4}
  \end{align}
  
\end{bsp}

\begin{satz}
  In Beispiel~\ref{bsp:5-6-7} ist $r_n = \ggT(f, g)$.
\end{satz}
\begin{proof}
  Sei $t(x)∈ K[x]$ ein Teiler von $f(x)$ und $g(x)$.  Dann folgt aus
  \eqref{eq:Euklid_1}: $t|r_1$.  Aus \eqref{eq:Euklid_2} folgt $t|r_2$ und so
  weiter bis schließlich $t|r_n$.  Umgekehrt folgt aus \eqref{eq:Euklid_4}
  $r_n|r_{n-1}$.  Aus \eqref{eq:Euklid_3} folgt $r_n|r_{n-2}$ und so weiter.
  Schließlich folgt $r_n|g$ und $r_n|f$.
\end{proof}

Ein analoges Verfahren kennen Sie aus der Schule für $ℤ$.  Für $R = ℤ[x]$
lässt sich so ein Verfahren aber beispielsweise nicht anwenden!

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "AlgebraZahlentheorie"
%%% End:

