Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:42 Mo 19.12.2016 | | Autor: | Marcel |
| Aufgabe | Hallo,
ich führe einen Alternativbeweis, den ich so zumindest bisher noch nicht
gesehen habe (das heißt aber nichts, denn ich habe jetzt dahingehend
auch nicht besonders viele Bücher durchforstet) zu der Aussage, dass
[mm] $\IZ/(rs)\IZ$ [/mm] isomorph zu [mm] $\IZ/r\IZ \times \IZ/s\IZ$ [/mm] für [mm] $\ggT(r,s)=1$ [/mm] ist. |
Ich würde darum bitten, diesen Beweis auf Richtigkeit zu überprüfen, oder
vielleicht habe ich doch einen (Denk-)Fehler gemacht?
Beweis:
Zunächst seien $n,r,s [mm] \in \IN$ [/mm] mit $n=rs$. Wir betrachten (Standard!)
$f [mm] \colon \IZ/n\IZ \to \IZ/r\IZ \times \IZ/s\IZ$
[/mm]
mit [mm] $f([x]_n)=([x]_r, [x]_s)$ [/mm] - ich denke, es ist klar, dass für $x,y [mm] \in \IZ$ [/mm] genau dann
$y [mm] \in [x]_n:=x+n\IZ=\{x+nz: z \in \IZ\}$ [/mm] geschrieben wird, wenn $x [mm] \equiv [/mm] y$ mod [mm] $n\,$ [/mm] bzw. [mm] $[x]_n=[y]_n$ [/mm] gilt.
Wegen $r [mm] \mid [/mm] n$ und $s [mm] \mid [/mm] n$ ist [mm] $f\,$ [/mm] wohldefiniert, und dass [mm] $f\,$ [/mm] ein Ring-Homomorphismus
ist, ist wegen der Rechenregeln für Kongruenzen auch klar.
Ich zeige nun:
Ist [mm] $x_0 \in \{0,...,n-1\}$, [/mm] so ist
[mm] $\blue{\min\{z \in \IN: z > x_0 \text{ und }f([z]_n)=f([x_0]_n)\}}=x_0+\kgV(r,s)$
[/mm]
und die Werte [mm] $f([0]_n), \ldots, f([x_0+\kgV(r,s)-1])$ [/mm] sind alle paarweise verschieden.
Sei [mm] $y_0:=x_0+\kgV(r,s).$ [/mm] Dann gilt
[mm] $f([y_0]_n)=([y_0]_r,[y_0]_s)=([x_0]_r+[\kgV(r,s)]_r, [x_0]_s+[\kgV(r,s)]_s)=([x_0]_r+[0]_r, [x_0]_s+[0]_s)=f([x_0]_n)$.
[/mm]
Also ist [mm] $y_0 \ge \blue{\min\{z \in \IN: z > x_0 \text{ und }f([z]_n)=f([x_0]_n)\}}\,.$
[/mm]
Nun nehmen wir an, die Werte [mm] $f([x_0]_n),...,f([x_0+\kgV(r,s)-1]_n)$ [/mm] wären doch
nicht alle paarweise verschieden. Dann gibt es o.E. $v,w [mm] \in \IN_0$ [/mm] mit
$0 [mm] \le [/mm] v < [mm] \red{\,w \le \kgV(r,s)-1}$, [/mm] so dass
[mm] $f([x_0+v]_n)=f([x_0+w]_n)$
[/mm]
und wegen der Homomorphie von [mm] $f\,$ [/mm] folgt
[mm] $f([v]_n)=f([w]_n)\,.$
[/mm]
Daraus folgt aber wegen $w=v+(w-v)$ und der Homomorphie von [mm] $f\,$
[/mm]
[mm] $f([0]_n)=f([w-v]_n)=([w-v]_r, [w-v]_s)\,.$
[/mm]
Es folgt daher, dass sowohl $r [mm] \mid [/mm] (w-v)$ als auch $s [mm] \mid [/mm] (w-v)$ gilt. Folglich gilt auch
[mm] $\kgV(r,s) \mid (w-v)\,.$
[/mm]
Wegen $w > [mm] v\,$ [/mm] ist dann aber
[mm] $w-v=m*\kgV(r,s)$ [/mm] mit einem $m [mm] \ge [/mm] 1$
und daher $w [mm] \ge v+\kgV(r,s)\ge \kgV(r,s)$ [/mm] im Widerspruch zu $w [mm] \le \kgV(r,s)-1$.
[/mm]
Fazit: [mm] $|f(\IZ/n\IZ)|=|f(\IZ/(rs)\IZ)|=\kgV(r,s)\,.$
[/mm]
Folgerung: Wegen [mm] $rs=\ggT(r,s)*\kgV(r,s)$ [/mm] hat [mm] $f(\IZ/n\IZ)=f(\IZ/(rs)\IZ)$ [/mm] genau $n=rs$
Elemente, falls [mm] $\ggT(r,s)=1$. [/mm] Wegen [mm] $|\IZ/r\IZ \times \IZ/s\IZ|=rs$ [/mm] ist damit [mm] $f\,$ [/mm] dann surjektiv und als
surjektive Abbildung zwischen zwei endlichen Mengen zudem injektiv, also
bijektiv. Also gilt für [mm] $\ggT(r,s)=1$ [/mm] in der Tat, dass
[mm] $\IZ/(rs)\IZ \cong (\IZ/r\IZ \times \IZ/s\IZ)$.
[/mm]
Gruß,
Marcel
|
|
| |
|
> Hallo,
>
> ich führe einen Alternativbeweis, den ich so zumindest
> bisher noch nicht
> gesehen habe (das heißt aber nichts, denn ich habe jetzt
> dahingehend
> auch nicht besonders viele Bücher durchforstet) zu der
> Aussage, dass
> [mm]\IZ/(rs)\IZ[/mm] isomorph zu [mm]\IZ/r\IZ \times \IZ/s\IZ[/mm] für
> [mm]\ggT(r,s)=1[/mm] ist.
>
>
>
>
>
>
>
>
> Ich würde darum bitten, diesen Beweis auf Richtigkeit zu
> überprüfen, oder
> vielleicht habe ich doch einen (Denk-)Fehler gemacht?
>
> Beweis:
> Zunächst seien [mm]n,r,s \in \IN[/mm] mit [mm]n=rs[/mm]. Wir betrachten
> (Standard!)
>
> [mm]f \colon \IZ/n\IZ \to \IZ/r\IZ \times \IZ/s\IZ[/mm]
>
> mit [mm]f([x]_n)=([x]_r, [x]_s)[/mm] - ich denke, es ist klar, dass
> für [mm]x,y \in \IZ[/mm] genau dann
> [mm]y \in [x]_n:=x+n\IZ=\{x+nz: z \in \IZ\}[/mm] geschrieben wird,
> wenn [mm]x \equiv y[/mm] mod [mm]n\,[/mm] bzw. [mm][x]_n=[y]_n[/mm] gilt.
>
> Wegen [mm]r \mid n[/mm] und [mm]s \mid n[/mm] ist [mm]f\,[/mm] wohldefiniert, und dass
> [mm]f\,[/mm] ein Ring-Homomorphismus
> ist, ist wegen der Rechenregeln für Kongruenzen auch
> klar.
>
> Ich zeige nun:
> Ist [mm]x_0 \in \{0,...,n-1\}[/mm], so ist
>
> [mm]\blue{\min\{z \in \IN: z > x_0 \text{ und }f([z]_n)=f([x_0]_n)\}}=x_0+\kgV(r,s)[/mm]
>
> und die Werte [mm]f([0]_n), \ldots, f([x_0+\kgV(r,s)-1])[/mm] sind
> alle paarweise verschieden.
>
> Sei [mm]y_0:=x_0+\kgV(r,s).[/mm] Dann gilt
>
> [mm]f([y_0]_n)=([y_0]_r,[y_0]_s)=([x_0]_r+[\kgV(r,s)]_r, [x_0]_s+[\kgV(r,s)]_s)=([x_0]_r+[0]_r, [x_0]_s+[0]_s)=f([x_0]_n)[/mm].
>
> Also ist [mm]y_0 \ge \blue{\min\{z \in \IN: z > x_0 \text{ und }f([z]_n)=f([x_0]_n)\}}\,.[/mm]
>
> Nun nehmen wir an, die Werte
> [mm]f([x_0]_n),...,f([x_0+\kgV(r,s)-1]_n)[/mm] wären doch
> nicht alle paarweise verschieden. Dann gibt es o.E. [mm]v,w \in \IN_0[/mm]
> mit
> [mm]0 \le v < \red{\,w \le \kgV(r,s)-1}[/mm], so dass
>
> [mm]f([x_0+v]_n)=f([x_0+w]_n)[/mm]
>
> und wegen der Homomorphie von [mm]f\,[/mm] folgt
>
> [mm]f([v]_n)=f([w]_n)\,.[/mm]
>
> Daraus folgt aber wegen [mm]w=v+(w-v)[/mm] und der Homomorphie von
> [mm]f\,[/mm]
>
> [mm]f([0]_n)=f([w-v]_n)=([w-v]_r, [w-v]_s)\,.[/mm]
>
> Es folgt daher, dass sowohl [mm]r \mid (w-v)[/mm] als auch [mm]s \mid (w-v)[/mm]
> gilt. Folglich gilt auch
>
> [mm]\kgV(r,s) \mid (w-v)\,.[/mm]
>
> Wegen [mm]w > v\,[/mm] ist dann aber
>
> [mm]w-v=m*\kgV(r,s)[/mm] mit einem [mm]m \ge 1[/mm]
>
> und daher [mm]w \ge v+\kgV(r,s)\ge \kgV(r,s)[/mm] im Widerspruch zu
> [mm]w \le \kgV(r,s)-1[/mm].
>
>
> Fazit: [mm]|f(\IZ/n\IZ)|=|f(\IZ/(rs)\IZ)|=\kgV(r,s)\,.[/mm]
>
> Folgerung: Wegen [mm]rs=\ggT(r,s)*\kgV(r,s)[/mm] hat
> [mm]f(\IZ/n\IZ)=f(\IZ/(rs)\IZ)[/mm] genau [mm]n=rs[/mm]
> Elemente, falls [mm]\ggT(r,s)=1[/mm]. Wegen [mm]|\IZ/r\IZ \times \IZ/s\IZ|=rs[/mm]
> ist damit [mm]f\,[/mm] dann surjektiv und als
> surjektive Abbildung zwischen zwei endlichen Mengen zudem
> injektiv, also
> bijektiv. Also gilt für [mm]\ggT(r,s)=1[/mm] in der Tat, dass
>
> [mm]\IZ/(rs)\IZ \cong (\IZ/r\IZ \times \IZ/s\IZ)[/mm].
>
> Gruß,
> Marcel
Hallo,
dein Beweis scheint mir korrekt, wobei er sich meines Erachtens noch abkürzen lässt. Es reicht zu zeigen, dass f ein Gruppenhomomorphismus und der Kern [0] ist.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:29 So 01.01.2017 | | Autor: | Marcel |
Hallo,
> Hallo,
> dein Beweis scheint mir korrekt, wobei er sich meines
> Erachtens noch abkürzen lässt. Es reicht zu zeigen, dass
> f ein Gruppenhomomorphismus und der Kern [0] ist.
Danke für die Kontrolle. Und ja, stimmt, das ist zudem ein guter Hinweis! :)
P.S. Frohes neues Jahr!! :)
Gruß,
Marcel
|
|
|
|
