Chinesischer Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | x [mm] \equiv [/mm] 2 mod 20
x [mm] \equiv [/mm] 6 mod 9
x [mm] \equiv [/mm] 5 mod 7
Berechne x |
Also mit dem chinesischen Restsatz:
m= 20*9*7=1260
[mm] m_1= [/mm] 1260/20= 63
[mm] m_2 [/mm] = 1260/9=140
[mm] m_3 [/mm] = 1260/7= 180
Jetzt komm ich nicht weiter...
Im Skript steht suche [mm] \tilde M_j [/mm] mit [mm] m_j* \tilde M_j \equiv [/mm] 1 mod [mm] m_j [/mm]
Aber wie mache ich das?
Vielen Dank für die Hilfe
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:22 So 25.10.2009 | | Autor: | felixf |
Halo!
> x [mm]\equiv[/mm] 2 mod 20
> x [mm]\equiv[/mm] 6 mod 9
> x [mm]\equiv[/mm] 5 mod 7
>
> Berechne x
> Also mit dem chinesischen Restsatz:
>
> m= 20*9*7=1260
>
> [mm]m_1=[/mm] 1260/20= 63
> [mm]m_2[/mm] = 1260/9=140
> [mm]m_3[/mm] = 1260/7= 180
Erstmal: setze [mm] $n_1 [/mm] = 20$, [mm] $n_2 [/mm] = 9$ und [mm] $n_3 [/mm] = 7$. Dann ist [mm] $m_i [/mm] = 1260 / [mm] n_i$.
[/mm]
> Jetzt komm ich nicht weiter...
>
> Im Skript steht suche [mm]\tilde M_j[/mm] mit [mm]m_j* \tilde M_j \equiv[/mm]
> 1 mod [mm]m_j[/mm]
Da hast du dich aber vertippt: modulo [mm] $m_j$ [/mm] ist [mm] $m_j [/mm] * [mm] \tilde{M_j}$ [/mm] immer 0 und niemals 1 -- es sei denn [mm] $m_j [/mm] = [mm] \pm [/mm] 1$.
Wenn du schon nach dem Skript vorgehen willst, schau mal genauer nach was da steht.
Insgesamt willst du ja [mm] $e_1, e_2, e_3$ [/mm] finden mit [mm] $e_i \equiv [/mm] 1 [mm] \pmod{n_i}$ [/mm] und [mm] $e_i \equiv [/mm] 0 [mm] \pmod{n_j}$ [/mm] mit $j [mm] \neq [/mm] i$. Zusammenfassend: [mm] $e_i \equiv [/mm] 1 [mm] \pmod{n_i}$ [/mm] und [mm] $e_i \equiv [/mm] 0 [mm] \pmod{m_i}$; [/mm] zweiteres heisst, dass [mm] $e_i$ [/mm] ein Vielfaches von [mm] $m_i$ [/mm] sein muss. Du kannst also ein [mm] $M_i$ [/mm] suchen mit [mm] $m_i M_i \equiv [/mm] 1 [mm] \pmod{n_i}$: [/mm] dann ist [mm] $e_i [/mm] := [mm] m_i M_i$ [/mm] ein Vielfaches von [mm] $m_i$.
[/mm]
Vermutlich steht das auch so in deinem Skript, also dass [mm] $m_j \tilde{M_j} \equiv [/mm] 1 [mm] \pmod{n_j}$ [/mm] sein soll und nicht modulo [mm] $m_j$!
[/mm]
> Aber wie mache ich das?
Stichwort: Erweiterter Euklidischer Algorithmus.
(Es bedeutet [mm] $m_j \tilde{M_j} \equiv [/mm] 1 [mm] \pmod{n_j}$ [/mm] ja [mm] $m_j \tilde{M_j} [/mm] + x [mm] n_j [/mm] = 1$ fuer ein $x [mm] \in \IZ$.)
[/mm]
LG Felix
|
|
|
|
