quadratische Reste und Zyklen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:33 So 17.03.2013 | | Autor: | schubi |
| Aufgabe | Eigentlich sind es 2 Fragen (2 Unteraufgaben):
1.)
Was können Sie über die Zyklizität der Gruppe [mm] R_{pq} [/mm] im Falle zweier verschiedener ungerader Primzahlen p und q sagen? Wenden Sie Ihre Erkenntnisse auf [mm] R_{19*29} [/mm] und [mm] R_{19*31} [/mm] an.
2.)
Wir betrachten eine ungerade Primzahl p und setzen s=(p-1)/2. Nach Satz 7.4 des Buches erfüllt jede primitive Wurzel g modulo p die Bedingung
[mm] g^{s} [/mm] mod p = -1 mod p (1)
Zeigen oder widerlegen Sie die Umkehrung: Aus (1) folgt, dass g primitive Wurzel modulo p ist. |
Hallo erstmal :)
Bei beiden Aufgaben fehlt mir irgendwie der Ansatz.
Zu der ersten:
-------------------------------------------------------------------------
Es gibt da ja so einen Satz: n [mm] \in \IN, [/mm] n=pq, a [mm] \in \IZ^{\*}_{n}
[/mm]
[mm] x^{2} [/mm] mod n = a besitzt für a [mm] \in R_{n} [/mm] genau 4 Lösungen.
-------------------------------------------------------------------------
Das heißt, ich kann auf jeden Fall schon einmal sagen, wie groß mein [mm] R_{n} [/mm] sein muss. Da jedes a 4 Lösungen hat, so ist die Anzahl der quadratischen Reste a gleich die Mächtigkeit von [mm] \IZ^{\*}_{n} [/mm] / 4.
Es gibt [mm] \phi(pq) [/mm] = (p-1)(q-1) Elemente in [mm] \IZ^{\*}_{n}, [/mm] also hat [mm] R_{n} [/mm] = (p-1)(q-1) / 4 elemente.
Oder irre ich mich da?
So aber das hat ja nun noch nciht so wirklich viel mit der Aufgabe zu tun...
-------------------------------------------------------------------------
Ich hab versucht ein wenig mit folgenden Sätzen rumzuspielen:
a ist quadr. Rest mod pq [mm] \gdw [/mm] a ist quadr. Rest mod p [mm] \wedge [/mm] a ist quadr. Rest mod q
und
ab ist quadr. Rest mod p [mm] \gdw [/mm] a,b beide quadr. Reste mod p [mm] \vee [/mm] a,b beide quadr. Nichtreste mod p
-------------------------------------------------------------------------
Ja und mir ist aufgefallen, dass die 4 immer in [mm] R_{n} [/mm] drin sein muss und dazu bei allen beispielen die ich mir gemacht habe war die 4 ein erzeugendes Element.
Ich vermute das es zyklisch ist und 4 immer ein erzeugendes Element ist, aber ich bekomme den verallgemeinerten Beweis nicht hin.
Da bräuchte ich ein wenig Hilfe :)
Und zur Aufgabe 2)
hier habe ich irgendwie keinen Ansatz. Höchstens (weil ich vermute das es nciht geht!) ein gegenbeispiel finden. Nur ich sehe keins?
Vielen Dank schonmal :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:54 Mo 18.03.2013 | | Autor: | hippias |
Was ist denn [mm] $R_{n}$? [/mm] Ich habe zwar eine Vermutung,aber mir ist diese Bezeichnung nicht gelaeufig.
1) Im ersten Aufgabenteil wird doch ueberhaupt nicht nach quadratischen Resten gefragt, sondern ob das [mm] $R_{pq}$ [/mm] zyklisch ist oder nicht. Dazu musst Du Dir Gedanken machen: Wenn Du weisst, dass [mm] $R_{p}$ [/mm] bzw. [mm] $R_{q}$ [/mm] von $a$ bzw. $b$ erzeugt werden, versuche daraus einen Erzeuger von [mm] $R_{pq}$ [/mm] zu konstruieren. Oder finde ein Beispiel, fuer das [mm] $R_{pq}$ [/mm] nicht zyklisch ist.
2) Wie lautet die Definition einer primitiven Wurzel? Schlage auch nocheinmal in dem Buch nach, wieso diese Kongruenz gilt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:15 Mo 18.03.2013 | | Autor: | schubi |
Hi :)
Also [mm] R_{n}<\IZ_{n}^{\*} [/mm] bezeichnet die Untergruppe quadratischer Reste.
Und zu 2.)
werde ich gleich den Beweis für die eine Richtung nochmal nachschauen und reinschreiben :)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:29 Mo 18.03.2013 | | Autor: | schubi |
Ah okay ja der Beweis war nicht schwer, nur die umgekehrte Richtung, ich komm auf keinen grünen Zweig :)
Also:
gegeben ist ja: p>2 Primzahl, g primitive Wurzel modulo p und
[mm] g^{(p-1)/2} [/mm] mod p = -1 mod p
Da g eine primitive Wurzel ist,also Erzeuger der Gruppe [mm] \IZ_{n}^{\*} [/mm] erreicht man über die Potenzen [mm] g^{k} [/mm] von p ja sämtliche Elemente der Gruppe.
Die Ordnung der Gruppe ist [mm] \phi(p) [/mm] = p-1.
Also ist (auch nach Fermat) [mm] g^{p-1} [/mm] mod p = 1 mod p.
Wenn ich meine ursprungsgleichung da quadriere erhalte ich:
[mm] {(g^{(p-1)/2})}^{2} [/mm] mod p = [mm] g^{p-1} [/mm] mod p = 1 mod p.
Da diese Gleichung 2 Lösungen hat, nämlich -1 mod p und 1 mod p, so kann aufgrund der vorherigen überlegung nur
[mm] g^{(p-1)/2} [/mm] mod p = -1 mod p
gelten.
Ich hoffe das hilft so weiter ... :) Wie kann man jetzt zeigen, dass die umgekehrte Richtung nicht gilt bzw gilt?
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:45 Mo 18.03.2013 | | Autor: | schubi |
Also ich denke, dass man aus [mm] g^s \equiv [/mm] -1 mod p folgern kann, dass g primitive Wurzel ist, eben weil folgendes gilt:
[mm] g^s \equiv [/mm] -1 mod p [mm] \Rightarrow (g^s)^{2} \equiv [/mm] 1 mod p [mm] \Rightarrow g^{p-1} \equiv [/mm] 1 mod p [mm] \Rightarrow [/mm] g Erzeuger von [mm] \IZ_{p}^{\*}
[/mm]
Oder ist das jetzt an den Haaren herbeigezogen? :)
Und zu deiner Antwort nochmal: Ist denn jede Primzahl automatisch Erzeuger? Ich meine ich weiß ja auch nichts über [mm] R_{p} [/mm] bzw. [mm] R_{q}... [/mm] dann kann ich doch auch nichts über [mm] R_{pq} [/mm] sagen...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:36 Di 19.03.2013 | | Autor: | hippias |
> Also ich denke, dass man aus [mm]g^s \equiv[/mm] -1 mod p folgern
> kann, dass g primitive Wurzel ist, eben weil folgendes
> gilt:
>
> [mm]g^s \equiv[/mm] -1 mod p [mm]\Rightarrow (g^s)^{2} \equiv[/mm] 1 mod p
> [mm]\Rightarrow g^{p-1} \equiv[/mm] 1 mod p [mm]\Rightarrow[/mm] g Erzeuger
> von [mm]\IZ_{p}^{\*}[/mm]
>
> Oder ist das jetzt an den Haaren herbeigezogen? :)
Nein, das ist schon gut. Die Ordnung von $g$ ist die kleinste natuerliche Zahl $n$ fuer die [mm] $g^{n}= [/mm] 1$ gilt. Der Vollstaendigkeit halber solltest Du noch zeigen, dass es eine kleinere Zahl als $p-1$ mit dieser Eigenschaft nicht gibt.
>
>
> Und zu deiner Antwort nochmal: Ist denn jede Primzahl
> automatisch Erzeuger? Ich meine ich weiß ja auch nichts
> über [mm]R_{p}[/mm] bzw. [mm]R_{q}...[/mm] dann kann ich doch auch nichts
> über [mm]R_{pq}[/mm] sagen...
Doch, Du solltest etwas ueber [mm] $R_{p}$ [/mm] und [mm] $R_{q}$ [/mm] wissen: naemlich, dass sie zyklisch sind. Auch der Chinesische Restsatz koennte hilfreich sein (oder so).
|
|
|
|
