Simultane Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Seien [mm] $a_1, a_2 \in \IZ$ [/mm] und [mm] $n,m\in \IZ_{>0}$
[/mm]
Zeigen sie:
Die simultane Kongruenzen
[mm] $x\equiv a_1 \mbox{mod } n_1$
[/mm]
[mm] $x\equiv a_2 \mbox{mod } n_2$
[/mm]
sind genau dann lösbar, wenn
[mm] $a_1 [/mm] - [mm] a_2 \equiv [/mm] 0 [mm] \mbox{ mod } ggT(n_1,n_2)$
[/mm]
Die Lösung ist eindeutig modulo dem [mm] kgV(n_1,n_2) [/mm] |
[mm] "\Rightarrow"
[/mm]
In diese Richtung muss ich doch zeigen, dass weil die simultane Kongruenz lösbar ist, [mm] a_1 [/mm] - [mm] a_2 \equiv [/mm] 0 mod [mm] ggT(n_1,n_2) [/mm] ist, oder?
Also ist meine Voraussetzung, die simultane kongruenz ist lösbar.
Da das so ist, weiß ich, dass der [mm] ggT(n_1,n_2) [/mm] = 1
Ich weiß außerdem, dass [mm] n_1|(x-a_1) [/mm] und [mm] n_2|(x-a_2)
[/mm]
Weiter weiß ich aber nicht. Kann mir jemand einen Tipp geben?
Für die Rückrichtung hab ich mir gar nichts überlegt. Ich verstehe den Ausdruck nicht ganz was 0 modulo [mm] ggT(n_1,n_2) [/mm] bedeuten soll. Also speziell das 0.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:40 So 23.01.2011 | | Autor: | felixf |
Moin!
> Seien [mm]a_1, a_2 \in \IZ[/mm] und [mm]n,m\in \IZ_{>0}[/mm]
> Zeigen sie:
> Die simultane Kongruenzen
> [mm]x\equiv a_1 \mbox{mod } n_1[/mm]
> [mm]x\equiv a_2 \mbox{mod } n_2[/mm]
>
> sind genau dann lösbar, wenn
> [mm]a_1 - a_2 \equiv 0 \mbox{ mod } ggT(n_1,n_2)[/mm]
>
> Die Lösung ist eindeutig modulo dem [mm]kgV(n_1,n_2)[/mm]
> [mm]"\Rightarrow"[/mm]
>
> In diese Richtung muss ich doch zeigen, dass weil die
> simultane Kongruenz lösbar ist, [mm]a_1[/mm] - [mm]a_2 \equiv[/mm] 0 mod
> [mm]ggT(n_1,n_2)[/mm] ist, oder?
Ja.
> Also ist meine Voraussetzung, die simultane kongruenz ist
> lösbar.
>
> Da das so ist, weiß ich, dass der [mm]ggT(n_1,n_2)[/mm] = 1
Woher weisst du das? Das stimmt doch gar nicht!
> Ich weiß außerdem, dass [mm]n_1|(x-a_1)[/mm] und [mm]n_2|(x-a_2)[/mm]
Das brauchst du. Der ggT teilt ja sowohl [mm] $n_1$ [/mm] wie auch [mm] $n_2$, [/mm] und somit (jetzt etwas umformen) auch [mm] $a_1 [/mm] - [mm] a_2$.
[/mm]
> Für die Rückrichtung hab ich mir gar nichts überlegt.
> Ich verstehe den Ausdruck nicht ganz was 0 modulo
> [mm]ggT(n_1,n_2)[/mm] bedeuten soll. Also speziell das 0.
Na, das bedeutet doch einfach, dass [mm] $a_1 \equiv a_2 \pmod{ggT(n_1, n_2)}$ [/mm] ist. Also dass [mm] $a_2 [/mm] - [mm] a_1$ [/mm] durch [mm] $ggT(n_1, n_2)$ [/mm] teilbar ist.
Sei $p$ ein Primteiler von [mm] $n_1 n_2$. [/mm] Sei $a$ maximal mit [mm] $p^a \mid n_1$ [/mm] und $b$ maximal mit [mm] $p^b \mid n_2$. [/mm] Sei weiterhin $c$ maximal mit [mm] $p^c \mid ggT(n_1, n_2)$ [/mm] und $d$ maximal mit [mm] $p^d \mid kgV(n_1, n_2)$. [/mm] Was kannst du ueber $c$ und $d$ in Relation zu $a$ und $b$ aussagen?
Ueberlege dir jetzt, dass es eine Loesung [mm] $x_p$ [/mm] gibt mit [mm] $x_p \equiv a_1 \pmod{p^a}$ [/mm] und [mm] $x_p \equiv a_2 \pmod{p^b}$, [/mm] und benutze dafuer, dass [mm] $a_1 [/mm] - [mm] a_2 \equiv [/mm] 0 [mm] \pmod{p^c}$ [/mm] gilt. Zeige weiterhin, dass diese Loesung modulo [mm] $p^d$ [/mm] eindeutig ist.
Schliesslich setzt du alle [mm] $x_p$ [/mm] mit dem chinesischen Restsatz zu einer Loesung $x$ von $x [mm] \equiv a_1 \pmod{n_1}$ [/mm] und $x [mm] \equiv a_2 \pmod{n_2}$ [/mm] zusammen.
LG Felix
|
|
|
| |
|
> Moin!
>
> > Seien [mm]a_1, a_2 \in \IZ[/mm] und [mm]n,m\in \IZ_{>0}[/mm]
> > Zeigen
> sie:
> > Die simultane Kongruenzen
> > [mm]x\equiv a_1 \mbox{mod } n_1[/mm]
> > [mm]x\equiv a_2 \mbox{mod } n_2[/mm]
>
> >
> > sind genau dann lösbar, wenn
> > [mm]a_1 - a_2 \equiv 0 \mbox{ mod } ggT(n_1,n_2)[/mm]
> >
> > Die Lösung ist eindeutig modulo dem [mm]kgV(n_1,n_2)[/mm]
> > [mm]"\Rightarrow"[/mm]
> >
> > In diese Richtung muss ich doch zeigen, dass weil die
> > simultane Kongruenz lösbar ist, [mm]a_1[/mm] - [mm]a_2 \equiv[/mm] 0 mod
> > [mm]ggT(n_1,n_2)[/mm] ist, oder?
>
> Ja.
>
> > Also ist meine Voraussetzung, die simultane kongruenz ist
> > lösbar.
> >
> > Da das so ist, weiß ich, dass der [mm]ggT(n_1,n_2)[/mm] = 1
>
> Woher weisst du das? Das stimmt doch gar nicht!
In meiner Definition des chinesischen Restsatzes heißt es, wenn [mm] n_1,...,n_r [/mm] teilerfremd sind, ist die simultane Kongruenz lösbar.
Beim ggT heißt es: Sind zwei Zahlen a,b teilerfremd gilt ggT(a,b)=1
Daher dachte ich, dass [mm] ggT(n_1,n_2)=1
[/mm]
Ist das falsch????
>
> > Ich weiß außerdem, dass [mm]n_1|(x-a_1)[/mm] und [mm]n_2|(x-a_2)[/mm]
>
> Das brauchst du. Der ggT teilt ja sowohl [mm]n_1[/mm] wie auch [mm]n_2[/mm],
> und somit (jetzt etwas umformen) auch [mm]a_1 - a_2[/mm].
>
Mit dem Umformen hab ich noch meine Probleme.
Wenn [mm] n_1|(x-a_1) [/mm] und [mm] n_2|(x-a_2) [/mm] und der ggT [mm] n_1 [/mm] und [mm] n_2 [/mm] teilt, komm ich auf
[mm] n_1* n_2| (x-a_1)*(x-a_2)
[/mm]
was mich nicht weiter bringt.
Da der ggT [mm] n_1 [/mm] und [mm] n_2 [/mm] teilt kann ich ja auch sagen, dass
[mm] ggT(n_1,n_2)|(x-a_1) [/mm] und [mm] ggT(n_1,n_2)|(x-a_2)
[/mm]
dann folgt daraus
[mm] x\equiv a_1 \mbox{mod } ggT(n_1,n_2)
[/mm]
[mm] x\equiv a_2 \mbox{mod } ggT(n_1,n_2)
[/mm]
kann ich dann
[mm] x\equiv a_1 \mbox{mod } ggT(n_1,n_2)
[/mm]
[mm] \gdw -a_1\equiv [/mm] x [mm] \mbox{mod } ggT(n_1,n_2)
[/mm]
[mm] \gdw -a_1\equiv a_2 \mbox{mod } ggT(n_1,n_2) \mbox{mod } ggT(n_1,n_2)
[/mm]
[mm] \gdw -a_1-a_2 \equiv [/mm] 0 [mm] \mbox{mod } ggT(n_1,n_2)
[/mm]
Sieht irgendwie nach großen quatsch aus.
wie kann ich das Umformen?
Bei
[mm] a_1 \mbox{mod } ggT(n_1,n_2)\equiv a_2 \mbox{mod } ggT(n_1,n_2)
[/mm]
kommt das gleiche raus, was nicht verwunderlich ist.
Wo ist mein Denkfehler??
Danke
Dr. G.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Di 25.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
> > Für die Rückrichtung hab ich mir gar nichts überlegt.
> > Ich verstehe den Ausdruck nicht ganz was 0 modulo
> > [mm]ggT(n_1,n_2)[/mm] bedeuten soll. Also speziell das 0.
>
> Na, das bedeutet doch einfach, dass [mm]a_1 \equiv a_2 \pmod{ggT(n_1, n_2)}[/mm]
> ist. Also dass [mm]a_2 - a_1[/mm] durch [mm]ggT(n_1, n_2)[/mm] teilbar ist.
Das hab ich verstanden...
>
> Sei [mm]p[/mm] ein Primteiler von [mm]n_1 n_2[/mm]. Sei [mm]a[/mm] maximal mit [mm]p^a \mid n_1[/mm]
> und [mm]b[/mm] maximal mit [mm]p^b \mid n_2[/mm].
Warum ein Primteiler?
Ist nicht [mm] n_j=\produkt_{i=1}^{s}p_i^{r_ji} [/mm] mit [mm] p_i [/mm] prim ??
(Was bedeutet a maximal?)
>Sei weiterhin [mm]c[/mm] maximal mit
> [mm]p^c \mid ggT(n_1, n_2)[/mm] und [mm]d[/mm] maximal mit [mm]p^d \mid kgV(n_1, n_2)[/mm].
[mm] ggT(n_1,n_2)=\produkt_{i=1}^{s}p_i^{min\{r_ji\}}
[/mm]
[mm] kgv(n_1,n_2)=\produkt_{i=1}^{s}p_i^{max\{r_ji\}}
[/mm]
> Was kannst du ueber [mm]c[/mm] und [mm]d[/mm] in Relation zu [mm]a[/mm] und [mm]b[/mm]
> aussagen?
Naja, dass [mm] c\le [/mm] a,b bzw. das min(a,b)
und [mm] d\ge [/mm] a,b bzw. das max(a,b)
wobei ich immer noch das Problem habe mir da nur einen Primteiler vorzustellen.
>
> Ueberlege dir jetzt, dass es eine Loesung [mm]x_p[/mm] gibt mit [mm]x_p \equiv a_1 \pmod{p^a}[/mm]
> und [mm]x_p \equiv a_2 \pmod{p^b}[/mm], und benutze dafuer, dass [mm]a_1 - a_2 \equiv 0 \pmod{p^c}[/mm]
> gilt. Zeige weiterhin, dass diese Loesung modulo [mm]p^d[/mm]
> eindeutig ist.
Ich glaub, dass ich das nur verstehe (also ich persönlich) wenn ich die Hinrichtung verstanden habe.
>
> Schliesslich setzt du alle [mm]x_p[/mm] mit dem chinesischen
> Restsatz zu einer Loesung [mm]x[/mm] von [mm]x \equiv a_1 \pmod{n_1}[/mm] und
> [mm]x \equiv a_2 \pmod{n_2}[/mm] zusammen.
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Di 25.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
