Berechnen quadr. Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:53 Fr 17.06.2011 | | Autor: | Olek |
Hey!
Sorry, jetzt kommt ne Kurzvariante. Die schöne ist eben verschwunden, als ich kurz nachdem ich mit allen Formeln fertig war einmal zuviel auf Backspace gedrückt habe & ne Seite zurück gegangen bin <img [mm] src="/editor/extrafiles/images/crash_2.gif" _cke_saved_src="/editor/extrafiles/images/crash_2.gif" title="crash_2.gif" alt="crash_2.gif" [/mm] _cke_realelement="true">
Ich möchte [mm] Y^2=453 [/mm] (mod 1236) lösen. Ich habe die Lösung hier liegen, aber einige Schritte sind mir unklar.
Direkt im ersten wird umgeformt zu
[mm] 3X^2=151 [/mm] (mod 412). Obwohl es einfach aussieht weiß ich nicht, wie das abläuft & welcher Satz benutzt wird.
Alles was dann kommt ist in Ordnung. Erst gegen Ende erhält man:
[mm]X^2\equiv-87 (103)\textrm{ ist } X^2\equiv16(103) \textrm{ und daraus folgt } x\equiv\pm4 (103)[/mm]
Nun verzweifele ich. Ohne jede Argumentation wird [mm]\pm99, \pm107[/mm] als Lösungen mod 412 gefolgert. Ich kann zwar die -4 & +4 mit 103 beliebig kombinieren um auf diese Zahlen zu kommen, aber wie läuft das systematisch? Und mit welchem Satz??
Zu guter Letzt werden die Lösungen nun mod 1236 angegeben. Dazu werden die Lösungen lediglich mit 3 multipliziert & man erhält: [mm]\pm297, \pm321[/mm]
Das verwirrt mich endgültig. Beim Schritt von (mod 103) zu (mod 412) wird vollkommen anders vorgegangen als bei (mod 412) zu (mod 1236). Warum???
Über Hilfe wäre ich sehr Glücklich!
Liebe Grüße,
Olek
|
|
| |
|
Hallo Olek,
> Hey!
> Sorry, jetzt kommt ne Kurzvariante. Die schöne ist eben
> verschwunden, als ich kurz nachdem ich mit allen Formeln
> fertig war einmal zuviel auf Backspace gedrückt habe & ne
> Seite zurück gegangen bin <img
> [mm]src="/editor/extrafiles/images/crash_2.gif" _cke_saved_src="/editor/extrafiles/images/crash_2.gif" title="crash_2.gif" alt="crash_2.gif"[/mm]
> _cke_realelement="true">
>
> Ich möchte [mm]Y^2=453[/mm] (mod 1236) lösen. Ich habe die Lösung
> hier liegen, aber einige Schritte sind mir unklar.
> Direkt im ersten wird umgeformt zu
> [mm]3X^2=151[/mm] (mod 412). Obwohl es einfach aussieht weiß ich
> nicht, wie das abläuft & welcher Satz benutzt wird.
Da ggT(453,1236)=3 muss auch Y durch 3 teilbar sein.
Demnach wird Y=3X gesetzt und es entsteht
[mm]\left(3X\right)^{2}=9X^{2}\equiv 453 \ \operatorname{mod} \ 1236[/mm]
Da in dieser Kongruenz alle 3 Zahlen durch 3 teilbar sind,
kann geschrieben werden:
[mm]3X^{2}\equiv 151 \ \operatorname{mod} \ 412[/mm]
>
> Alles was dann kommt ist in Ordnung. Erst gegen Ende
> erhält man:
> [mm]X^2\equiv-87 (103)\textrm{ ist } X^2\equiv16(103) \textrm{ und daraus folgt } x\equiv\pm4 (103)[/mm]
Daraus erhält man die Lösungen:
[mm]X_{1} = 4+103*k, \ k \in \IZ[/mm]
[mm]X_{2} = -4+103*k, \ k \in \IZ[/mm]
>
> Nun verzweifele ich. Ohne jede Argumentation wird [mm]\pm99, \pm107[/mm]
> als Lösungen mod 412 gefolgert. Ich kann zwar die -4 & +4
> mit 103 beliebig kombinieren um auf diese Zahlen zu kommen,
> aber wie läuft das systematisch? Und mit welchem Satz??
>
> Zu guter Letzt werden die Lösungen nun mod 1236 angegeben.
> Dazu werden die Lösungen lediglich mit 3 multipliziert &
> man erhält: [mm]\pm297, \pm321[/mm]
Nun, da Y=3X sind die Lösungen X mit 3 zu multiplizieren.
> Das verwirrt mich endgültig.
> Beim Schritt von (mod 103) zu (mod 412) wird vollkommen
> anders vorgegangen als bei (mod 412) zu (mod 1236).
> Warum???
>
> Über Hilfe wäre ich sehr Glücklich!
> Liebe Grüße,
> Olek
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:24 Fr 17.06.2011 | | Autor: | Olek |
Allerbesten Dank! Sehr verständlich aufgeschrieben, damit ist alles klar <img src="/editor/extrafiles/images/klatsch.gif" _cke_saved_src="/editor/extrafiles/images/klatsch.gif" title="klatsch.gif" alt="klatsch.gif" _cke_realelement="true">
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:22 Sa 18.06.2011 | | Autor: | Olek |
Hey!
Ich musste eben nochmal feststellen, dass ich die Lösung doch noch nicht ganz nachvollziehen kann.
Wie man [mm] x_1 [/mm] und [mm] x_2 [/mm] erhält erschließt sich mir nicht. Nach deiner Formel wäre auch x=4+103*2=210 eine Lösung. Diese Zahl ist aber nur durch 103, nicht aber durch 412 teilbar.
Wie kommt man denn von dem Modul 103 wieder auf 412?
Viele Grüße,
Olek
|
|
|
| |
|
Hallo Olek,
die Dir vorliegende Lösung scheint nicht vollständig zu sein.
Wenn [mm] X\equiv\pm4\mod{103} [/mm] die vollständige Lösung ist, dann gilt [mm] \mod{412} [/mm] natürlich wegen 412=4*103:
[mm] X\in\{[4],[99],[107],[202],[210],[305],[313],[408]\}, [/mm] oder in der Schreibweise Deiner Lösung [mm] X\equiv\pm4,\pm99,\pm107,\pm202(412).
[/mm]
Es ist doch klar, dass aus zwei Lösungen [mm] \mod{103} [/mm] acht Lösungen [mm] \mod{412} [/mm] werden müssen.
Deine Überlegung ist also vollkommen richtig.
Jetzt das ABER:
Nur vier der obigen Lösungen führen zu einer Lösung der eigentlichen Aufgabe. Insofern ist die Lösung [mm] X\equiv\pm4\mod{103} [/mm] nicht korrekt, wohl aber die Lösung [mm] X\equiv 103\pm4\mod{206} [/mm] bzw.
[mm] X_1=4+(2k+1)*103=107+j*206, j\in\IZ
[/mm]
[mm] X_2=-4+(2k+1)*103=99+j*206, j\in\IZ
[/mm]
Irgendwo in Deiner Musterlösung ist also der Wurm drin.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:18 Sa 18.06.2011 | | Autor: | Olek |
Hi!
Vielen Dank für deine Ausführungen. Dann mache ich mir über dieses Beispiel nun keine weiteren Gedanken mehr - das Prinzip habe ich verstanden.
Die "Musterlösung" ist übrigens ein Beispiel aus dem Bundschuh, Seite 137.
Liebe Grüße,
Olek
|
|
|
|
