Lösung quadratischer Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es seien p, q zwei verschiedene ungerade Primzahlen mit [mm] (\bruch{p}{q}) [/mm] = 1, wobei [mm] (\bruch{p}{q}) [/mm] das Legendre Symbol bezeichne.
Finden Sie eine Lösung für [mm] x^{2} \equiv [/mm] p (mod q) |
Hallo Leute,
mir kommt diese Aufgabe etwas suspekt vor, da ich nicht weiß, wie ich das systematisch lösen soll.
Mir würde nur Rumprobiererei einfallen, aber ich denke, dass kann und sollte es nicht sein.
Hätte jemand einen Tipp für mich, wie ich hier vorgehen soll?
Kann man evtl. das quadratische Reziprozitätsgesetz irgendwie einfliesen lassen?
Viele Grüße
Anfänger
|
|
| |
|
Hallo Anfänger,
ich habe leider nur eine Lösung für [mm] q\equiv 3\mod{4}.
[/mm]
> Es seien p, q zwei verschiedene ungerade Primzahlen mit
> [mm](\bruch{p}{q})[/mm] = 1, wobei [mm](\bruch{p}{q})[/mm] das Legendre
> Symbol bezeichne.
>
> Finden Sie eine Lösung für [mm]x^{2} \equiv[/mm] p (mod q)
> Hallo Leute,
>
> mir kommt diese Aufgabe etwas suspekt vor, da ich nicht
> weiß, wie ich das systematisch lösen soll.
> Mir würde nur Rumprobiererei einfallen, aber ich denke,
> dass kann und sollte es nicht sein.
>
> Hätte jemand einen Tipp für mich, wie ich hier vorgehen
> soll?
> Kann man evtl. das quadratische Reziprozitätsgesetz
> irgendwie einfliesen lassen?
Es ist [mm] \left(\bruch{p}{q}\right)\equiv p^{\bruch{1}{2}(q-1)}\equiv 1\mod{q}
[/mm]
Gesucht ist ein x mit [mm] x^2\equiv p\equiv p*1\equiv p*p^{\bruch{1}{2}(q-1)} \equiv p^{\bruch{1}{2}(q+1)} \mod{q}
[/mm]
Für [mm] q\equiv 3\mod{4} [/mm] ist [mm] \tfrac{1}{2}(q+1) [/mm] gerade, und damit ist [mm] x\equiv p^{\bruch{1}{4}(q+1)}\mod{q} [/mm] eine gültige Lösung.
***
Bleibt also noch [mm] q\equiv 1\mod{4} [/mm] zu untersuchen.
Dazu habe ich bisher keinen Einfall.
Immerhin wissen wir für diesen Fall: [mm] \left(\bruch{p}{q}\right)=\left(\bruch{q}{p}\right)=1
[/mm]
Also ist auch [mm] q\mod{p} [/mm] ein quadratischer Rest.
Ich weiß nicht, ob das für die Aufgabe weiterhilft.
Darum lasse ich sie auf "teilweise beantwortet" stehen.
Du findest übrigens leicht Beispiele wie (p,q)=(13,17), an denen Du einen Lösungsweg versuchen kannst. Hier sind x=8 und x=9 Lösungen. Für (p,q)=(11,37) sind x=14 und x=23 Lösungen.
Viel Erfolg!
reverend
|
|
|
| |
|
Hallo ihr Beiden,
erstmal Danke, dass ihr euch so schnell gerührt habt.
Der Fall q [mm] \equiv [/mm] 3 mod 4 ist soweit sehr einleuchtend.
Beim zweiten Fall seh ich irgendwie auch keine Möglichkeit, wie man da allgemein eine Lösung angeben soll. Wenn in den nächsten Tagen keiner ne Idee dazu hat, werd ich wohl doch mal beim Professor nachfragen müssen, ob das überhaupt geht.
Auf jeden Fall Danke soweit 
Viele Grüße
Anfänger
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Do 27.09.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
Dort braucht man auch gar nicht, dass $p$ eine Primzahl ist.
