Primzahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:42 Mi 16.06.2010 | | Autor: | buef |
| Aufgabe | Seien p,q ungerade Primzahlen mit p=2q+1 und 2 [mm] \leq [/mm] r [mm] \leq [/mm] q.
a) Wieviele Erzeuger hat [mm] (\IZ [/mm] / p [mm] \IZ [/mm] )* ?
b) Zeigen Sie [mm] r^{q} \equiv [/mm] 1 (mod p)
c) Eine der beiden Zahlen r, -r ist Primitivwurzel mod p |
zu a)
Ich weiß dass die Anzahl der Erzeuger die sind, wo ggT(i,p)=1 für 1 [mm] \leq [/mm] i [mm] \leq [/mm] p
Kann man das so machen?
Betrachte [mm] G:=(\IZ [/mm] / p [mm] \IZ [/mm] )* mit [mm] ord(G)=\varphi(p)
[/mm]
Berechne also [mm] \varphi(2q+1)
[/mm]
Jetzt komme ich nicht weiter
wahrscheinlich kommt man aber damit weiter
[mm] \varphi(p)=p-1 [/mm] für p [mm] \in \IP
[/mm]
Beispiele wären
q=3 also p=2*3+1=7
[mm] \varphi(7)=6=2*q
[/mm]
q=23 also p=2*23+1=47
varphi(47)=46=2*q
zu b)
Da tapp ich noch im Dunkeln
zu c)
Zu zeigen ist also, dass
[mm] r^k [/mm] = 1 mod (2q+1) bzw
[mm] (-r)^k [/mm] = 1 mod (2q+1) mit 2 [mm] \leq [/mm] r [mm] \leq [/mm] q.
Aber auch da, weiß ich nicht genau, wie ich das zeigen soll.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:27 Mi 16.06.2010 | | Autor: | abakus |
> Seien p,q ungerade Primzahlen mit p=2q+1 und 2 [mm]\leq[/mm] r [mm]\leq[/mm]
> q.
>
> a) Wieviele Erzeuger hat [mm](\IZ[/mm] / p [mm]\IZ[/mm] )* ?
> b) Zeigen Sie [mm]r^{q} \equiv[/mm] 1 (mod p)
> c) Eine der beiden Zahlen r, -r ist Primitivwurzel mod p
> zu a)
>
> Ich weiß dass die Anzahl der Erzeuger die sind, wo
> ggT(i,p)=1 für 1 [mm]\leq[/mm] i [mm]\leq[/mm] p
>
> Kann man das so machen?
> Betrachte [mm]G:=(\IZ[/mm] / p [mm]\IZ[/mm] )* mit [mm]ord(G)=\varphi(p)[/mm]
> Berechne also [mm]\varphi(2q+1)[/mm]
>
> Jetzt komme ich nicht weiter
>
> wahrscheinlich kommt man aber damit weiter
>
> [mm]\varphi(p)=p-1[/mm] für p [mm]\in \IP[/mm]
>
> Beispiele wären
> q=3 also p=2*3+1=7
> [mm]\varphi(7)=6=2*q[/mm]
>
> q=23 also p=2*23+1=47
> varphi(47)=46=2*q
>
> zu b)
> Da tapp ich noch im Dunkeln
Hallo,
nach kleinem Satz von Fermat gilt
[mm]r^{p-1} \equiv[/mm] 1 (mod p).
Wegen p=2q+1 gilt also [mm]r^{2q} \equiv[/mm] 1 (mod p).
Die Reste der Potenzen sind bekanntlich zyklisch, wobei die Zykluslänge (p-1) oder ein Teiler von (p-1) ist. Du musst also noch zeigen, dass nicht erst bei [mm] r^{2q}, [/mm] sondern schon eher ein solcher Zyklus zu Ende ist.
>
> zu c)
> Zu zeigen ist also, dass
>
> [mm]r^k[/mm] = 1 mod (2q+1) bzw
> [mm](-r)^k[/mm] = 1 mod (2q+1) mit 2 [mm]\leq[/mm] r [mm]\leq[/mm] q.
>
> Aber auch da, weiß ich nicht genau, wie ich das zeigen
> soll.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:40 Mi 16.06.2010 | | Autor: | buef |
a habe ich jetzt. hat ja nicht mehr viel gefehlt
zu b)
aus einem Korollar von der Vorlesung wissen wir
[mm] r^{\varphi(p)} \equiv [/mm] 1 (mod p)
[mm] r^{\varphi(2q+1)} \equiv [/mm] 1 (mod p)
da p Prim
[mm] r^{2q} \equiv [/mm] 1 mod p
da [mm] q=\bruch{p-1}{2}
[/mm]
[mm] r^{p-1} \equiv [/mm] 1 (mod p)
mit p-1 = 2q
Die Reste der Potenzen sind bekanntlich zyklisch, wobei die Zykluslänge (p-1) oder ein Teiler von (p-1) ist.
bei c) komm ich trotzdem nicht weiter!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:43 Do 17.06.2010 | | Autor: | felixf |
Moin!
> a habe ich jetzt. hat ja nicht mehr viel gefehlt
>
> zu b)
>
> aus einem Korollar von der Vorlesung wissen wir
>
> [mm]r^{\varphi(p)} \equiv[/mm] 1 (mod p)
> [mm]r^{\varphi(2q+1)} \equiv[/mm] 1 (mod p)
> da p Prim
> [mm]r^{2q} \equiv[/mm] 1 mod p
> da [mm]q=\bruch{p-1}{2}[/mm]
> [mm]r^{p-1} \equiv[/mm] 1 (mod p)
>
> mit p-1 = 2q
Genau.
> Die Reste der Potenzen sind bekanntlich zyklisch, wobei die
> Zykluslänge (p-1) oder ein Teiler von (p-1) ist.
Und, wie machst du den Beweis jetzt fertig?
> bei c) komm ich trotzdem nicht weiter!
Du hast zwei Faelle:
a) [mm] $r^q \equiv [/mm] 1 [mm] \pmod{p}$;
[/mm]
b) [mm] $r^q \equiv [/mm] -1 [mm] \pmod{p}$.
[/mm]
Damit $r$ die Ordnung $p - 1$ hat (also eine Primitivwurzel ist), muss [mm] $r^x \not\equiv [/mm] 1 [mm] \pmod{p}$ [/mm] sein fuer alle echten Teiler von $p - 1$, also fuer $x = 1$ (klar), $x = p$ und $x = 2$.
Im Fall a) schau dir $-r$ an, im Fall b) schau dir $r$ selber an. Was kannst du jetzt sagen?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:37 Mi 16.06.2010 | | Autor: | ms2008de |
Hallo,
eine Frage zur Aufgabe: Soll r denn auch eine ungerade Primzahl sein oder nur eine natürliche Zahl oder kann das auch 2 sein? Falls ja gilt b) nämlich nicht:
[mm] 2^5 [/mm] =32 [mm] \equiv [/mm] 10 (mod 11)
Viele Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:18 Mi 16.06.2010 | | Autor: | buef |
Spitze Danke!
r muss nicht eine ungerade Primzahl sein!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:31 Mi 16.06.2010 | | Autor: | felixf |
Moin!
> Seien p,q ungerade Primzahlen mit p=2q+1 und 2 [mm]\leq[/mm] r [mm]\leq[/mm]
> q.
>
> a) Wieviele Erzeuger hat [mm](\IZ[/mm] / p [mm]\IZ[/mm] )* ?
> b) Zeigen Sie [mm]r^{q} \equiv[/mm] 1 (mod p)
> c) Eine der beiden Zahlen r, -r ist Primitivwurzel mod p
Ich finde diese Aufgabe etwas "komisch":
Gilt [mm] $r^q \equiv [/mm] 1 [mm] \pmod{p}$, [/mm] so kann $r$ keine Primitivwurzel modulo $p$ sein. Jedoch ist $-r$ dann immer eine Primitivwurzel modulo $p$, da $-1$ ein Element gerader Ordnung ist.
Ist dagegen [mm] $r^q \not\equiv [/mm] 1 [mm] \pmod{p}$, [/mm] und $r [mm] \not\equiv [/mm] -1 [mm] \pmod{p}$, [/mm] dann ist $r$ bereits eine Primitivwurzel modulo $p$. Da jedoch $2 [mm] \le [/mm] r [mm] \le [/mm] q$ ist, ist automatisch $r [mm] \not\equiv [/mm] -1 [mm] \pmod{p}$.
[/mm]
Somit ist Teilaufgabe b) i.A. falsch (siehe das Gegenbeispiel von ms2008de), Teilaufgabe c) jedoch richtig. Es gilt sogar: genau eine der beiden Zahlen $r$ und $-r$ ist Primitivwurzel modulo $p$.
LG Feix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:32 Do 17.06.2010 | | Autor: | marcsn |
Buef hat die Aufgabe falsch abgeschrieben....
Teil b lautet richtig:
$ [mm] r^{q} \equiv [/mm] $ +- 1 mod p
also entweder [mm] \overline{1} [/mm] oder [mm] \overline{-1}
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 03:39 Do 17.06.2010 | | Autor: | felixf |
Moin!
> Buef hat die Aufgabe falsch abgeschrieben....
>
> Teil b lautet richtig:
>
> [mm]r^{q} \equiv[/mm] +- 1 mod p
>
> also entweder [mm]\overline{1}[/mm] oder [mm]\overline{-1}[/mm]
Ah, dann macht das ganze gleich viel mehr Sinn :)
Fuer b) musst du uebrigens benutzen, dass die Gleichung [mm] $x^2 \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] genau zwei Loesungen hat: $x [mm] \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] und $x [mm] \equiv [/mm] -1 [mm] \pmod{p}$. [/mm] (Das liegt daran, dass [mm] $\IZ/p\IZ$ [/mm] ein Koerper ist und das Polynom [mm] $x^2 [/mm] - 1 = (x - 1) (x + 1) [mm] \in (\IZ/p\IZ)[x]$ [/mm] eine eindeutige Zerlegung in (normierte) Linearfaktoren hat.)
LG Felix
|
|
|
|
