Kongruenz mit quadratRest < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:35 Mo 18.06.2012 | | Autor: | Laurent |
| Aufgabe | Sei p = 4k+3 für ein k [mm] \in \IZ, [/mm] ggT(a,p)=1
Zeige: [mm] x^4\equiv [/mm] a mod p [mm] \gdw [/mm] a q.R. von p |
Hallihallo!
Ich habe mit oben genannter Aufgabe so meine Probleme. q.R. soll hier für quadratischen Rest stehen.
Meine Überlegungen dazu waren bisher diese:
Zur Rückrichtung:
[mm] x^4=(x^2)^2 \equiv a^2, [/mm] da a q.R mod p ist.
Aber wie zum Teufel soll ich jetzt zeigen, dass [mm] a^2 \equiv [/mm] a mod p ist?
Oder ist mein erster Schritt schon falsch?
Zur Hinrichtung habe ich noch nichtmal eine Idee..
Ich hoffe ihr könnt mir helfen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
Hallo Laurent, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
> Sei p = 4k+3 für ein k [mm]\in \IZ,[/mm] ggT(a,p)=1
> Zeige: [mm]x^4\equiv[/mm] a mod p [mm]\gdw[/mm] a q.R. von p
> Hallihallo!
>
> Ich habe mit oben genannter Aufgabe so meine Probleme. q.R.
> soll hier für quadratischen Rest stehen.
> Meine Überlegungen dazu waren bisher diese:
>
> Zur Rückrichtung:
>
> [mm]x^4=(x^2)^2 \equiv a^2,[/mm] da a q.R mod p ist.
Da stimmt etwas in der Logik nicht.
Dass [mm] x^4=(x^2)^2 [/mm] ist, kannst Du für die Hinrichtung verwenden. Da ist doch offensichtlich, dass a ein q.R. ist.
> Aber wie zum Teufel soll ich jetzt zeigen, dass [mm]a^2 \equiv[/mm]
> a mod p ist?
Das wird i.a. nur für a=1 der Fall sein. 
Ansonsten ist das auch nicht zu folgern bzw. zu fordern.
> Oder ist mein erster Schritt schon falsch?
Ja.
> Zur Hinrichtung habe ich noch nichtmal eine Idee..
Die ist eigentlich schon gelöst, s.o.
Die Frage ist die Rückrichtung: wenn a ein q.R. ist, dann soll es also immer ein zu p teilerfremdes x geben, so dass [mm] x^{\red{4}}\equiv a\mod{p} [/mm] ist. Das ist nicht selbstverständlich.
Hast Du die besondere Struktur von p schon mit eingebracht?
Grüße
reverend
> Ich hoffe ihr könnt mir helfen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:42 Mo 18.06.2012 | | Autor: | Laurent |
Hallo reverend, ja natürlich, das war dumm von mir. Dann habe ich die Hinrichtung gezeigt.
Die Struktur von p habe ich noch nicht eingebracht. Da steht ja eigentlich
[mm] x^4 \equiv [/mm] a mod 4k+3, und zu zeigen ist doch jetzt, dass es ein y gibt mit [mm] y^2 \equiv [/mm] a mod p. Leider sehe ich hier keinen Unterschied zu einer Primzahl der Form 4k+1. Da müsste es ja demnach irgendwo schiefgehen, leider sehe ich das nicht... :-(
Aber schonmal vielen dank für die Hilfe.
|
|
|
| |
|
Hallo,
> Hallo reverend, ja natürlich, das war dumm von mir. Dann
> habe ich die Hinrichtung gezeigt.
>
> Die Struktur von p habe ich noch nicht eingebracht. Da
> steht ja eigentlich
>
> [mm]x^4 \equiv[/mm] a mod 4k+3, und zu zeigen ist doch jetzt, dass
> es ein y gibt mit [mm]y^2 \equiv[/mm] a mod p.
Nein, das ist ja schon klar. Wenn a ein q.R. ist, und das ist in der Rückrichtung ja die Voraussetzung, dann gibt es genau zwei solche y (weil p ja prim ist, sonst gäbe es mehr). Nur wieso ist nun eins dieser y selbst wieder q.R.? Es gibt ja [mm] x^4\equiv y^2, [/mm] woraus wir folgern, dass es mindest ein Paar (x,y) gibt, so dass [mm] x^2\equiv y\mod{p}.
[/mm]
> Leider sehe ich hier
> keinen Unterschied zu einer Primzahl der Form 4k+1. Da
> müsste es ja demnach irgendwo schiefgehen, leider sehe ich
> das nicht... :-(
Wie prüft man denn, ob y ein q.R. ist? Eine Möglichkeit ist, ein passendes x zu finden, aber das wird bei dieser allgemeinen Aufgabenstellung sicher nicht gelingen.
Da gabs doch noch ne Regel...
lg
reverend
> Aber schonmal vielen dank für die Hilfe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:06 Mo 18.06.2012 | | Autor: | Laurent |
Ich kenne nur das Legendre Symbol, oder welche Regel meintest du?
Ich glaube mit dem Symbol lässt sich hier auch nicht gut arbeiten oder?
Aber schonmal danke, danke, danke :)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:37 Mo 18.06.2012 | | Autor: | Laurent |
Ich habe nochmal etwas überlegt, weiß aber nicht, ob mir das was bringt.
Dass a ein q.R. ist heißt ja, dass [mm] (\bruch{a}{p})=1 [/mm] ist.
[mm] (\bruch{a}{p}) [/mm] = [mm] (-1)^{\bruch{p-1}{2}}, [/mm] also muss p-1 [mm] \equiv [/mm] 1 mod 4 sein.
aber mein p ist ja kongruent 2 mod 4, das heißt, der ggT(4,p-1) ist 2.
Was mach ich denn jetzt? =(
|
|
|
| |
|
Hallo nochmal,
dochdoch, Legendre-Symbol ist der richtige Ansatz.
> Ich habe nochmal etwas überlegt, weiß aber nicht, ob mir
> das was bringt.
>
> Dass a ein q.R. ist heißt ja, dass [mm](\bruch{a}{p})=1[/mm] ist.
>
> [mm](\bruch{a}{p})[/mm] = [mm](-1)^{\bruch{p-1}{2}},[/mm] also muss p-1 [mm]\equiv[/mm] 1 mod 4 sein.
Tipp- oder Denkfehler? [mm] p-1\stackrel{\mathrm{!}}\equiv \blue{0}\mod{4}
[/mm]
Außerdem: [mm] \left(\bruch{a}{p}\right)=\blue{a}^{\bruch{p-1}{2}}
[/mm]
Da a sicher q.R. ist (Bedingung der Rückrichtung), wissen wir also, dass mit p=4k+3 gilt: [mm] a^{2k+1}\equiv 1\mod{p}
[/mm]
> aber mein p ist ja kongruent 2 mod 4,
[mm] p\equiv 3\mod{4}\quad \gdw\quad p-1\equiv 2\mod{4}
[/mm]
> das heißt, der
> ggT(4,p-1) ist 2. ![[ok]](/images/smileys/ok.gif "[ok]")
> Was mach ich denn jetzt? =(
Wir suchten doch eine Aussage über ein y mit [mm] y\equiv x^2\mod{p}, [/mm] oder anders gesagt [mm] \left(\bruch{y}{p}\right)=1
[/mm]
Also muss auch [mm] y^{2k+1}\equiv 1\mod{p} [/mm] sein.
Das ist natürlich nicht offensichtlich, aber zumindestens ist das Problem damit klar.
lg
reverend
PS: Immer wenns schwierig wird, lohnt es sich, an einem einfachen Beispiel zu überprüfen, ob die Behauptung da stimmt, also z.B. für p=3,7,11,19...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:16 Mo 18.06.2012 | | Autor: | Laurent |
Ja okay das habe ich verstanden. Das eine war ein Tipp, das andere ein Denkfehler.
Aber wenn wir so ein y suchen mit y [mm] \equiv x^2 [/mm] mod p, dann ist doch eigentlich mit a eins gegeben, weil a q.R. ist. Oder ist das wieder völlig daneben?
|
|
|
| |
|
Hallo Laurent,
> Ja okay das habe ich verstanden. Das eine war ein Tipp, das
> andere ein Denkfehler.
>
> Aber wenn wir so ein y suchen mit y [mm]\equiv x^2[/mm] mod p, dann
> ist doch eigentlich mit a eins gegeben, weil a q.R. ist.
> Oder ist das wieder völlig daneben?
Das ist auch ein Denkfehler.
Schau Dir mal n=13 an (das ja nicht die Form 4k+3 hat).
Da sind quadratische Reste: 1,3,4,9,10,12.
Biquadratische Reste (also solche von [mm] x^4 [/mm] ) sind: 1,3,9.
Heißt also: bloß weil a ein q.R. ist, gibt es noch nicht unbedingt auch ein x, so dass [mm] x^4\equiv a\mod{13}.
[/mm]
Für [mm] a\equiv4,10,12 [/mm] existieren solche x nicht.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:49 Mo 18.06.2012 | | Autor: | Laurent |
Aber über das y weiß ich doch so nichts, wie kann ich das denn jetzt zeigen?
Ich weiß a ist qR also gilt [mm] a^{2k+1} \equiv [/mm] 1 mod p. Und damit y qR ist, muss auch [mm] y^{2k+1} \equiv [/mm] 1 mod p sein. Das einzige was ich aber weiß ist, dass [mm] y^2\equiv [/mm] a mod p ist. Jetzt ist natürlich [mm] y^{2k+1} [/mm] = [mm] y*(y^2)^k \equiv y*a^k [/mm] mod p. Aber das bringt mich ja nicht weiter =(
|
|
|
| |
|
Hallo Laurent,
ein letzter Tipp - danach kann ich eigentlich nur noch die Lösung verraten...
> Aber über das y weiß ich doch so nichts, wie kann ich das
> denn jetzt zeigen?
>
> Ich weiß a ist qR also gilt [mm]a^{2k+1} \equiv[/mm] 1 mod p. Und
> damit y qR ist, muss auch [mm]y^{2k+1} \equiv[/mm] 1 mod p sein.
> Das
> einzige was ich aber weiß ist, dass [mm]y^2\equiv[/mm] a mod p ist.
> Jetzt ist natürlich [mm]y^{2k+1}[/mm] = [mm]y*(y^2)^k \equiv y*a^k[/mm] mod
> p. Aber das bringt mich ja nicht weiter =(
Naja, wie mans nimmt.
Nehmen wirs mal von einer anderen Seite. Du weißt (nehme ich an), dass es [mm] \tfrac{p-1}{2} [/mm] quadratische Reste gibt.
Was die Aufgabe behauptet, ist dass für p=4k+3 nun die vollständige Liste aller quadratischen Reste sich selbst redupliziert.
Beispiele: p=7 liefert die quadratischen Reste 1,2,4. Wenn man die quadriert, kommt man auf [mm] 1\to1, 2\to4, 4\to2.
[/mm]
p=11 hat folgende q.R.: 1,3,4,5,9. Quadriert ergibt sich [mm] 1\to1, 3\to9, 4\to5, 5\to3, 9\to4.
[/mm]
Wenn also a ein q.R. ist, was heißt das für -a?
Grüße
reverend
|
|
|
|
