Quadratische Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:44 Mi 14.12.2011 | | Autor: | Loko |
| Aufgabe | Lösen der quadratischen Kongruenzen:
a) [mm] x^{2} [/mm] + x + 1 [mm] \equiv [/mm] 0 (mod 7)
b) [mm] x^{2} [/mm] + 5x + 1 [mm] \equiv [/mm] 0 (mod 7)
c) [mm] x^{2} [/mm] + 3x + 1 [mm] \equiv [/mm] 0 (mod 7) |
Ich habe mich bisher nur an der a) versucht.
Also zunächst habe ich das alles mal etwas handlicher umgeformt:
[mm] x^{2} [/mm] + x + 1 [mm] \equiv 4x^{2} [/mm] + 4x + 4 [mm] \equiv [/mm] 0 (mod 7)
[mm] \gdw (2x+1)^{2} \equiv [/mm] -3 [mm] \equiv [/mm] 4 (mod 7)
[mm] y^{2} [/mm] := [mm] (2x+1)^{2}.
[/mm]
So kann ich dann über (4|7) prüfen ob es für y eine Lösung gibt.
(4|7) = (2|7)(2|7) = [mm] (-1)^{\bruch{7^{2}-1}{8}}*(-1)^{\bruch{7^{2}-1}{8}}
[/mm]
= 1
[mm] \Rightarrow [/mm] 4 ist quadratischer Rest von 7, und so besitzt y eine Lösung.
In der Vorlesung hatten wir dann so weiter gemacht:
prüfe p(mod 4) = ?:
7 [mm] \equiv [/mm] 3 (mod 4)
[mm] \Rightarrow y^{2} \equiv \pm 4^{\bruch{7+1}{4}} [/mm] (mod 7) (Das hat uns eine Proposition verraten)
[mm] \equiv [/mm] 2 (mod 7).
Jetzt weiss ich also, dass [mm] y^{2} \equiv \pm [/mm] 2 (mod 7) ist.
Wie mach ich denn jetzt weiter?
Wie kann ich darüber auf die Lösung für [mm] (2x+1)^{2} [/mm] kommen?
Und ist der Weg bis hierher so sinnvoll?
Vielen Dank und liebe Grüsse
Loko
|
|
| |
|
> Lösen der quadratischen Kongruenzen:
> a) [mm]x^{2}[/mm] + x + 1 [mm]\equiv[/mm] 0 (mod 7)
> b) [mm]x^{2}[/mm] + 5x + 1 [mm]\equiv[/mm] 0 (mod 7)
> c) [mm]x^{2}[/mm] + 3x + 1 [mm]\equiv[/mm] 0 (mod 7)
> Ich habe mich bisher nur an der a) versucht.
>
> Also zunächst habe ich das alles mal etwas handlicher
> umgeformt:
>
> [mm]x^{2}[/mm] + x + 1 [mm]\equiv 4x^{2}[/mm] + 4x + 4 [mm]\equiv[/mm] 0 (mod 7)
> [mm]\gdw (2x+1)^{2} \equiv[/mm] -3 [mm]\equiv[/mm] 4 (mod 7)
>
> [mm]y^{2}[/mm] := [mm](2x+1)^{2}.[/mm]
>
> So kann ich dann über (4|7) prüfen ob es für y eine
> Lösung gibt.
>
> (4|7) = (2|7)(2|7) =
> [mm](-1)^{\bruch{7^{2}-1}{8}}*(-1)^{\bruch{7^{2}-1}{8}}[/mm]
> = 1
> [mm]\Rightarrow[/mm] 4 ist quadratischer Rest von 7, und so besitzt
> y eine Lösung.
>
> In der Vorlesung hatten wir dann so weiter gemacht:
> prüfe p(mod 4) = ?:
> 7 [mm]\equiv[/mm] 3 (mod 4)
> [mm]\Rightarrow y^{2} \equiv \pm 4^{\bruch{7+1}{4}}[/mm] (mod 7)
> (Das hat uns eine Proposition verraten)
> [mm]\equiv[/mm] 2 (mod 7).
>
> Jetzt weiss ich also, dass [mm]y^{2} \equiv \pm[/mm] 2 (mod 7) ist.
>
> Wie mach ich denn jetzt weiter?
> Wie kann ich darüber auf die Lösung für [mm](2x+1)^{2}[/mm]
Jetzt fehlt doch nur noch die Rücksubstitution, d.h. du bestimmst die zwei Lösungen für x aus der Gleichung [mm] 2x+1=y=\pm [/mm] 2,
also [mm] 2x_1+1=2 [/mm] und [mm] 2x_2+1=-2
[/mm]
> kommen?
> Und ist der Weg bis hierher so sinnvoll?
das scheint mir alles korrekt
>
> Vielen Dank und liebe Grüsse
>
> Loko
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:59 Mi 14.12.2011 | | Autor: | Loko |
Vielen Dank schonmal für die schnelle Antwort!
Nur ist doch [mm] y^{2} \equiv \pm [/mm] 2? Wie kann ich da das "hoch 2" auflösen?
Tut mir leid.. ich seh noch nicht, wie die Rücksubstitution funktioniert....
Viele Grüsse! :)
(Ich hab die Nächste Stunde Vorlesung..)
Danke nochmal!
|
|
|
| |
|
> Vielen Dank schonmal für die schnelle Antwort!
>
> Nur ist doch [mm]y^{2} \equiv \pm[/mm] 2? Wie kann ich da das "hoch
> 2" auflösen?
Das hast du doch schon getan! Aus [mm] y^2=4 [/mm] hast du [mm] y=\pm [/mm] 2 bestimmt.
> Tut mir leid.. ich seh noch nicht, wie die
> Rücksubstitution funktioniert....
Das ist dann "nur noch" das Auflösen einer linearen Kongruenz.
Für die eine Lösung [mm] 2=2x+1\Leftrightarrow 4\m 2=4\m 2x+4\Leftrightarrow x+4=1\Leftrightarrow [/mm] x=4
durch Multiplikation mit dem Inversen [mm] 2^{-1}=4
[/mm]
>
> Viele Grüsse! :)
>
> (Ich hab die Nächste Stunde Vorlesung..)
>
> Danke nochmal!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:33 Do 15.12.2011 | | Autor: | Loko |
Vielen, vielen Dank! Heute hab ichs dann auch endlich verstanden :-D
Gut zur a) y [mm] \equiv \pm [/mm] 2 (mod 7)
[mm] \Rightarrow [/mm] 2x + 1 [mm] \equiv \pm [/mm] 2 (mod 7)
[mm] \gdw [/mm] x + 4 [mm] \equiv \pm [/mm] 1 (mod 7)
[mm] \gdw [/mm] x + 4 [mm] \equiv [/mm] 1 (mod 7) [mm] \Rightarrow [/mm] x [mm] \equiv [/mm] 4 und x + 4 [mm] \equiv [/mm] -1 [mm] \equiv [/mm] 6 [mm] \Rightarrow [/mm] x [mm] \equiv [/mm] 2
b) [mm] x^{2} [/mm] + 5x + 1 [mm] \equiv [/mm] 0 (mod 7)
[mm] \gdw 4x^{2} [/mm] + 20x + 4 [mm] \equiv [/mm] 0 (mod 7)
[mm] \gdw 4x^{2} [/mm] - 8x + 4 [mm] \equiv [/mm] 0 (mod 7)
[mm] \gdw [/mm] (2x - [mm] 2)^{2} \equiv [/mm] 0 (mod 7)
[mm] \Rightarrow [/mm] 2x - 2 [mm] \equiv [/mm] 0 (mod 7)
[mm] \gdw [/mm] x [mm] \equiv [/mm] 1 (mod 7).
War's das hierbei schon? Oder gibt es auch hier mehr als eine Lösung?
Ich erinnere mich nicht mehr, wie das war wenn die Legendre Zahl 0 war,
und finde es auch nicht in der Vorlesung.
Aber eigentlich sieht es so ja ganz hübsch aus ;)
c) [mm] x^{2} [/mm] + 3x + 1 [mm] \equiv [/mm] 0 (mod 7)
[mm] \gdw 4x^{2} [/mm] + 12x + 4 [mm] \equiv [/mm] 0 (mod 7)
[mm] \gdw [/mm] (2x + [mm] 3)^{2} [/mm] + 2 [mm] \equiv [/mm] 0 (mod 7) (wg 4 [mm] \equiv [/mm] 11)
[mm] \gdw [/mm] (2x + [mm] 3)^{2} \equiv [/mm] -2 [mm] \equiv [/mm] 5 (mod 7)
y := 2x + 3
[mm] y^{2} \equiv [/mm] 5 (mod 7) hat Lösung, gdw (5|7) [mm] \ge [/mm] 0
(5|7) = [mm] (-1)^{\bruch{5-1}{2} \bruch{7-1}{2}} [/mm] * (7|5)
= (7|5) = (2|5) = [mm] (-1)^{\bruch{5^{2}-1}{8}} [/mm] = -1
[mm] \Rightarrow [/mm] Es gibt keine Lösung
Stimmt das alles so?
Vielen Dank und Liebe Grüße!!
Loko
|
|
|
| |
|
Hallo Loko,
das ist alles vollkommen richtig. ![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:08 Do 15.12.2011 | | Autor: | Loko |
Vielen Dank ihr zwei!! :)
|
|
|
|
