Erzeuger, Einheitengruppe < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe eine Frage zu Erzeugern bzgl. einer Einheitengruppe [mm] \IZ_{p}^{ \*} [/mm] (p Prim), und der Untergruppe der quadratischen Reste von [mm] \IZ_{p}^{ \*}, [/mm] also der betrachteten Einheitengruppe.
Erstmal was ein quadratischer Rest ist:
Eine Zahl a [mm] \in \IZ [/mm] heißt quadratischer Rest modulo n>0, wenn ggT(a,n)=1 und es ein b [mm] \in \IZ [/mm] gibt mit [mm] b^2 [/mm] mod n = a mod n.
So, wenn ich jetzt einen Erzeuger g von der Einheitengruppe [mm] \IZ_{p}^{ \*} [/mm] habe, kann g dann überhaupt ein quadratischer Rest sein?
Ich habe mir dazu folgendes überlegt:
Da g Erzeuger von [mm] \IZ_{p}^{ \*} [/mm] ist, dann ist [mm] \IZ_{p}^{ \*} [/mm] = { [mm] g^i [/mm] | für alle i [mm] \in [/mm] {0,...,| [mm] \IZ_{p} [/mm] *|-1} }. Daraus folgt dann, dass
g mod p = [mm] g^2 [/mm] mod p nicht gilt, da [mm] g^2 [/mm] ein anderes Element aus [mm] \IZ_{p}^{ \*} [/mm] ist, aber aufjedenfall nicht g.
Stimmt das so, oder ist das völliger blödsinn? ;)
Danke schon mal!
|
|
|
|
> Hallo,
>
> ich habe eine Frage zu Erzeugern bzgl. einer
> Einheitengruppe [mm]\IZ_{p}^{ \*}[/mm] (p Prim), und der
> Untergruppe der quadratischen Reste von [mm]\IZ_{p}^{ \*},[/mm] also
> der betrachteten Einheitengruppe.
>
> Erstmal was ein quadratischer Rest ist:
> Eine Zahl a [mm]\in \IZ[/mm] heißt quadratischer Rest modulo n>0,
> wenn ggT(a,n)=1 und es ein b [mm]\in \IZ[/mm] gibt mit [mm]b^2[/mm] mod n =
> a mod n.
>
> So, wenn ich jetzt einen Erzeuger g von der Einheitengruppe
> [mm]\IZ_{p}^{ \*}[/mm] habe, kann g dann überhaupt ein
> quadratischer Rest sein?
> Ich habe mir dazu folgendes überlegt:
> Da g Erzeuger von [mm]\IZ_{p}^{ \*}[/mm] ist, dann ist [mm]\IZ_{p}^{ \*}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> = { [mm]g^i[/mm] | für alle i [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
{0,...,| [mm]\IZ_{p}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
*|-1} }. Daraus
> folgt dann, dass
> g mod p = [mm]g^2[/mm] mod p nicht gilt, da [mm]g^2[/mm] ein anderes Element
> aus [mm]\IZ_{p}^{ \*}[/mm] ist, aber aufjedenfall nicht g.
>
> Stimmt das so, oder ist das völliger blödsinn? ;)
So stimmt es nicht, da g quadratischer Rest ja nicht bedeutet, dass [mm] g^2=g [/mm] (mod p) gilt.
Trotzdem lässt sich der Beweis "retten": Du nimmst an, dass es ein b mit [mm] b^2=g [/mm] (mod p) gibt. Nach dem kleinen Satz von Fermat ist [mm] b^{p-1}=1 [/mm] (mod p), woraus du folgern kannst, dass g kein Erzeuger sein kann.
>
> Danke schon mal!
>
>
|
|
|
|
|
Tut mir leid, aber ich verstehe nicht so richtig was du meinst. Was hat denn aufeinmal [mm] b^{p-1} [/mm] mod p = 1 damit zu tun? Ich möchte doch ein [mm] b^{2} [/mm] haben...?
|
|
|
|
|
Aus [mm] a^2=b [/mm] und [mm] b^{p-1}=1 [/mm] folgt [mm] a^{(p-1)/2}=1, [/mm] womit a kein Erzeuger sein kann.
|
|
|
|