simultane Kongruenzen Restsatz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:43 Do 05.02.2009 | | Autor: | lula |
Hallo zusammen,
hätte da eine Frage zum chiesischen Restsatz: Geg. sin zwei Kongruenzen:
[mm] x\equiv [/mm] 4 mod 9
[mm] x\equiv [/mm] 2 mod 5
Jetzt muss ich ja zunächst das kgV bestimmen, also M=45 und dann M1=45:9=5 und M2=45:5=9.
Beim nächsten Schritt müsste ich nun weiter mit dem euklidischen Algorithmus machen, also zunächst ggT(9,5)=1=2*5-9 und dann ggT(5,9)? Das wäre dann ja wieder dasselbe und am Ende müßte ich dann x=-9*-9, was ja definitiv falsch ist. Leider weiß ich nicht, wo ich den Fehler mache, hoffe also auf eure Hilfe...
LG,
Lula
|
|
| |
|
Hallo lula,
Du willst den ![[]](/images/popup.gif) erweiterten euklidischen Algorithmus benutzen, um eine Lösung nach dem chinesischen Restsatz zu bestimmen.
Das geht hier so:
> [mm]x\equiv[/mm] 4 mod 9
> [mm]x\equiv[/mm] 2 mod 5
> Jetzt muss ich ja zunächst das kgV bestimmen, also M=45
> und dann M1=45:9=5 und M2=45:5=9.
> Beim nächsten Schritt müsste ich nun weiter mit dem
> euklidischen Algorithmus machen, also zunächst
> ggT(9,5)=1=2*5-9 und dann ggT(5,9)? Das wäre dann ja wieder
> dasselbe ...
Bis hierhin alles richtig!
Jetzt kannst Du Deine [mm] e_{1,2} [/mm] bestimmen. Es sind die Vielfachen von [mm] M_1 [/mm] und [mm] M_2 [/mm] in der blau markierten Gleichung: [mm] e_1=10, e_2=-9
[/mm]
Damit bekommst Du dann eine Lösung: [mm] 4*10+2*(-9)=22\mod{45}
[/mm]
> und am Ende müßte ich dann x=-9*-9, was ja
> definitiv falsch ist. Leider weiß ich nicht, wo ich den
> Fehler mache, hoffe also auf eure Hilfe...
Den kann ich auch nicht ganz nachvollziehen. Verstehst Du's denn jetzt? Sonst probiers mal mit einem anderen Beispiel und den Wiki-Rechnungen.
> LG,
> Lula
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:23 Do 05.02.2009 | | Autor: | lula |
Ah ja, alles klar, vielen Dank für die schnelle Antwort! Ich dachte, ich muss nochmal den EEA anwenden...
Hätte da noch eine Frage zu nicht-teilerfremden Moduln: Z.B.
1. [mm] x\equiv [/mm] 3 mod 4
2. [mm] x\equiv [/mm] 5 mod 6
Da ggT(6,4)=2 und [mm] 3\equiv [/mm] 5 mod 2 gibt es eine Lösung. Und aus 1. ergibt sich x=3+4j. Wenn ich das in 2. einsetze, erhalte ich:
[mm] 3+4j\equiv [/mm] 5mod 6
[mm] 4j\equiv [/mm] 2 mod 6
[mm] 2j\equiv [/mm] 1 mod 3
Nun meine Frage (falls das bis hierhin richtig ist): Wie bekomme ich die 2 vor dem j weg, ich kann doch jetzt nicht mehr durch 2 teilen? Wie geht das jetzt weiter?
Grüße, Lula
|
|
|
| |
|
Hallo lula,
wieder alles richtig.
Jetzt bist Du hier: [mm] 2j\equiv1\mod{3}
[/mm]
Da gibt es zwei Möglichkeiten. Die vollständige wendet die Entsprechung der Division in der Restklassenrechnung an, das ist die Multiplikation mit dem Inversen, sofern es überhaupt existiert. In diesem Fall ist es offensichtlich, das Inverse zu 2 ist die 2, da [mm] 2*2\equiv1\mod{3}. [/mm] Zufällig kannst Du aus dieser Äquivalenz sogar direkt Dein j ablesen. Eigentlich müsste man aber das Inverse auf beiden Seiten multiplizieren, also:
[mm] 2*2j\equiv2*1\mod{3} \Rightarrow 1j\equiv2\mod{3}
[/mm]
Dabei entsteht der neue Koeffizient 1 vor dem j durch die Multiplikation der dort ursprünglich stehenden 2 mit ihrem Inversen.
Besser zu sehen: sei [mm] 3j\equiv2\mod{13}
[/mm]
Das Inverse von 3 ist 9, da [mm] 3*9=27\equiv1\mod{13}
[/mm]
Deswegen [mm] 3j\equiv2\mod{13}\Rightarrow 9*3j\equiv9*2\mod{13}\Rightarrow 1j\equiv18\mod{13}\Rightarrow j\equiv5\mod{13}
[/mm]
Aber zurück zu Deinem letzten Stand: [mm] 2j\equiv1\mod{3}
[/mm]
Oft praktikabel ist diese Beobachtung: rechts steht eine ungerade Restklasse, auch der Modul ist ungerade...
Also [mm] 2j\equiv1\equiv1+3\mod{3}
[/mm]
Und von da kann man ja leicht weiterrechnen. Bis hier wars auch vollständig erlaubt. Leider funktioniert das nicht immer so gut wie bei der Teilung durch 2, z.B. hier: [mm] 19j\equiv a\mod{23}
[/mm]
Jetzt probiers mal mit a=2,5,17,20...
Grüße,
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:26 Do 05.02.2009 | | Autor: | lula |
Super, danke, das hat mir sehr weiter geholfen!
Zunächst nochmal szu meiner Aufgabe:
Da ja [mm] j\equiv [/mm] 2 mod 3 heisst das, das j=2+3k. Das resubsttituiert:
x=3+4(2+3k)=11+12k. Also: [mm] x\equiv [/mm] 11 mod 12. Die Zahlen für x sind also alle 11+12k!?
Bei der Aufgabe [mm] 19j\equiv a\mod{23} [/mm] erhält man für bei den Primzahlen wegen der Teilerfremdheit immer [mm] j\equiv [/mm] 23*p mod 23, also [mm] j\equiv [/mm] 0 mod 23, also ist das dann die einzige Lösung. Habe ich das so richtig verstanden?
Grüße,
Lula
|
|
|
| |
|
Hallo lula,
> Super, danke, das hat mir sehr weiter geholfen!
> Zunächst nochmal szu meiner Aufgabe:
> Da ja [mm]j\equiv[/mm] 2 mod 3 heisst das, das j=2+3k. Das
> resubsttituiert:
> x=3+4(2+3k)=11+12k. Also: [mm]x\equiv[/mm] 11 mod 12. Die Zahlen
> für x sind also alle 11+12k!?
So isses. ![[ok]](/images/smileys/ok.gif "[ok]")
>
> Bei der Aufgabe [mm]19j\equiv a\mod{23}[/mm] erhält man für bei den
> Primzahlen wegen der Teilerfremdheit immer [mm]j\equiv[/mm] 23*p mod
> 23, also [mm]j\equiv[/mm] 0 mod 23, also ist das dann die einzige
> Lösung. Habe ich das so richtig verstanden?
>
Alle Lösungen dieser Kongruenz bekommst Du,
wenn Du mit den multiplikativ Inversen von 19 modulo 23 durchmultiplizierst.
>
> Grüße,
> Lula
>
Gruß
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:38 Do 05.02.2009 | | Autor: | reverend |
Hallo lula,
noch ein Tipp.
> Alle Lösungen dieser Kongruenz bekommst Du,
> wenn Du mit den multiplikativ Inversen von 19 modulo 23
> durchmultiplizierst.
Zu jedem Rest gibt es genau ein Inverses und damit auch genau eine Lösung.
Dabei kommt [mm] j\equiv 0\mod{23} [/mm] nie vor (außer natürlich, wenn der Rest selbst 0 ist; dann existiert auch kein Inverses).
Grüße,
reverend
|
|
|
|
