Primitivwurzeln < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:43 So 18.01.2009 | | Autor: | Bob1982 |
| Aufgabe | zu zeigen: für eine Primitivwurzel g und eine ungerade Primzahl p gilt:
a) Es existiert ein k, so dass [mm]g^{k+1} \equiv g^k+1\ mod\ p[/mm]
b) Es existiert kein r, so dass [mm]g^{r+2} \equiv g^{r+1}+1 \equiv g^r+2 \ mod\ p[/mm] |
Ich dachte erst an einen indirekten Beweis, kam damit aber nicht weiter.
Nun ist das hier mein Ansatz (Indexnutzung)
[mm]g^{k+1} \equiv g^k+1\ mod\ p<=> g^k(g-1) \equiv 1\ mod\ p[/mm]
[mm]k \equiv -ind_g(g-1)\ mod\ p-1[/mm]
Diese Kongurenz sollte ja dann eine eindeutige Lösung haben oder ?
Analog dann b)
[mm]r \equiv ind_g(2)-ind_g(g^2-1)\ mod\ p-1[/mm]
Und hier muss dann irgendwo etwas sein, was nicht sein darf - aber ich finde es nicht...
Ist das überhaupt ein Idee, die mich hier weiterbringt ?
Gruß Björn
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:56 Di 20.01.2009 | | Autor: | felixf |
Hallo
> zu zeigen: für eine Primitivwurzel g und eine ungerade
> Primzahl p gilt:
>
> a) Es existiert ein k, so dass [mm]g^{k+1} \equiv g^k+1\ mod\ p[/mm]
>
> b) Es existiert kein r, so dass [mm]g^{r+2} \equiv g^{r+1}+1 \equiv g^r+2 \ mod\ p[/mm]
>
> Ich dachte erst an einen indirekten Beweis, kam damit aber
> nicht weiter.
> Nun ist das hier mein Ansatz (Indexnutzung)
>
> [mm]g^{k+1} \equiv g^k+1\ mod\ p<=> g^k(g-1) \equiv 1\ mod\ p[/mm]
Also [mm] $g^k \equiv [/mm] (g - [mm] 1)^{-1} \pmod [/mm] p$.
> [mm]k \equiv -ind_g(g-1)\ mod\ p-1[/mm]
Genau.
> Diese Kongurenz sollte ja dann eine eindeutige Lösung haben
> oder ?
Ja.
> Analog dann b)
>
> [mm]r \equiv ind_g(2)-ind_g(g^2-1)\ mod\ p-1[/mm]
Wie kommst du jetzt da drauf?
> Und hier muss dann irgendwo etwas sein, was nicht sein darf
> - aber ich finde es nicht...
Nun, in b) hast du zwei Gleichungen: [mm] $g^{r + 2} \equiv g^{r + 1} [/mm] + 1 [mm] \pmod{p}$ [/mm] und [mm] $g^{r + 1} [/mm] + 1 [mm] \equiv g^r [/mm] + 2 [mm] \pmod{p}$.
[/mm]
Was kannst du in den beiden Gleichungen jeweils ueber $r$ sagen?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:59 Di 20.01.2009 | | Autor: | Bob1982 |
| Aufgabe | zu zeigen: für eine Primitivwurzel g und eine ungerade Primzahl p gilt:
a) Es existiert ein k, so dass $ [mm] g^{k+1} \equiv g^k+1\ [/mm] mod\ p $
b) Es existiert kein r, so dass $ [mm] g^{r+2} \equiv g^{r+1}+1 \equiv g^r+2 [/mm] \ mod\ p $ |
> > [mm]r \equiv ind_g(2)-ind_g(g^2-1)\ mod\ p-1[/mm]
>
> Wie kommst du jetzt da drauf?
Ich habe [mm] g^{r+2} \equiv g^r+2\ mod\ p[/mm] analog wie oben nach r aufgelöst.
> Nun, in b) hast du zwei Gleichungen: [mm]g^{r + 2} \equiv g^{r + 1} + 1 \pmod{p}[/mm]
> und [mm]g^{r + 1} + 1 \equiv g^r + 2 \pmod{p}[/mm].
>
> Was kannst du in den beiden Gleichungen jeweils ueber [mm]r[/mm]
> sagen?
Dass sie jeweils für sich wegen a) eine Lösung haben müssen.
Da jedoch in beiden Kongruenzen derselbe Parameter r vorkommt darf die Lösung für die erste Kongruenz, die ich in a) ja angegeben habe, nicht auch noch die zweite Kongruenz erfüllen.
Wolltest du darauf hinaus bzw soll ich dann die Lösung aus a) einfach einsetzen und es ergibt sich damit ein Widerspruch (Unlösbarkeit) ?
Danke für deine Hilfe.
Gruß Björn
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:00 Di 20.01.2009 | | Autor: | felixf |
Hallo
> zu zeigen: für eine Primitivwurzel g und eine ungerade
> Primzahl p gilt:
>
> a) Es existiert ein k, so dass [mm]g^{k+1} \equiv g^k+1\ mod\ p[/mm]
>
>
> b) Es existiert kein r, so dass [mm]g^{r+2} \equiv g^{r+1}+1 \equiv g^r+2 \ mod\ p[/mm]
> > > [mm]r \equiv ind_g(2)-ind_g(g^2-1)\ mod\ p-1[/mm]
> >
> > Wie kommst du jetzt da drauf?
>
> Ich habe [mm]g^{r+2} \equiv g^r+2\ mod\ p[/mm] analog wie oben nach
> r aufgelöst.
>
> > Nun, in b) hast du zwei Gleichungen: [mm]g^{r + 2} \equiv g^{r + 1} + 1 \pmod{p}[/mm]
> > und [mm]g^{r + 1} + 1 \equiv g^r + 2 \pmod{p}[/mm].
> >
> > Was kannst du in den beiden Gleichungen jeweils ueber [mm]r[/mm]
> > sagen?
>
> Dass sie jeweils für sich wegen a) eine Lösung haben
> müssen.
Ja.
> Da jedoch in beiden Kongruenzen derselbe Parameter r
> vorkommt darf die Lösung für die erste Kongruenz, die ich
> in a) ja angegeben habe, nicht auch noch die zweite
> Kongruenz erfüllen.
Nun, das haengt davon ab wie die Kongruenzen aussehen. Schreib sie doch mal hier hin.
> Wolltest du darauf hinaus bzw soll ich dann die Lösung aus
> a) einfach einsetzen und es ergibt sich damit ein
> Widerspruch (Unlösbarkeit) ?
So ganz grob ungefaehr ja. Nur schreib doch mal hin was du hast.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:58 Di 20.01.2009 | | Autor: | Bob1982 |
| Aufgabe | zu zeigen: für eine Primitivwurzel g und eine ungerade Primzahl p gilt:
a) Es existiert ein k, so dass $ [mm] g^{k+1} \equiv g^k+1\ [/mm] mod\ p $
b) Es existiert kein r, so dass $ [mm] g^{r+2} \equiv g^{r+1}+1 \equiv g^r+2 [/mm] \ mod\ p $
|
> > Da jedoch in beiden Kongruenzen derselbe Parameter r
> > vorkommt darf die Lösung für die erste Kongruenz, die ich
> > in a) ja angegeben habe, nicht auch noch die zweite
> > Kongruenz erfüllen.
>
> Nun, das haengt davon ab wie die Kongruenzen aussehen.
> Schreib sie doch mal hier hin.
>
> > Wolltest du darauf hinaus bzw soll ich dann die Lösung aus
> > a) einfach einsetzen und es ergibt sich damit ein
> > Widerspruch (Unlösbarkeit) ?
>
> So ganz grob ungefaehr ja. Nur schreib doch mal hin was du
> hast.
Also ich denke ich habe es jetzt:
Aus a) folgt ja [mm] g^{r+1}-g^r=1 <=> r+ind_g(g-1) \equiv\ 0 [/mm]
Wenn so ein r aus b) existieren sollte müsste gelten:
[mm] g^{r+2}-g^r=2 <=> r+ind_g(g^2-1) \equiv\ ind_g(2)<=>r+ind_g(g-1)+ind_g(g+1) \equiv\ ind_g(2) [/mm]
Setzt man Gleichung 1 in die zweite ein so folgt:
[mm] ind_g(g+1)=ind_g(2) <=> g+1=2 <=> g=1 [/mm]
Und das ist ein Widerspruch, da g als Erzeuger nicht 1 sein kann.
Korrekt ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:20 Di 20.01.2009 | | Autor: | felixf |
Hallo
> zu zeigen: für eine Primitivwurzel g und eine ungerade
> Primzahl p gilt:
>
> a) Es existiert ein k, so dass [mm]g^{k+1} \equiv g^k+1\ mod\ p[/mm]
>
>
> b) Es existiert kein r, so dass [mm]g^{r+2} \equiv g^{r+1}+1 \equiv g^r+2 \ mod\ p[/mm]
>
> > > Da jedoch in beiden Kongruenzen derselbe Parameter r
> > > vorkommt darf die Lösung für die erste Kongruenz, die ich
> > > in a) ja angegeben habe, nicht auch noch die zweite
> > > Kongruenz erfüllen.
> >
> > Nun, das haengt davon ab wie die Kongruenzen aussehen.
> > Schreib sie doch mal hier hin.
> >
> > > Wolltest du darauf hinaus bzw soll ich dann die Lösung aus
> > > a) einfach einsetzen und es ergibt sich damit ein
> > > Widerspruch (Unlösbarkeit) ?
> >
> > So ganz grob ungefaehr ja. Nur schreib doch mal hin was du
> > hast.
>
> Also ich denke ich habe es jetzt:
>
> Aus a) folgt ja [mm]g^{r+1}-g^r=1 <=> r+ind_g(g-1) \equiv\ 0[/mm]
>
> Wenn so ein r aus b) existieren sollte müsste gelten:
>
> [mm]g^{r+2}-g^r=2 <=> r+ind_g(g^2-1) \equiv\ ind_g(2)<=>r+ind_g(g-1)+ind_g(g+1) \equiv\ ind_g(2)[/mm]
>
> Setzt man Gleichung 1 in die zweite ein so folgt:
>
> [mm]ind_g(g+1)=ind_g(2) <=> g+1=2 <=> g=1[/mm]
>
> Und das ist ein Widerspruch, da g als Erzeuger nicht 1 sein
> kann.
Genau.
Alternativ kann man auch die Gleichungen [mm] $g^{r+2} \equiv g^{r+1} [/mm] + [mm] 1\pmod{p}$ [/mm] und [mm] $g^{r+1} [/mm] + 1 [mm] \equiv g^r [/mm] + 2 [mm] \pmod{p} \Leftrightarrow g^{r+1} \equiv g^r [/mm] + 1 [mm] \pmod{p}$ [/mm] betrachten; daraus ergibt sich dass $1 [mm] \equiv [/mm] 0 [mm] \pmod{p - 1}$ [/mm] sein muss, also $p - 1 = 1$, also $p = 2$, ein Widerspruch.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:05 Mi 21.01.2009 | | Autor: | Bob1982 |
Vielen Dank für deine Hilfe, ich denke jetzt ist alles geklärt.
Gruß Björn
|
|
|
|
