Lösung quadratischer Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:10 So 16.06.2013 | | Autor: | Killuah |
| Aufgabe | Bestimmen Sie alle Lösungen der quadratischen Kongruenzen:
i) 3x² + 4x - 11 [mm] \equiv [/mm] 0 mod 36
ii) 13x² + 35x +170 [mm] \equiv [/mm] 0 mod 32264 |
Ich verstehe die Idee hinter dem Algorithmus, mit dem man die Lösungen bestimmen soll. Allerdings habe ich so meine gewissen Probleme mit der quadratischen Ergänzung.
Ich habe mal bei der i) angefangen mit:
[mm] 3x^{2} [/mm] + 4 -11 [mm] \equiv [/mm] 0 mod 36 |*3
[mm] \gdw 9x^{2} [/mm] + 12x -33 [mm] \equiv [/mm] 0 mod 36 | binom
[mm] \gdw (3x+2)^{2} [/mm] - 29 [mm] \equiv [/mm] 0 mod 36 | +29
[mm] \gdw (3x+2)^{2} \equiv [/mm] 29 mod 36
Setze y:= (3x+2)
Nun muss ich ja überprüfen, ob [mm] y^{2} \equiv [/mm] 29 mod 36 eine Lösung hat. Dies mache ich mit dem Legendre Symbol und komme auf (29/36)=1. Also hat diese Gleichung eine Lösung.
Allerdings komme ich jetzt nichtmehr weiter.
Ich habe schon die Frage
https://matheraum.de/forum/Quadratische_Kongruenz/t850184
gefunden und mir durchgelesen, aber ich verstehe den Schritt nicht, an dem vermerkt ist: "(Das hat uns eine Proposition verraten)"
Deswegen wäre es nett, wenn mir jemand die Schritte ab dem Punkt, an dem ich bin erklären könnte.
Und zu ii) habe ich folgende Frage:
Ich habe vor dem [mm] x^{2} [/mm] ja eine Primzahl stehen (13). Ich habe mittlerweile schon versucht die gesamte Gleichung mit 13 zu multiplizieren, damit ich auf
[mm] 169x^{2} [/mm] +455x+2210 [mm] \equiv [/mm] 0 mod 32264 komme.
Aber das Problem ist nun, dass 455 ungerade ist und ich somit nicht wirklich mit der quadratischen Ergänzung weiterkomme, da ich auf folgendes komme:
(13x+ [mm] 17,5)^{2} [/mm] +... komme.
Dabei denke ich hat sich ein Fehler bei mir eingeschlichen, da in der EZT (Einführung in die Zahlentheorie) nicht unbedingt Brüche in solch einer Form auftauchen sollten.
Gibt es bei ii) einen Trick, den ich übersehe?
Vielen Dank im Voraus.
PS: Ich möchte die Lösung erarbeiten bzw. einen weiterführenden Tipp bekommen.
PPS: Dies ist mein erster Post hier in dem Forum, ich bitte um konstruktieve Kritik zur Formatierung und Formulierung per privater Nachricht.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:16 So 16.06.2013 | | Autor: | abakus |
> Bestimmen Sie alle Lösungen der quadratischen
> Kongruenzen:
> i) 3x² + 4x - 11 [mm]\equiv[/mm] 0 mod 36
> ii) 13x² + 35x +170 [mm]\equiv[/mm] 0 mod 32264
>
> Ich verstehe die Idee hinter dem Algorithmus, mit dem man
> die Lösungen bestimmen soll. Allerdings habe ich so meine
> gewissen Probleme mit der quadratischen Ergänzung.
> Ich habe mal bei der i) angefangen mit:
>
> [mm]3x^{2}[/mm] + 4 -11 [mm]\equiv[/mm] 0 mod 36 |*3
> [mm]\gdw 9x^{2}[/mm] + 12x -33 [mm]\equiv[/mm] 0 mod 36 | binom
> [mm]\gdw (3x+2)^{2}[/mm] - 29 /equiv 0 mod 36
Falsch umgeformt. Statt -29 muss da -37 stehen.
Gruß Abakus
>| +29
> [mm]\gdw (3x+2)^{2} \equiv[/mm] 0 mod 36
>
> Setze y:= (3x+2)
>
> Nun muss ich ja überprüfen, ob [mm]y^{2} \equiv[/mm] 29 mod 36
> eine Lösung hat. Dies mache ich mit dem Legendre Symbol
> und komme auf (29/36)=1. Also hat diese Gleichung eine
> Lösung.
> Allerdings komme ich jetzt nichtmehr weiter.
>
> Ich habe schon die Frage
> https://matheraum.de/forum/Quadratische_Kongruenz/t850184
> gefunden und mir durchgelesen, aber ich verstehe den
> Schritt nicht, an dem vermerkt ist: "(Das hat uns eine
> Proposition verraten)"
>
> Deswegen wäre es nett, wenn mir jemand die Schritte ab dem
> Punkt, an dem ich bin erklären könnte.
>
> Und zu ii) habe ich folgende Frage:
> Ich habe vor dem [mm]x^{2}[/mm] ja eine Primzahl stehen (13). Ich
> habe mittlerweile schon versucht die gesamte Gleichung mit
> 13 zu multiplizieren, damit ich auf
>
> [mm]169x^{2}[/mm] +455x+2210 [mm]\equiv[/mm] 0 mod 32264 komme.
>
> Aber das Problem ist nun, dass 455 ungerade ist und ich
> somit nicht wirklich mit der quadratischen Ergänzung
> weiterkomme, da ich auf folgendes komme:
>
> (13x+ [mm]17,5)^{2}[/mm] +... komme.
>
> Dabei denke ich hat sich ein Fehler bei mir eingeschlichen,
> da in der EZT (Einführung in die Zahlentheorie) nicht
> unbedingt Brüche in solch einer Form auftauchen sollten.
> Gibt es bei ii) einen Trick, den ich übersehe?
>
> Vielen Dank im Voraus.
>
> PS: Ich möchte die Lösung erarbeiten bzw. einen
> weiterführenden Tipp bekommen.
>
> PPS: Dies ist mein erster Post hier in dem Forum, ich bitte
> um konstruktieve Kritik zur Formatierung und Formulierung
> per privater Nachricht.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
Hallo Killuah,
> Bestimmen Sie alle Lösungen der quadratischen
> Kongruenzen:
> i) 3x² + 4x - 11 [mm]\equiv[/mm] 0 mod 36
> ii) 13x² + 35x +170 [mm]\equiv[/mm] 0 mod 32264
>
>
>
>
> Ich verstehe die Idee hinter dem Algorithmus, mit dem man
> die Lösungen bestimmen soll. Allerdings habe ich so meine
> gewissen Probleme mit der quadratischen Ergänzung.
> Ich habe mal bei der i) angefangen mit:
>
> [mm]3x^{2}[/mm] + 4 -11 [mm]\equiv[/mm] 0 mod 36 |*3
> [mm]\gdw 9x^{2}[/mm] + 12x -33 [mm]\equiv[/mm] 0 mod 36 | binom
> [mm]\gdw (3x+2)^{2}[/mm] - 29 [mm]\equiv[/mm] 0 mod 36 | +29
> [mm]\gdw (3x+2)^{2} \equiv[/mm] 29 mod 36
>
> Setze y:= (3x+2)
>
> Nun muss ich ja überprüfen, ob [mm]y^{2} \equiv[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
29 mod 36
> eine Lösung hat. Dies mache ich mit dem Legendre Symbol
> und komme auf (29/36)=1.
Hier gibt es ein massives Problem:
36 ist keine Primzahl; das Legendre Symbol $\bigleft(\frac{a}{p}} \bigright )$ ist nur modulo Primzahlen definiert.
Das Jacobi-Symbol liefert hier keine abschließende Aussage ob 29 eine Quadratzahl ist.
> Also hat diese Gleichung eine
> Lösung.
> Allerdings komme ich jetzt nichtmehr weiter.
>
> Ich habe schon die Frage
> https://matheraum.de/forum/Quadratische_Kongruenz/t850184
> gefunden und mir durchgelesen, aber ich verstehe den
> Schritt nicht, an dem vermerkt ist: "(Das hat uns eine
> Proposition verraten)"
>
> Deswegen wäre es nett, wenn mir jemand die Schritte ab dem
> Punkt, an dem ich bin erklären könnte.
>
> Und zu ii) habe ich folgende Frage:
> Ich habe vor dem [mm]x^{2}[/mm] ja eine Primzahl stehen (13).
Und was hat das für Folgen für die Aufgabe, dass du diese Eigenschaft hier explizit erwähnst?
> Ich habe mittlerweile schon versucht die gesamte Gleichung mit
> 13 zu multiplizieren, damit ich auf
>
> [mm]169x^{2}[/mm] +455x+2210 [mm]\equiv[/mm] 0 mod 32264 komme.
>
> Aber das Problem ist nun, dass 455 ungerade ist und ich
> somit nicht wirklich mit der quadratischen Ergänzung
> weiterkomme, da ich auf folgendes komme:
>
> (13x+ [mm]17,5)^{2}[/mm] +... komme.
>
> Dabei denke ich hat sich ein Fehler bei mir eingeschlichen,
> da in der EZT (Einführung in die Zahlentheorie) nicht
> unbedingt Brüche in solch einer Form auftauchen sollten.
Das ist alles ziemlich zurückhaltend formuliert. Es gibt in Restklassenringen keine Kommazahlen.Punkt.
Was hier gemeint wäre ist $35 [mm] \cdot 2^{-1}$, [/mm] was es aber in diesem Ring nicht gibt, da 2 hier nicht invertierbar ist.
> Gibt es bei ii) einen Trick, den ich übersehe?
>
> Vielen Dank im Voraus.
>
> PS: Ich möchte die Lösung erarbeiten bzw. einen
> weiterführenden Tipp bekommen.
Als erster Tipp:
Das erste was du hier jeweils tun solltest ist die moduli auf Primzahlpotenzen zu vereinfachen. Und darauf die entsprechenden Sätze draufloszulassen.
Zusammenbasteln der Lösungen dann wieder mit chin. Restsatz.
> PPS: Dies ist mein erster Post hier in dem Forum, ich bitte
> um konstruktieve Kritik zur Formatierung und Formulierung
> per privater Nachricht.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:53 So 16.06.2013 | | Autor: | Killuah |
Zu dem ersten Punkt: abakus hatte mich schon auf den Fehler hingewiesen, dass da sowieso etwas anderes steht, und zwar
[mm] (\bruch{37}{36}). [/mm] Dies entspricht in modulo 36 eben [mm] (\bruch{1}{36})
[/mm]
Damit habe ich dann ja mehr oder weniger automatisch, dass die Gleichung lösbar ist, da z.B. y=1 die Gleichung
[mm] y^{2} \equiv [/mm] 1 mod 36 erfüllen würde.
Zu deinem Tipp:
Wenn ich modulo 36 in die Primfaktoren wie im Hauptsatz zerlege bekomme ich ja
36 = [mm] 2^{2}*3^{2}.
[/mm]
dann habe ich die Gleichung ja in die Form:
[mm] (3x+2)^{2} \equiv [/mm] 1 mod [mm] 2^{2}*3^{2} [/mm] umgewandelt.
Allerdings haben wir (zumindest glaube ich das, da ich nichts in meinem Skript gefunden habe) bisher keine Sätze gemacht, die man auf solch eine Aufgabe loslassen könnte.
Das einzige, was etwa die gleiche Form hat ist eine weitere Aufgabe auf dem Übungsblatt, die wir beweisen sollen, aber dies ist eine andere Sache.
|
|
|
| |
|
> Zu dem ersten Punkt: abakus hatte mich schon auf den Fehler
> hingewiesen, dass da sowieso etwas anderes steht, und zwar
> [mm](\bruch{37}{36}).[/mm] Dies entspricht in modulo 36 eben
> [mm](\bruch{1}{36})[/mm]
> Damit habe ich dann ja mehr oder weniger automatisch, dass
> die Gleichung lösbar ist, da z.B. y=1 die Gleichung
> [mm]y^{2} \equiv[/mm] 1 mod 36 erfüllen würde.
Du scheinst meine Anmerkung nicht zu verstehen. [mm] $(\frac{a}{36})$ [/mm] kann keine Aussage darüber treffen, ob a eine Quadratzahl modulo 36 ist, höchstens darüber, dass es keines ist.
Du benutzt dies hier ja auch gar nicht, sondern gibst explizit eine Wurzel an. Dabei gibt's aber noch ein Problem:
Du hast damit nicht alle möglichen Quadratwurzeln von 1 modulo 36 erwischt, noch weißt du wann das der Fall ist.
> Zu deinem Tipp:
>
> Wenn ich modulo 36 in die Primfaktoren wie im Hauptsatz
> zerlege bekomme ich ja
> 36 = [mm]2^{2}*3^{2}.[/mm]
> dann habe ich die Gleichung ja in die Form:
> [mm](3x+2)^{2} \equiv[/mm] 1 mod [mm]2^{2}*3^{2}[/mm] umgewandelt.
Ich hatte gehofft chin. Restsatz als Stichwort würde ausreichen.
Betrachte deine Gleichung modulo 4 und 9.
Wenn ihr keine weiteren Sätze dazu hast, schau dir erst Lösungen modulo 2und 3 an.
Und nimm die ursprüngliche Gleichung, denn deine erste Umformung ist hier keine Äquivalenzumformung (3 ist nicht invertierbar.)
>
> Allerdings haben wir (zumindest glaube ich das, da ich
> nichts in meinem Skript gefunden habe) bisher keine Sätze
> gemacht, die man auf solch eine Aufgabe loslassen könnte.
> Das einzige, was etwa die gleiche Form hat ist eine weitere
> Aufgabe auf dem Übungsblatt, die wir beweisen sollen,
> aber dies ist eine andere Sache.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:55 Mo 17.06.2013 | | Autor: | SaskiaCl |
Hallo,
ich arbeite grade an einer ähnlichen Aufgabe und habe dasselbe Problem.
Also
[mm] y^2=2 [/mm] mod 9
was sich ja offensichtlich nicht einfach lösen lässt.
Wie muss ich nun fortfahren um ein Ergebnis bekommen ?
Danke
|
|
|
| |
|
Hallo SaskiaCI,
> ich arbeite grade an einer ähnlichen Aufgabe und habe
> dasselbe Problem.
nein, da ist das Problem anders gelagert. 
> Also
> [mm]y^2=2[/mm] mod 9
> was sich ja offensichtlich nicht einfach lösen lässt.
Stimmt.
> Wie muss ich nun fortfahren um ein Ergebnis bekommen ?
Du kannst natürlich den Weg über das Legendresymbol gehen, aber bei so kleinen Modulen geht es oft einfacher direkt - und hier noch einfacher:
[mm] y^2\equiv 2\mod{9}\;\;\Rightarrow\;\;y^2\equiv 2\mod{3}
[/mm]
Hier kann man ohne weiteren Nachweis überblicken, dass 2 kein quadratischer Rest [mm] \mod{3} [/mm] ist.
Deine Aufgabe hat keine Lösung.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:27 Mo 17.06.2013 | | Autor: | SaskiaCl |
>
> Deine Aufgabe hat keine Lösung.
>
> Grüße
> reverend
Nein, ich habe die hier gestellte Aufgabe betrachtet und die hat schon einen Lösung z.B x=11
Also habe ich vorher einen Fehler:
Also die Umformung auf [mm] (3x+2)^2=29 \Rightarrow (3x+2)^2=2 [/mm] mod 9
komisch
|
|
|
| |
|
Hallo,
scheinbar habe ich mich im Verlauf dieses Threads zu diplomatisch ausgedrückt.
Die Umformung ist für die Tonne, da der erste Schritt- die Muktiplikation mit 3- keine Äquivalenzumformung ist, da 3 in diesem Ring nicht invertierbar ist.
Wie man hier sieht vernichtet diese Umformung sogar Lösungen.
Und die ursprüngliche Gleichung hat 2 Lösungen.
|
|
|
|
