Primitivwurzel < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:15 So 03.10.2010 | | Autor: | daN-R-G |
| Aufgabe | | Welche der Zahlen aus der Menge [mm] \lbrace1, [/mm] 2, 3, [mm] 4\rbrace [/mm] sind eine Primitivwurzel modulo 47 |
Huhu!
Ich hätte da ne Frage zu dieser Aufgabe: Ein Element ist ja Primitivwurzel, wenn seine Ordnung gleich der Ordnung seiner Gruppe ist.
Ich habe ja jetzt keine genaue Gruppe angegeben. Ist damit wohl [mm] \IZ/47\IZ [/mm] gemeint?
47 Ist ja nun Primzahl, dementsprechend wäre die Ordnung dann ja 46. Muss ich nun jedes der 4 Elemente überprüfen, ob 46 der kleinste Expontent ist, sodass (ich nenn das Element nun mal a) [mm] a^{47} [/mm] = 1 ist?
|
|
| |
|
Hallo
> Welche der Zahlen aus der Menge [mm]\lbrace1,[/mm] 2, 3, [mm]4\rbrace[/mm]
> sind eine Primitivwurzel modulo 47
> Huhu!
>
> Ich hätte da ne Frage zu dieser Aufgabe: Ein Element ist
> ja Primitivwurzel, wenn seine Ordnung gleich der Ordnung
> seiner Gruppe ist.
> Ich habe ja jetzt keine genaue Gruppe angegeben. Ist damit
> wohl [mm]\IZ/47\IZ[/mm] gemeint?
>
> 47 Ist ja nun Primzahl, dementsprechend wäre die Ordnung
> dann ja 46. Muss ich nun jedes der 4 Elemente überprüfen,
> ob 46 der kleinste Expontent ist, sodass (ich nenn das
> Element nun mal a) [mm]a^{47}[/mm] = 1 ist?
Nicht ganz.
Du hast also ne Gruppe von Ordnung 47. Das ist eine Primzahl, somit ist [mm]\varphi(47) = 46[/mm].
Jetzt ist es ja so, dass eine Zahl [mm]a \in G[/mm] ne Primitivwurzel ist, wenn [mm]a[/mm] die Einheitengruppe [mm]G^{\times}[/mm] erzeugt.
[mm]|G^{\times}| = 46[/mm], somit ist [mm]a[/mm] eine Primitivwurzel, falls [mm]a^{46} \equiv 1 (mod 47)[/mm] und [mm]a^{x} \not\equiv 1 (mod 47)[/mm] für jedes [mm]x < 46[/mm].
>
>
Grüsse, Amaro
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:06 So 03.10.2010 | | Autor: | daN-R-G |
Danke erstmal für die Antwort!
Ich glaube so ungefährt meinte ich das auch *g*
Mein Problem ist nun: Muss ich jetzt alle [mm] a^x [/mm] für 1 [mm] \leq [/mm] x [mm] \leq [/mm] 46 durchrechnen oder gibts es da auch irgendwie einen Trick? Weil das ganze wäre ja ziemlich aufwändig, das so einfach zu "brute-forcen".
1 Fällt ja eh direkt weg, da bereits [mm] 1^1 \equiv [/mm] 1 [mm] \pmod [/mm] 47 gilt.
Nebenbei: Müsste ich eigentlich immer nur die a [mm] \in [/mm] G betrachten, für die gilt: ggT(a, m) = 1? Bei Primzahlen als Modulo wäre das jetzt zwar eh egal, aber falls es mal keine sein sollte...
|
|
|
| |
|
Hallo daN-R-G,
nee, brute force ist nicht nötig. Was weißt Du über quadratische Reste bzw. Nichreste?
Ein quadratischer Rest kann hier nicht Primitivwurzel sein, wie man sich leicht überlegen kann:
Ist [mm] a^2\equiv b\mod{47} [/mm] und (a,47)=1, so ist [mm] a^{46}\equiv b^{23}\equiv 1\mod{47}.
[/mm]
Und Deine andere "Vermutung"; bzgl. der Teilerfremdheit ist richtig.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:43 So 03.10.2010 | | Autor: | daN-R-G |
Ui... ich glaub da muss ich wohl noch bissle lesen.
Also zu QR weiß ich, dass falls ggT(a, m) = 1 gilt, dass a genau dann QR ist, wenn [mm] a^{\frac{p-1}{2}} \equiv [/mm] 1 [mm] \pmod{m}.
[/mm]
Irgendwie fehlt mir aber noch der Überblick über das ganze. Also wäre der richtige Ansatz zu überprüfen, ob 1, 2, 3, 4 Quadratische Rest Modulo 47 wären? Dann weiß ich ja auch schonmal, wo ich suchen muss :)
Zumindest weiß ich schonmal ohne groß rechnen zu müssen, dass 1 und 4 rausfallen, da 4 schließlich QR ist.
|
|
|
| |
|
Hallo nochmal,
> Ui... ich glaub da muss ich wohl noch bissle lesen.
Keine Angst, ich auch. 
> Also zu QR weiß ich, dass falls ggT(a, m) = 1 gilt, dass a
> genau dann QR ist, wenn [mm]a^{\frac{p-1}{2}} \equiv[/mm] 1
> [mm]\pmod{m}.[/mm]
Schon, aber genau das habe ich mir ja auch gerade zunutze gemacht.
> Irgendwie fehlt mir aber noch der Überblick über das
> ganze. Also wäre der richtige Ansatz zu überprüfen, ob
> 1, 2, 3, 4 Quadratische Rest Modulo 47 wären? Dann weiß
> ich ja auch schonmal, wo ich suchen muss :)
>
> Zumindest weiß ich schonmal ohne groß rechnen zu müssen,
> dass 1 und 4 rausfallen, da 4 schließlich QR ist.
Du kannst es recht kurz halten, wenn Du nur die Primzahlen p<47 darauf untersuchst, ob sie QR sind. Aus dieser Information kannst Du alle QR gewinnen.
Es zeigt sich, dass 2 und 3 QR sind, 5 aber nicht...
(es ist ja [mm] 7^2\equiv{2},\ 12^2\equiv 3\mod{47}).
[/mm]
Dass es nicht genügt, nur bis [mm] \wurzel{47} [/mm] zu suchen, zeigt z.B. die 17. Sie ist ein quadratischer Rest, da ja [mm] 8^2=64\equiv 17\mod{47}.
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:06 So 03.10.2010 | | Autor: | daN-R-G |
Vielen Dank für die Mühe! :)
Ich werde noch ein wenig lesen zu Quadratischen Resten und Primitivwurzeln und bei Gegebenheit nochmal nachfragen ;)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:06 So 03.10.2010 | | Autor: | felixf |
Moin!
> Ui... ich glaub da muss ich wohl noch bissle lesen.
>
> Also zu QR weiß ich, dass falls ggT(a, m) = 1 gilt, dass a
> genau dann QR ist, wenn [mm]a^{\frac{p-1}{2}} \equiv[/mm] 1
> [mm]\pmod{m}.[/mm]
Ja. Man kann es aber auch mit dem Legendre-Symbol und dem quadratischen Reziprozitaetsgesetz nachpruefen. Damit geht es meist einfacher.
> Irgendwie fehlt mir aber noch der Überblick über das
> ganze. Also wäre der richtige Ansatz zu überprüfen, ob
> 1, 2, 3, 4 Quadratische Rest Modulo 47 wären? Dann weiß
> ich ja auch schonmal, wo ich suchen muss :)
Ja. Allgemein gilt:
Sei $G$ eine Gruppe und $a [mm] \in [/mm] G$.
$a$ hat genau dann Ordnung $n$, wenn gilt:
(i) [mm] $a^n [/mm] = 1$;
(ii) [mm] $a^{n/p} \neq [/mm] 1$ fuer alle Primzahlen $p$, die $n$ teilen.
Hier ist $n = 46$, und das hat die Primteiler 2 und 23. Nach Fermat gilt sowieso [mm] $a^n [/mm] = 1$ in [mm] $(\IZ/47\IZ)^\ast$, [/mm] womit du also testen muss, ob [mm] $a^{46/23} [/mm] = [mm] a^2 \neq [/mm] 1$ und ob [mm] $a^{46/2} \neq [/mm] 1$ ist. Das zweite ist aequivalent dazu, ob's ein quadratischer Rest ist (kann also mit dem Legendre-Symbol schnell geprueft werden), und das erste kann man auch so schnell nachrechnen
> Zumindest weiß ich schonmal ohne groß rechnen zu müssen,
> dass 1 und 4 rausfallen, da 4 schließlich QR ist.
Genau.
1 ist sowieso nur dann eine Primitivwurzel in [mm] $\IZ/n\IZ$, [/mm] wenn [mm] $\phi(n) [/mm] = 1$ ist. (Was wiederum nur bei $n = 1$ und $n = 2$ geht.)
LG Felix
|
|
|
|
