Kurs:Elemente der Algebra (Osnabrück 2015)/Vorlesung 16/latex
\setcounter{section}{16}
\zwischenueberschrift{Der Chinesische Restsatz für $\Z$}
\inputfaktbeweis
{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 {}
}
{
Dies folgt unmittelbar aus Satz 15.7.
Beweisvariante
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. Es sei $x$ eine natürliche Zahl, die im Produktring
\zusatzklammer {rechts} {} {}
zu $0$ wird, also modulo $p_i^{r_i}$ den Rest $0$ hat für alle
\mavergleichskette
{\vergleichskette
{ i
}
{ = }{ 1,2 , \ldots , k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist $x$ ein Vielfaches von $p_i^{r_i}$ für alle
\mavergleichskette
{\vergleichskette
{ i
}
{ = }{ 1,2 , \ldots , k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
d.h. in der Primfaktorzerlegung von $x$ muss $p_i$ zumindest mit dem Exponenten $r_i$ vorkommen. Also muss $x$
nach Lemma 9.9
ein Vielfaches des Produktes sein, also ein Vielfaches von $n$. Damit ist
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in
\mathl{\Z/(n)}{} und die Abbildung ist injektiv.
Unter den Basislösungen zu einer simultanen Kongruenz versteht man die kleinsten natürlichen Zahlen, die modulo den vorgegebenen Zahlen ein Restetupel ergeben, das an genau einer Stelle den Wert $1$ und sonst überall den Wert $0$ besitzt. Aus diesen Basislösungen kann man die Lösungen zu sämtlichen simultanen Kongruenzen berechnen.
\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 {(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.6.
\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.
}
{
Dies folgt aus Lemma 14.9.
Beweisvariante
Sind \mathkor {} {a} {und} {n} {}
\definitionsverweis {teilerfremd}{}{,}
so gibt es nach
Satz 8.5
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, 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 16.4
an, wie viele Zahlen $r$,
\mathl{0 \leq r<n}{,} zu $n$
\definitionsverweis {teilerfremd}{}{}
sind.
}
Für eine Primzahl $p$ ist
\mavergleichskette
{\vergleichskette
{ {\varphi (p)}
}
{ = }{ 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 16.3 und die zweite aus Lemma 16.8.