Simultane Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:33 Mo 13.06.2011 | | Autor: | clemenum |
| Aufgabe | Man löse folgendes Kongruenzsystem und gebe die Lösungen inkongruent modulo [mm] $20\cdot 21\cdot [/mm] 23$ an:
[mm] $7x\equiv [/mm] 8(20)$
[mm] $5x\equiv [/mm] -6(21) $
[mm] $9x\equiv [/mm] 13(23)$ |
Nun, im Sinne des chin. Restsatzes empfiehlt es sich ersichtlich, dass man $x$ in einfacher Vielfachheit stehen hat (wie man durch ein wenig geschickte Anwendung der Kongruenzsätze erhält), also:
I [mm] $x\equiv [/mm] 4(20) $
II [mm] $x\equiv [/mm] 3(21)$
III $ x [mm] \equiv [/mm] 4(23) $
__________________
Nun ermittle ich die [mm] $M_i$:
[/mm]
[mm] $M_1= [/mm] M/20 = 483, [mm] M_2= [/mm] M/21=460, [mm] M_3= [/mm] 420$
Ich schreibe nun (im Sinne des (erweiterten) euklidischen Algorithmus) die Vielfachsummendarstellungen fertig auf:
1. [mm] $1=7\cdot [/mm] 483 [mm] -169\cdot [/mm] 20$ [mm] $\Rightarrow e_1 [/mm] = -3380 $
2. $1= [mm] 10\cdot [/mm] 460 [mm] -219\cdot [/mm] 21$ [mm] $\Rightarrow e_2 [/mm] = -4599$
3. $1= [mm] 4\cdot 420-73\cdot [/mm] 23$ [mm] $\Rightarrow e_3 [/mm] = -1679$
Nun, dem (konstruktiven) Beweis entnehmend, müsste DIE Lösung modulo $M$ nun
[mm] $e_1\cdot [/mm] 4 + [mm] e_2\cdot [/mm] 3 + [mm] e_3 \cdot [/mm] 4,$ also -34033 sein,
was aber durch einen Blick erkennend schon nicht stimmen kann, da $ -33037$ nicht durch 2 und damit erstrecht nicht durch 20 teilbar ist.
Meine Frage: Woran hapert es, verrechnet habe ich mich nicht. Ich habe es sogar mit Computeralgebrasystemen nachgerechnet und es kam dasgleiche heraus wie beim händischen Rechnen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:05 Mo 13.06.2011 | | Autor: | felixf |
Moin!
> Man löse folgendes Kongruenzsystem und gebe die Lösungen
> inkongruent modulo [mm]20\cdot 21\cdot 23[/mm] an:
> [mm]7x\equiv 8(20)[/mm]
> [mm]5x\equiv -6(21)[/mm]
> [mm]9x\equiv 13(23)[/mm]
> Nun, im Sinne des chin. Restsatzes
> empfiehlt es sich ersichtlich, dass man [mm]x[/mm] in einfacher
> Vielfachheit stehen hat (wie man durch ein wenig geschickte
> Anwendung der Kongruenzsätze erhält), also:
> I [mm]x\equiv 4(20)[/mm]
> II [mm]x\equiv 3(21)[/mm]
> III [mm]x \equiv 4(23)[/mm]
> __________________
> Nun ermittle ich die [mm]M_i[/mm]:
> [mm]M_1= M/20 = 483, M_2= M/21=460, M_3= 420[/mm]
>
> Ich schreibe nun (im Sinne des (erweiterten) euklidischen
> Algorithmus) die Vielfachsummendarstellungen fertig auf:
> 1. [mm]1=7\cdot 483 -169\cdot 20[/mm] [mm]\Rightarrow e_1 = -3380 [/mm]
> 2.
> [mm]1= 10\cdot 460 -219\cdot 21[/mm] [mm]\Rightarrow e_2 = -4599[/mm]
> 3. [mm]1= 4\cdot 420-73\cdot 23[/mm]
> [mm]\Rightarrow e_3 = -1679[/mm]
> Nun, dem (konstruktiven) Beweis entnehmend, müsste DIE
> Lösung modulo [mm]M[/mm] nun
> [mm]e_1\cdot 4 + e_2\cdot 3 + e_3 \cdot 4,[/mm] also -34033 sein,
> was aber durch einen Blick erkennend schon nicht stimmen
> kann, da [mm]-33037[/mm] nicht durch 2 und damit erstrecht nicht
> durch 20 teilbar ist.
>
> Meine Frage: Woran hapert es, verrechnet habe ich mich
> nicht.
Du hast die [mm] $e_i$ [/mm] falsch berechnet! Du musst [mm] $e_1$ [/mm] nicht als $-169 [mm] \cdot [/mm] 20$ waehlen, sondern als $7 [mm] \cdot [/mm] 483$. Das ist naemlich kongruent zu 1 modulo 20, und kongruent zu 0 modulo 21 und 23.
Genauso dann bei [mm] $e_2$ [/mm] und [mm] $e_3$.
[/mm]
LG Felix
|
|
|
|
