Kurs:Einführung in die Algebra (Osnabrück 2009)/Vorlesung 15/latex
\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}{}{,}
sodass 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:
Für
\mavergleichskette
{\vergleichskette
{ n
}
{ = }{ 2
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
liegt eine Primzahl vor und die Aussage ist klar. Es sei nun
\mavergleichskette
{\vergleichskette
{ n
}
{ \geq }{ 3
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir
\mavergleichskettedisp
{\vergleichskette
{ n
}
{ =} { p_1 { \cdots } p_r
}
{ =} { q_1 { \cdots } q_s
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl $p_1$ das Produkt rechts teilt. Nach
dem Lemma von Euklid
muss dann $p_1$ einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass $q_1$ von $p_1$ geteilt wird. Da $q_1$ selbst eine Primzahl ist, folgt, dass
\mavergleichskette
{\vergleichskette
{ p_1
}
{ = }{ q_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sein muss. Daraus ergibt sich durch Kürzen, dass
\mavergleichskettedisp
{\vergleichskette
{ p_2 { \cdots } p_r
}
{ =} {q_2 { \cdots } q_s
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist. Nennen wir diese Zahl $n'$. Da
\mavergleichskette
{\vergleichskette
{ n'
}
{ < }{ n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist, können wir die Induktionsvoraussetzung auf $n'$ anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen.
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{{ \exp_p(n) }}{} bezeichnet. Die eindeutige Primfaktorzerlegung kann man auch als
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {\prod_p p^{ \exp_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
{ { \exp_p(n) }
}
{ \geq} { { \exp_p(k) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.}
\faktzusatz {}
\faktzusatz {}
}
{
$(1) \Rightarrow (2)$. Aus der Beziehung
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ t
}
{ = }{ \prod_p p^{{ \exp_p(n) }-{ \exp_p(k) }}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine natürliche Zahl mit
\mavergleichskette
{\vergleichskette
{ 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^{ \exp_p(n) }} {und} {m=\prod_p p^{ \exp_p(m) }} {.}}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{
\operatorname{kgV} (n,m)
}
{ =} { \prod_p p^{\max { \left( { \exp_p(n) } , { \exp_p(m) } \right) } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{ \operatorname{ggT} (n,m)
}
{ =} { \prod_p p^ {\min { \left( { \exp_p(n) } , { \exp_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
{}
{
Es 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
\mavergleichskette
{\vergleichskette
{R
}
{ = }{ R_1 \times \cdots \times R_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Produkt}{}{}
aus
\definitionsverweis {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$}
{Restklassenringe (Z)/Chinesischer Restsatz/Fakt}
{Satz}
{}
{
\faktsituation {Es 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
\betonung{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,
\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 {Es 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 {\zusatzklammer {die $p_i$ seien also verschieden und
\mavergleichskettek
{\vergleichskettek
{ 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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ 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
\mavergleichskette
{\vergleichskette
{ r
}
{ \in }{ \Z/(n)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ ar
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in
\mathl{\Z/(n)}{.} Das bedeutet aber, dass
\mathl{ar-1}{} ein Vielfaches von $n$ ist, sodass 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_.png} }
\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
\mathbed {r} {}
{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 {Es 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 {Es 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.