Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 15/latex

Aus Wikiversity
Zur Navigation springen Zur Suche springen

\setcounter{section}{15}






\zwischenueberschrift{Der Hauptsatz der elementaren Zahlentheorie}

Wir beweisen nun, dass sich jede natürliche Zahl in eindeutiger Weise als Produkt von Primzahlen darstellen lässt.





\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Primzahl erfüllt Primelementeigenschaft/Fakt}
{Satz}
{}
{

\faktsituation {Es sei $p$ eine \definitionsverweis {Primzahl}{}{} und}
\faktvoraussetzung {$p$ teile ein Produkt $ab$ von natürlichen Zahlen
\mavergleichskette
{\vergleichskette
{a,b }
{ \in }{\N }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}}
\faktfolgerung {Dann teilt $p$ einen der Faktoren.}
\faktzusatz {}
\faktzusatz {}

}
{

Die Voraussetzung bedeutet, dass
\mavergleichskettedisp
{\vergleichskette
{ \overline{ a }\,\overline{ b }\, }
{ =} {\overline{ 0 }\, }
{ =} {0 }
{ } { }
{ } { }
} {}{}{} in $\Z/(p)$ ist. Da $p$ eine Primzahl ist, ist dieser Restklassenring nach Satz 14.13 ein \definitionsverweis {Körper}{}{,} so dass ein Faktor null sein muss. Sagen wir
\mathl{\overline{ a }\,=0}{.} Dies bedeutet aber zurückübersetzt nach $\Z$, dass $a$ ein Vielfaches von $p$ ist.

}






\inputfaktbeweis
{Zahlentheorie/Primfaktorzerlegung/Fakt}
{Satz}
{}
{

Jede natürliche Zahl
\mathbed {n\in \N} {}
{n \geq 2} {}
{} {} {} {,} besitzt eine eindeutige Zerlegung in Primfaktoren.

D.h. es gibt eine Darstellung
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} {p_1 { \cdots } p_r }
{ } { }
{ } { }
{ } { }
} {}{}{} mit \definitionsverweis {Primzahlen}{}{} $p_i$, und dabei sind die Primfaktoren bis auf ihre Reihenfolge eindeutig bestimmt.

}
{

Wir beweisen die Existenz und die Eindeutigkeit jeweils durch Induktion.  Für
\mathl{n=2}{} liegt eine Primzahl vor. Bei
\mathl{n\geq3}{} ist entweder $n$ eine Primzahl, und diese bildet die Primfaktorzerlegung, oder aber $n$ ist keine Primzahl. In diesem Fall gibt es eine nichttriviale Zerlegung
\mathl{n=ab}{} mit kleineren Zahlen
\mathl{a,b <n}{.} Für diese Zahlen gibt es nach der Induktionsvoraussetzung eine Zerlegung in Primfaktoren, und diese setzen sich zu einer Primfaktorzerlegung für $n$ zusammen. Zur Eindeutigkeit:  Bei
\mathl{n=2}{} ist die Aussage klar. Im Allgemeinen seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} { p_1{ \cdots }p_r }
{ =} { q_1 { \cdots } q_s }
{ } { }
{ } { }
} {}{}{.} Insbesondere teilt die Primzahl $p_1$ dann das Produkt rechts, und damit nach dem Lemma von Euklid einen der Faktoren. Nach Umordnung können wir annehmen, dass $q_1$ von $p_1$ geteilt wird. Da $q_1$ selbst eine Primzahl ist, folgt, dass
\mathl{p_1=q_1}{} sein muss. Da $\Z$ \definitionsverweis {nullteilerfrei}{}{} ist, kann man beidseitig durch
\mathl{p_1=q_1}{} dividieren und erhält die Gleichung
\mavergleichskettedisp
{\vergleichskette
{ n^\prime }
{ =} { p_2{ \cdots }p_r }
{ =} { q_2 { \cdots } q_s }
{ } { }
{ } { }
} {}{}{.} Da
\mathl{n'<n}{} ist, können wir die Induktionsvoraussetzung der Eindeutigkeit auf $n'$ anwenden. 

}


Zu einer Primzahl $p$ und einer positiven ganzen Zahl $n$ ist der \stichwort {Exponent} {,} also die Vielfachheit, mit der $p$ als Primfaktor in $n$ auftritt, eindeutich festgelegt. Dieser Exponent wird mit
\mathl{{ \nu_p(n) }}{} bezeichnet. Die eindeutige Primfaktorzerlegung kann man auch als
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} {\prod_p p^{ \nu_p(n) } }
{ } { }
{ } { }
{ } { }
} {}{}{} schreiben, wobei das Produkt in Wirklichkeit endlich ist, da in der Primfaktorzerlegung nur endlich viele Primfaktoren mit einem positiven Exponenten vorkommen.





\inputfaktbeweis
{Teilbarkeitstheorie (Z)/Exponentenkriterium/Fakt}
{Lemma}
{}
{

\faktsituation {Es seien \mathkor {} {n} {und} {k} {} positive natürliche Zahlen.}
\faktvoraussetzung {Dann wird $n$ von $k$ genau dann geteilt,}
\faktfolgerung {wenn für jede Primzahl $p$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ { \nu_p(n) } }
{ \geq} { { \nu_p(k) } }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt.}
\faktzusatz {}
\faktzusatz {}

}
{

$(1) \Rightarrow (2)$. Aus der Beziehung
\mathl{n=kt}{} folgt in Verbindung mit der eindeutigen Primfaktorzerlegung, dass die Primfaktoren von $k$ mit mindestens ihrer Vielfachheit auch in $n$ vorkommen müssen.
$(2) \Rightarrow (1)$. Wenn die Exponentenbedingung erfüllt ist, so ist
\mathl{t= \prod_p p^{{ \nu_p(n) }-{ \nu_p(k) }}}{} eine natürliche Zahl mit
\mathl{n=kt}{.}

}






\inputfaktbeweis
{Zahlentheorie/Primfaktorzerlegung/KgV und ggT/Fakt}
{Korollar}
{}
{

\faktsituation {Es seien \mathkor {} {n} {und} {m} {} positive natürliche Zahlen mit den Primfaktorzerlegungen \mathkor {} {n=\prod_p p^{ \nu_p(n) }} {und} {m=\prod_p p^{ \nu_p(m) }} {.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{kgV} (n,m) }
{ =} { \prod_p p^{\max { \left( { \nu_p(n) } , { \nu_p(m) } \right) } } }
{ } { }
{ } { }
{ } { }
} {}{}{} und
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ggT} (n,m) }
{ =} { \prod_p p^ {\min { \left( { \nu_p(n) } , { \nu_p(m) } \right) } } }
{ } { }
{ } { }
{ } { }
} {}{}{.}}
\faktzusatz {}
\faktzusatz {}

}
{

Dies folgt direkt aus Lemma 15.3.

}







\zwischenueberschrift{Produktringe}

Um die Restklassenringe von $\Z$ besser verstehen zu können, insbesondere dann, wenn man $n$ als Produkt von kleineren Zahlen schreiben kann \zusatzgs {z.B., wenn die Primfaktorzerlegung bekannt ist} {,} braucht man den Begriff des Produktringes.




\inputdefinition
{}
{

Seien
\mathl{R_1 , \ldots , R_n}{} \definitionsverweis {kommutative Ringe}{}{.} Dann heißt das Produkt
\mathdisp {R_1 \times \cdots \times R_n} { , }
versehen mit komponentenweiser Addition und Multiplikation, der \definitionswort {Produkt\-ring}{} der
\mathbed {R_i} {}
{i=1 , \ldots , n} {}
{} {} {} {.}

}

Eng verwandt mit dem Begriff des Produktringes ist das Konzept der idempotenten Elemente.


\inputdefinition
{}
{

Ein Element $e$ eines \definitionsverweis {kommutativen Ringes}{}{} heißt \definitionswort {idempotent}{,} wenn
\mavergleichskette
{\vergleichskette
{e^2 }
{ = }{e }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} gilt.

}

Die Elemente \mathkor {} {0} {und} {1} {} sind trivialerweise idempotent, man nennt sie die trivialen idempotenten Elemente. In einem Produktring sind auch diejenigen Elemente, die in allen Komponenten nur den Wert \mathkor {} {0} {oder} {1} {} besitzen, idempotent, also bspw.
\mathl{(1,0)}{.} In einem Integritätsbereich gibt es nur die beiden trivialen idempotenten Elemente: Ein idempotentes Element $e$ besitzt die Eigenschaft
\mavergleichskettedisp
{\vergleichskette
{e(1-e) }
{ =} {e-e^2 }
{ =} {e-e }
{ =} {0 }
{ } {}
} {}{}{.} Im nullteilerfreien Fall folgt daraus \mathkor {} {e=1} {oder} {e=0} {.}





\inputfaktbeweis
{Produktring/Einheitengruppe/Fakt}
{Lemma}
{}
{

\faktsituation {Es sei
\mathl{R=R_1 \times \cdots \times R_n}{} ein \definitionsverweis {Produkt}{}{} aus kommutativen Ringen.}
\faktfolgerung {Dann gilt für die \definitionsverweis {Einheitengruppe}{}{} von $R$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ R^{\times} }
{ =} { R_1^{\times} \times \cdots \times R_n^{\times} }
{ } { }
{ } { }
{ } { }
} {}{}{.}}
\faktzusatz {}
\faktzusatz {}

}
{

Dies ist klar, da ein Element genau dann eine Einheit ist, wenn es in jeder Komponente eine Einheit ist.

}







\zwischenueberschrift{Der Chinesische Restsatz für $\Z$}


\inputfaktbeweis
{Restklassenringe (Z)/Chinesischer Restsatz/Fakt}
{Satz}
{}
{

\faktsituation {Sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} { p_1^{r_1} \cdot p_2^{r_2} { \cdots } p_k^{r_k} }
{ } { }
{ } { }
{ } { }
} {}{}{} \zusatzklammer {die $p_i$ seien also verschieden und
\mavergleichskettek
{\vergleichskettek
{ r_i }
{ \geq }{ 1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}} {} {.}}
\faktfolgerung {Dann induzieren die kanonischen Ringhomomorphismen \maabb {} {\Z/(n)} {\Z/(p_i^{r_i} ) } {} einen \definitionsverweis {Ringisomorphismus}{}{}
\mavergleichskettedisp
{\vergleichskette
{ \Z/(n) }
{ \cong} { \Z/(p_1^{r_1} ) \times \Z/(p_2^{r_2} ) \times \cdots \times \Z/(p_k^{r_k} ) }
{ } { }
{ } { }
{ } { }
} {}{}{.}}
\faktzusatz {Zu gegebenen ganzen Zahlen
\mathl{(a_1,a_2 , \ldots , a_k)}{} gibt es also genau eine natürliche Zahl
\mavergleichskette
{\vergleichskette
{a }
{ < }{n }
{ }{ }
{ }{ }
{ }{ }
} {}{}{,} die die \stichwort {simultanen Kongruenzen} {}
\mathdisp {a= a_1 \mod p_1^{r_1}, \,\, a= a_2 \mod p_2^{r_2}, \, \ldots , \,\, a= a_k \mod p_k^{r_k}} { }
löst.}
\faktzusatz {}

}
{Da die Ringe links und rechts beide endlich sind und die gleiche Anzahl von Elementen haben, nämlich $n$, genügt es, die Injektivität zu zeigen. Sei $x$ eine natürliche Zahl, die im Produktring (rechts) zu null wird, also modulo
\mathl{p_i^{r_i}}{} den Rest null hat für alle
\mathl{i=1,2, \ldots ,k}{.} Dann ist $x$ ein Vielfaches von
\mathl{p_i^{r_i}}{} für alle
\mathl{i=1,2, \ldots , k}{,} d.h., es ist ein gemeinsames Vielfaches dieser Potenzen. Daraus folgt aufgrund von Lemma 4.8,

dass $x$ ein Vielfaches des Produktes sein muss, also ein Vielfaches von $n$. Damit ist
\mathl{x=0}{} in $\Z/(n)$ und die Abbildung ist injektiv.}


\inputbeispiel
{}
{ \inputaufgabeloesungvar{

(a) Bestimme für die Zahlen $3$, $5$ und $7$ modulare Basislösungen, finde also die kleinsten positiven Zahlen, die in
\mathdisp {\Z/(3) \times \Z/(5) \times \Z/(7)} { }
die Restetupel $(1,0,0),\, (0,1,0)$ und $(0,0,1)$ repräsentieren.

(b) Finde mit den Basislösungen die kleinste positive Lösung $x$ der simultanen Kongruenzen
\mathdisp {x = 2 \!\! \mod 3 , \, \, \, \, x = 4 \!\! \mod 5 \text{ und } x = 3 \!\! \mod 7} { . }

} {

(a) $(1,0,0)$

Alle Vielfachen von
\mathl{5 \cdot 7=35}{} haben modulo $5$ und modulo $7$ den Rest $0$. Unter diesen Vielfachen muss also die Lösung liegen. $35$ hat modulo $3$ den Rest $2$, somit hat $70$ modulo $3$ den Rest $1$. Also repräsentiert $70$ das Restetupel
\mathl{(1,0,0)}{.}


\mathl{(0,1,0)}{:} Hier betrachtet man die Vielfachen von $21$, und $21$ hat modulo $5$ den Rest $1$. Also repräsentiert $21$ das Restetupel
\mathl{(0,1,0)}{.}


\mathl{(0,0,1)}{:} Hier betrachtet man die Vielfachen von $15$, und $15$ hat modulo $7$ den Rest $1$. Also repräsentiert $15$ das Restetupel
\mathl{(0,0,1)}{.}

(b) Man schreibt \zusatzklammer {in \mathlk{\Z/(3) \times \Z/(5) \times \Z/(7)}{}} {} {}
\mavergleichskettedisp
{\vergleichskette
{ (2,4,3) }
{ =} {2(1,0,0)+4(0,1,0)+3(0,0,1) }
{ } { }
{ } { }
{ } { }
} {}{}{.} Die Lösung ist dann
\mavergleichskettedisp
{\vergleichskette
{ 2 \cdot 70 +4 \cdot 21 +3 \cdot 15 }
{ =} { 140+84+45 }
{ =} {269 }
{ } { }
{ } { }
} {}{}{.} Die minimale Lösung ist dann
\mavergleichskette
{\vergleichskette
{ 269- 2 \cdot 105 }
{ = }{ 59 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

} }





\inputfaktbeweis
{Chinesischer Restsatz/Einheiten/Fakt}
{Korollar}
{}
{

\faktsituation {Sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
\mavergleichskette
{\vergleichskette
{n }
{ = }{p_1^{r_1} \cdot p_2^{r_2} \cdots p_k^{r_k} }
{ }{ }
{ }{ }
{ }{ }
} {}{}{}}
\faktvoraussetzung {(die $p_i$ seien also verschieden und \mathlk{r_i \geq 1}{).}}
\faktfolgerung {Dann gibt es einen kanonischen \definitionsverweis {Gruppenisomorphismus}{}{}
\mavergleichskettedisp
{\vergleichskette
{ { \left( \Z/(n) \right) }^{\times} }
{ \cong} { { \left( \Z/(p_1^{r_1} ) \right) }^{\times} \times \cdots \times { \left( \Z/(p_k^{r_k} ) \right) }^{\times} }
{ } { }
{ } { }
{ } { }
} {}{}{.}}
\faktzusatz {Insbesondere ist eine Zahl $a$ genau dann eine Einheit modulo $n$, wenn sie eine Einheit modulo
\mathl{p_i^{r_i}}{} ist für
\mathl{i=1 , \ldots , k}{.}}
\faktzusatz {}

}
{

Dies folgt aus dem chinesischen Restsatz und Lemma 15.7.

}







\zwischenueberschrift{Die Eulersche $\varphi$-Funktion}





\inputfaktbeweis
{Restklassenring (Z)/Einheit/Charakterisierung/Teilerfremd/Fakt}
{Satz}
{}
{

Genau dann ist
\mathl{a \in \Z}{} eine \definitionsverweis {Einheit}{}{} modulo $n$ \zusatzklammer {d.h. $a$ repräsentiert eine Einheit in \mathlk{\Z/(n)}{}} {} {,} wenn \mathkor {} {a} {und} {n} {} \definitionsverweis {teilerfremd}{}{} sind.

}
{

Sind \mathkor {} {a} {und} {n} {} \definitionsverweis {teilerfremd}{}{,} so gibt es nach Satz 4.1 eine Darstellung der $1$, es gibt also ganze Zahlen
\mathl{r,s}{} mit
\mavergleichskettedisp
{\vergleichskette
{ra+sn }
{ =} {1 }
{ } { }
{ } { }
{ } { }
} {}{}{.} Betrachtet man diese Gleichung modulo $n$, so ergibt sich
\mavergleichskette
{\vergleichskette
{ra }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} in
\mathl{\Z/(n)}{.} Damit ist $a$ eine Einheit mit Inversem
\mavergleichskette
{\vergleichskette
{ a^{-1} }
{ = }{ r }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

Ist umgekehrt $a$ eine Einheit in
\mathl{\Z/(n)}{,} so gibt es ein
\mathl{r \in \Z/(n)}{} mit
\mathl{ar=1}{} in
\mathl{\Z/(n)}{.} Das bedeutet aber, dass
\mathl{ar-1}{} ein Vielfaches von $n$ ist, so dass also
\mavergleichskettedisp
{\vergleichskette
{ ar-1 }
{ =} { sn }
{ } { }
{ } { }
{ } { }
} {}{}{} gilt. Dann ist aber wieder
\mavergleichskette
{\vergleichskette
{ar-sn }
{ = }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} und $a$ und $n$ sind teilerfremd.

}







\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Leonhard_Euler_by_Handmann_.eps} }
\end{center}
\bildtext {Leonhard Euler (1707-1783)} }

\bildlizenz { Leonhard Euler by Handmann .png } {Emanuel Handmann} {QWerk} {Commons} {PD} {http://www.euler-2007.ch/doc/Bild0015.pdf}





\inputdefinition
{}
{

Zu einer natürlichen Zahl $n$ bezeichnet
\mathl{{\varphi (n)}}{} die Anzahl der Elemente von
\mathl{(\Z/(n))^{\times}}{.} Man nennt
\mathl{{\varphi (n)}}{} die \definitionswort {Eulersche Funktion}{.}

}






\inputbemerkung
{}
{

Die \definitionsverweis {Eulersche Funktion}{}{}
\mathl{\varphi(n)}{} gibt also für
\mavergleichskette
{\vergleichskette
{n }
{ \geq }{1 }
{ }{ }
{ }{ }
{ }{ }
} {}{}{} nach Satz 15.11 an, wie viele Zahlen $r$,
\mathl{0 \leq r<n}{,} zu $n$ \definitionsverweis {teilerfremd}{}{} sind.

}

Für eine Primzahl ist ${\varphi (n)}=p-1$. Eine Verallgemeinerung des
\stichwort{kleinen Fermat}{} ist der folgende Satz von Euler.





\inputfaktbeweis
{Restklassenringe von Z/Einheiten/Euler/Fakt}
{Satz}
{}
{

\faktsituation {}
\faktvoraussetzung {Sei $n$ eine natürliche Zahl.}
\faktfolgerung {Dann gilt für jede zu $n$ teilerfremde Zahl $a$ die Beziehung
\mavergleichskettedisp
{\vergleichskette
{ a^{\varphi (n)} }
{ =} { 1 \!\! \! \mod n }
{ } { }
{ } { }
{ } { }
} {}{}{.}}
\faktzusatz {}
\faktzusatz {}

}
{

Das Element $a$ gehört zur Einheitengruppe
\mathl{{ \left( \Z/(n) \right) }^{\times}}{,} die
\mathl{\varphi(n)}{} Elemente besitzt. Nach dem Satz von Lagrange ist aber die Gruppenordnung ein Vielfaches der Ordnung des Elementes.

}


Wir geben abschließend Formeln an, wie man die Eulersche $\varphi$-Funktion berechnet, wenn die Primfaktorzerlegung bekannt ist.





\inputfaktbeweis
{Eulersche Funktion (Zahlentheorie)/Formel für Primzahlpotenz/Fakt}
{Lemma}
{}
{

\faktsituation {Es sei $p$ eine \definitionsverweis {Primzahl}{}{} und $p^r$ eine Potenz davon.}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{ {\varphi (p^r)} }
{ =} {p^{r-1} (p-1) }
{ } { }
{ } { }
{ } { }
} {}{}{.}}
\faktzusatz {}
\faktzusatz {}

}
{

Eine Zahl $a$ ist genau dann \definitionsverweis {teilerfremd}{}{} zu einer Primzahlpotenz $p^r$, wenn sie teilerfremd zu $p$ selbst ist, und dies ist genau dann der Fall, wenn sie kein Vielfaches von $p$ ist. Unter den natürlichen Zahlen
\mathl{< p^r}{} sind genau die Zahlen
\mathdisp {0,p,2p,3p , \ldots , (p^{r-1}-1) p} { }
Vielfache von $p$. Das sind
\mathl{p^{r-1}}{} Stück, und daher gibt es
\mavergleichskettedisp
{\vergleichskette
{p^r-p^{r-1} }
{ =} {p^{r-1}(p-1) }
{ } {}
{ } {}
{ } {}
} {}{}{} Einheiten in
\mathl{\Z/(p^r)}{.} Also ist
\mavergleichskette
{\vergleichskette
{ {\varphi (p^r)} }
{ = }{p^{r-1}(p-1) }
{ }{ }
{ }{ }
{ }{ }
} {}{}{.}

}






\inputfaktbeweis
{Eulersche Funktion (Zahlentheorie)/Produktformel bei Primfaktorzerlegung/Vollständig/Fakt}
{Korollar}
{}
{

\faktsituation {Sei $n$ eine positive natürliche Zahl mit kanonischer Primfaktorzerlegung
\mavergleichskettedisp
{\vergleichskette
{n }
{ =} { p_1^{r_1} { \cdots } p_k^{r_k} }
{ } { }
{ } { }
{ } { }
} {}{}{} \zusatzklammer {die $p_i$ seien also verschieden und \mathlk{r_i \geq 1}{}} {} {.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{ {\varphi (n)} }
{ =} { {\varphi (p_1^{r_1})} { \cdots } {\varphi (p_k^{r_k})} }
{ =} { (p_1-1) p_1^{r_1-1} { \cdots } (p_k-1) p_k^{r_k-1} }
{ } {}
{ } {}
} {}{}{.}}
\faktzusatz {}
\faktzusatz {}

}
{

Die erste Gleichung folgt aus Korollar 15.10 und die zweite aus Lemma 15.15.

}



<< | Kurs:Einführung in die Algebra (Osnabrück 2009) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)