Rechnen mit Gruppen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:20 Do 02.07.2015 | | Autor: | riju |
| Aufgabe | Berechnen Sie
a) [mm] 100^{61}[/mm] [mm] (mod 61) [/mm]
b) [mm] ((1247)(132))^{62}
[/mm]
[mm] c)ord(-0,2+\IZ) [/mm] in der Faktorgruppe von [mm] \IQ [/mm] nach [mm] \IZ [/mm] |
Hallo,
ich bereite mich gerade auf ein Testat vor und möchte dafür die oben genannte Aufgabe lösen.
zu a) ich nehme mal an, dass es sich um die Gruppe [mm] (\IZ_{61},\*) [/mm] handelt.
die Ordnung der Gruppe ist [mm] ord(\IZ_{61})=61
[/mm]
somit kann ich hier den kleinen fermatschen Satz anwenden: [mm] a^{ord(G)}=e
[/mm]
somit ist [mm] 100^{61}=1[/mm] [mm] (mod 61) [/mm]
Ist das richtig?
bei b) und c) habe ich leider keine Ahnung wie ich vorgehen soll.
Könnt ihr mir vllt da einen Tipp geben?
Wir haben leider in der Vorlesung dafür keine Beispiele
Vielen Dank
Liebe Grüße
riju
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:02 Do 02.07.2015 | | Autor: | Marcel |
Hallo,
> Berechnen Sie
> a) [mm]100^{61}[/mm] [mm](mod 61)[/mm]
> zu a) ich nehme mal an, dass es sich um die Gruppe
> [mm](\IZ_{61},\*)[/mm] handelt.
ich kenne Eure Notationen nicht, aber ich würde wenigstens
[mm] $(\IZ^\times_{61},\*)$
[/mm]
schreiben.
> die Ordnung der Gruppe ist [mm]ord(\IZ_{61})=61[/mm]
Nein, das wäre die von [mm] $(\IZ_{61},+)$. [/mm] 61 ist aber Primzahl, daher ist die Ordnung
der obigen multiplikativen Gruppe einfach =61-1=60.
("Entfernung der *störenden Null*.")
> somit kann ich hier den kleinen fermatschen Satz anwenden:
> [mm]a^{ord(G)}=e[/mm]
> somit ist [mm]100^{61}=1[/mm] [mm](mod 61)[/mm]
>
> Ist das richtig?
Das ist nun ein Folgefehler: Wir wissen nun
[mm] $100^{60} \equiv [/mm] 1$ mod 61,
oder wegen $100 [mm] \equiv [/mm] 39 [mm] \equiv [/mm] 1$ mod 61:
$1 [mm] \equiv 100^{60} \equiv 39^{60}$ [/mm] mod 61
also
[mm] $100^{61}\equiv 39*39^{60} \equiv [/mm] 39*1=39$ mod 61.
Ich mag' es, sowas auch nochmal mit einem Rechner/Programm nachzu-
kontrollieren:
Wenn man das etwa mit Octave testen will, musst Du beachten, dass
dort die Exponenten zu groß werden (teste einfach mod(100^(61),61),
dann spuckt Octave 0 raus, und dann müsste bei mod(100^(61)+1,61) halt
1 rauskommen, aber es kommt wieder 0 raus).
Daher kann man sich folgende Schleife schreiben (naiv programmiert - es
gibt intelligentere Rechenmethoden):
| 1: | z0 = mod(100,61);
| | 2: | z(1)=z0;
| | 3: | for k=2:61
| | 4: | z(k)=mod(z(k-1)*z(1),61);
| | 5: | end
| | 6: | fprintf(['\n\nAusgabe von mod(z^61,61): ',num2str(z(61)),' \n']);
|
P.S. z(k) gibt Dir dort an, was [mm] $100^k \equiv 39^k$ [/mm] mod 61 ist. Test:
z(3) hat den Wert 27. Nun ist in der Tat
[mm] $100^3 \equiv 39^3=1521*39 \equiv [/mm] 57*39=2223 [mm] \equiv [/mm] 27$ mod 61.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:23 Do 02.07.2015 | | Autor: | riju |
> Berechnen Sie
b) [mm]((1247)(132))^{62}[/mm]
Ich rechne erstmal [mm] (1247)(132) [/mm]:
[mm](1247)(132)=(1347) [/mm] (wir rechnen von hinten nach vorn)
Für Permutationen p der Länge k gilt [mm] p^{k-1}=id [/mm] und [mm] p^{k} =p[/mm]
[mm] (1347)^{62}=(1347)^{3*20+2}=((1347)^{3})^{20}(1347)^{2}=(id)^{20}(1347)^{2}=(1347)(1347)=(14)(37) [/mm]
Ist das richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:15 Fr 03.07.2015 | | Autor: | felixf |
Moin!
> > Berechnen Sie
>
> b) [mm]((1247)(132))^{62}[/mm]
>
> Ich rechne erstmal [mm](1247)(132) [/mm]:
>
> [mm](1247)(132)=(1347)[/mm] (wir rechnen von hinten nach vorn)
![[ok]](/images/smileys/ok.gif "[ok]")
> Für Permutationen p der Länge k gilt [mm]p^{k-1}=id[/mm] und [mm]p^{k} =p[/mm]
Das kann nicht stimmen: wenn du $p = (1 2)$ nimmst -- hier ist $k = 2$ -- dann ist [mm] $p^{k-1} [/mm] = p [mm] \neq [/mm] id$ und [mm] $p^k [/mm] = [mm] p^2 [/mm] = id$.
Allgemein gilt: [mm] $p^k [/mm] = id$ und [mm] $p^{k+1} [/mm] = p$.
> [mm](1347)^{62}=(1347)^{3*20+2}=((1347)^{3})^{20}(1347)^{2}=(id)^{20}(1347)^{2}=(1347)(1347)=(14)(37)[/mm]
>
> Ist das richtig?
Jein. Da $62 [mm] \bmod [/mm] 4 = 2 = 62 [mm] \bmod [/mm] 3$ ist, kommt das richtige heraus. Der Rechenweg dorthin ist jedoch nicht ganz korrekt.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Sa 04.07.2015 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
