quadratische Gleichung (mod p) < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:00 Sa 03.05.2008 | | Autor: | kichel |
| Aufgabe | | Sei p eine Primzahl der Form p = 4*n + 1 wobei n eine positive Zahl ist. Zeigen sie, dass die Gleichung [mm] x^2 \equiv-1 [/mm] (mod p) eine Lösung in Z hat. |
Das gilt falls ein y in Z existiert sodass [mm] x^2 [/mm] = y*(4*n+1) - 1 . Wie kann man diesen Ausdruck so faktorisieren, das beide Faktoren gleich sind? Kann man die Aufgabe auch anders lösen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:58 Sa 03.05.2008 | | Autor: | felixf |
Hallo
> Sei p eine Primzahl der Form p = 4*n + 1 wobei n eine
> positive Zahl ist. Zeigen sie, dass die Gleichung [mm]x^2 \equiv-1[/mm]
> (mod p) eine Lösung in Z hat.
>
> Das gilt falls ein y in Z existiert sodass [mm]x^2[/mm] = y*(4*n+1)
> - 1 . Wie kann man diesen Ausdruck so faktorisieren, das
> beide Faktoren gleich sind? Kann man die Aufgabe auch
> anders lösen?
Du musst zeigen, dass [mm] $\left( \frac{-1}{p} \right) [/mm] = 1$ ist (Legendre-Symbol). Was kennst du da fuer Rechenregeln?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:04 Sa 03.05.2008 | | Autor: | kichel |
Leider gar keine. Dieses Symbol wurde noch nicht definiert.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:15 Sa 03.05.2008 | | Autor: | felixf |
Hallo
> Leider gar keine. Dieses Symbol wurde noch nicht definiert.
Ok, dann machen wir das halt zu Fuss. Betrachten wir mal die multiplikative Gruppe $G = [mm] (\IZ/p\IZ)^*$; [/mm] diese ist zyklisch und hat $p - 1$ Elemente. Sei etwa $g [mm] \in [/mm] G$ ein Erzeuger.
Jetzt kann man sich erstmal ueberlegen, dass ein Element $h [mm] \in [/mm] G$ genau dann ein Quadrat ist, wenn es ein $n [mm] \in \IN$ [/mm] gibt mit [mm] $g^n [/mm] = h$ und $n$ gerade. (Ein $n$ gibt es immer, aber es ist nicht umbedingt gerade.)
Sei also $h [mm] \in [/mm] G$ beliebig und $n [mm] \in \IN$ [/mm] mit [mm] $g^n [/mm] = h$. Wann ist $n$ gerade? Man kann sich jetzt ueberlegen, dass $n$ genau dann gerade ist, wenn [mm] $h^{\frac{p - 1}{2}} [/mm] = 1$ ist, also wenn $n [mm] \frac{p - 1}{2}$ [/mm] ein Vielfaches von $p - 1$ (der Ordnung von $g$) ist.
Du musst also zeigen, dass [mm] $(-1)^{\frac{p - 1}{2}} [/mm] = 1$ ist in [mm] $\IZ/p\IZ$. [/mm] Jetzt weisst du, dass $p = 4 n + 1$ ist, also [mm] $\frac{p - 1}{2} [/mm] = 2 n$. Das sollte dir jetzt weiterhelfen 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:45 Sa 03.05.2008 | | Autor: | kichel |
und wie mir das weitergeholfen hat, so glänzt das ganze in schönem Licht :) vielen dank!
|
|
|
|
