Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:46 Do 16.04.2009 | | Autor: | fin129 |
| Aufgabe | | Aufgabe existiert nicht explizit, mir geht es um einen Teil des Beweises des chinesischen Restsatz, siehe unten. |
Zu zeigen wäre allgemein: für simultane Kongruenzen mit teilerfremden Moduln: es existiert eine Lösung, sie ist eindeutig und effizient berechenbar.
Mich interessiert nur der Existenzbeweis.
Mein Problem ist, dass ich die Beweis-Idee nicht kenne, sowie einen Schritt in dem gegebenen Beweis nicht nachvollziehen kann.
Der Beweis soweit:
Sei [mm] $\forall 1\leq [/mm] i [mm] \leq [/mm] k$
[mm]
x\equiv a_i \mod n_i
[/mm]
und sei
[mm]
N=\prod_{i=1}^{k}n_i
[/mm]
sowie alle [mm] $n_i$ [/mm] paarweise teilerfremd.
Sei ausserdem [mm] $m_i \cdot \frac{N}{n_i} \equiv [/mm] 1 [mm] \mod n_i$, [/mm] also [mm] $m_i$ [/mm] multiplikativ invers zu [mm] $\frac{N}{n_i}$ [/mm] in [mm] $\mathbb{Z}_{n_i}$
[/mm]
Betrachten Zahl x mit
[mm]
x\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod N
[/mm]
>Frage 1) wie kommt man auf diese Zahl [mm] $\widehat{=}$ [/mm] Beweis-Idee
[mm]
\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod n_j
[/mm]
>Frage 2) diesen Schritt verstehe ich nicht, wie kommt man von [mm] $\mod [/mm] N$ auf [mm] $\mod n_j$
[/mm]
Der Rest ist mir soweit klar, da [mm] $\frac{N}{n_i}\equiv [/mm] 0 [mm] \mod n_j [/mm] $, [mm] $\forall [/mm] i [mm] \neq [/mm] j$ vereinfacht sich die Summe zu
[mm]
\equiv a_j\cdot m_j \cdot \frac{N}{n_j} \mod n_j
[/mm]
und da [mm] $\frac{N}{n_j}\equiv [/mm] 1 [mm] \mod n_j [/mm] $ ist, folgt
[mm]
\equiv a_j \mod n_j \square
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:21 Fr 17.04.2009 | | Autor: | rainerS |
Hallo!
> Aufgabe existiert nicht explizit, mir geht es um einen Teil
> des Beweises des chinesischen Restsatz, siehe unten.
> Zu zeigen wäre allgemein: für simultane Kongruenzen mit
> teilerfremden Moduln: es existiert eine Lösung, sie ist
> eindeutig und effizient berechenbar.
>
> Mich interessiert nur der Existenzbeweis.
>
> Mein Problem ist, dass ich die Beweis-Idee nicht kenne,
> sowie einen Schritt in dem gegebenen Beweis nicht
> nachvollziehen kann.
>
> Der Beweis soweit:
> Sei [mm]\forall 1\leq i \leq k[/mm]
> [mm]
x\equiv a_i \mod n_i
[/mm]
> und sei
> [mm]
N=\prod_{i=1}^{k}n_i
[/mm]
> sowie alle [mm]n_i[/mm] paarweise teilerfremd.
>
> Sei ausserdem [mm]m_i \cdot \frac{N}{n_i} \equiv 1 \mod n_i[/mm],
> also [mm]m_i[/mm] multiplikativ invers zu [mm]\frac{N}{n_i}[/mm] in
> [mm]\mathbb{Z}_{n_i}[/mm]
>
> Betrachten Zahl x mit
> [mm]
x\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod N
[/mm]
>
> >Frage 1) wie kommt man auf diese Zahl [mm]\widehat{=}[/mm]
> Beweis-Idee
>
> [mm]
\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod n_j
[/mm]
>
> >Frage 2) diesen Schritt verstehe ich nicht, wie kommt man
> von [mm]\mod N[/mm] auf [mm]\mod n_j[/mm]
Das gilt für alle Teiler von N, denn [mm] $a\equiv [/mm] b [mm] \pmod{N}$ [/mm] bedeutet, dass $a-b$ ein Vielfaches von N ist. Also ist $a-b$ ein Vielfaches eines beliebigen Teilers von N.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:37 Fr 17.04.2009 | | Autor: | fin129 |
Danke für die Antwort, konkret auf den Beweis angewandt heißt das dann doch:
$ [mm] x\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod [/mm] N $
Sei [mm] $s_i [/mm] = [mm] a_i\cdot m_i\cdot \frac{N}{n_i}$, [/mm] also
$ [mm] x\equiv \sum_{i=1}^{k}s_i \mod [/mm] N [mm] \Longrightarrow x-\sum_{i=1}^{k}s_i =c_1\cdot [/mm] N$
und da [mm] $n_j \vert [/mm] N$ auch
$ [mm] x-\sum_{i=1}^{k}s_i =c_2\cdot n_j$ [/mm] mit [mm] $c_1, c_2 \in \mathbb{N}$ [/mm] konstant
In Worten: Da x minus die Summe durch N teilbar ist, und [mm] $n_j$ [/mm] Teiler von N ist, ist x minus die Summe auch durch [mm] $n_j$ [/mm] teilbar.
Bitte ggf. korrigieren.
Und Frage 1) bzgl. Beweis-Idee ist immer noch offen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:16 Fr 17.04.2009 | | Autor: | rainerS |
Hallo!
> Danke für die Antwort, konkret auf den Beweis angewandt
> heißt das dann doch:
>
> [mm]x\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod N[/mm]
>
> Sei [mm]s_i = a_i\cdot m_i\cdot \frac{N}{n_i}[/mm], also
> [mm]x\equiv \sum_{i=1}^{k}s_i \mod N \Longrightarrow x-\sum_{i=1}^{k}s_i =c_1\cdot N[/mm]
>
> und da [mm]n_j \vert N[/mm] auch
> [mm]x-\sum_{i=1}^{k}s_i =c_2\cdot n_j[/mm] mit [mm]c_1, c_2 \in \mathbb{N}[/mm]
> konstant
>
> In Worten: Da x minus die Summe durch N teilbar ist, und
> [mm]n_j[/mm] Teiler von N ist, ist x minus die Summe auch durch [mm]n_j[/mm]
> teilbar.
Richtig.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:50 Fr 17.04.2009 | | Autor: | fin129 |
Bleibt noch meine erste Frage,
Betrachten Zahl x mit
[mm]
x\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod N
[/mm]
>Frage 1) wie kommt man auf diese Zahl [mm] $\widehat{=}$ [/mm] Beweis-Idee
Edit: Ich konkretisiere ein wenig, wie stellt man eine Zahl auf, die alle simultanen o.g. Kongruenzen erfüllt. Das Ergenis selbst steht ja schon da, der Beweis auch, aber weswegen soll x gerade von dieser Form sein / was ist der eigentliche Grundgedanke des Beweises?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:23 Sa 18.04.2009 | | Autor: | felixf |
Hallo!
> Betrachten Zahl x mit
> [mm]
x\equiv \sum_{i=1}^{k}a_i\cdot m_i \cdot \frac{N}{n_i} \mod N
[/mm]
>
> >Frage 1) wie kommt man auf diese Zahl [mm]\widehat{=}[/mm]
> Beweis-Idee
>
> Edit: Ich konkretisiere ein wenig, wie stellt man eine Zahl
> auf, die alle simultanen o.g. Kongruenzen erfüllt. Das
> Ergenis selbst steht ja schon da, der Beweis auch, aber
> weswegen soll x gerade von dieser Form sein / was ist der
> eigentliche Grundgedanke des Beweises?
Die Idee ist, dass [mm] $x_i [/mm] := [mm] m_i \cdot \frac{N}{n_i}$ [/mm] die Gleichungen [mm] $x_i \equiv [/mm] 1 [mm] \pmod{n_i}$ [/mm] und [mm] $x_i \equiv [/mm] 0 [mm] \pmod{n_j}$ [/mm] fuer $j [mm] \neq [/mm] i$ erfuellt. (Zweiteres ist klar, da [mm] $n_j$ [/mm] ein Teiler von [mm] $\frac{N}{n_i}$ [/mm] und dadurch auch von [mm] $m_i \cdot \frac{N}{n_i}$ [/mm] ist. Fuer das erstere braucht man etwas mehr Arbeit.)
Damit hat man naemlich sozusagen eine ``Basis'', die man mit den Koeffizienten [mm] $a_i$ [/mm] linear kombinieren kann um das gewuenschte $x$ zu erhalten.
Eine andere Version des Chinesischen Restsatzes sagt ja auch [mm] $\IZ/N\IZ \cong \IZ/n_1\IZ \times \dots \times \IZ/n_k\IZ$. [/mm] Auf der linken Seite suchst du $x$, das auf der rechten Seite den Vektor [mm] $(a_1, \dots, a_k)$ [/mm] ergibt. Und [mm] $m_i \cdot \frac{N}{n_i}$ [/mm] auf der linken Seite ergibt gerade $(0, [mm] \dots, [/mm] 0, 1, 0, [mm] \dots, [/mm] 0)$ mit $1$ an der $i$-ten Stelle.
Hilft dir das weiter?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:35 Sa 18.04.2009 | | Autor: | fin129 |
Hm, es handelt sich also um eine Art Linearkombination von den [mm] $a_i$ [/mm] derart, dass die Kongruenzen erfüllt sind?
Das muss ich mal durchdenken, danke.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Mi 22.04.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
