Elemente einer abelschen Gruppe berechnen |
yuro123
Mitglied
Dabei seit: 09.12.2013
Beiträge: 35
|
|
Elemente einer abelschen Gruppe berechnen |
|
Hi,
und zwar habe ich eine Frage zu abelsche Gruppen. Meine Aufgabe lautet:
Es werde die Gruppe (Zn*, ×) mit n = 2×7×17 = 238 betrachtet.
Berechnen Sie die Anzahl der Elemente von (Zn*,×).
Also wir hatten mal eine Aufgabe mit n=26 wo ich alle Zahlen von 1...25 mittels ggT(a,26) berechnet und so alle Elemente bekommen habe.
Nur für n = 238 wäre das ein wenig viel.. Gibt es eine andere Möglichkeit die Elemente zu berechnen?
|
|
15.07.2015 12:29 |
|
|
|
Ich bin bei der Mathematik nicht komplett im Bilde, was musst du denn berechnen?
Du schreibst etwas vom ggT, falls du wissen willst, wie viele Zahlen teilerfremd sind, schau' dir mal die eulersche Phi Funktion an.
PS:
ich weiß nicht, ob du meine Antwort auf deine letzte Frage noch gelesen hast, daher verlinke ich nochmal:
Substitutionschiffre
__________________ Syntax Highlighting fürs Board (Link)
|
|
15.07.2015 14:37 |
|
|
yuro123
Mitglied
Dabei seit: 09.12.2013
Beiträge: 35
|
|
Danke für deine ausführliche Antwort aus dem letzten Thread. Das hat sich mittlerweile geklärt, da ich die Lösungen dazu bekommen habe und es garnicht so schwer war wie ich dachte..
zu diesem Thread: Es geht um die modulare Arithmetik und Gruppen. Wenn ich jetzt genauer im Skript nachschaue geht es um prime Restklassengruppen modulo n (Zn*, ×)
Laut Skript steht: Die Anzahl der Elemente von Zn* ist durch die eulersche Phi-Funktion Phi(n) bestimmt. Deren Werte können in den folgenden Fälle besonders einfach berechnet werden.
i) n = p (Primzahl), dann gilt Phi(p) = p-1
ii) n = p*q (Produkt 2er Primzahlen mit p!=q), dann gilt Phi(p*q) = (p-1)(q-1)
iii) n = p^k, k € N (Potenz einer Primzahl), dann gilt ggT(p^k, n) != 1 nur für alle Vielfachen von p. Daher gilt Phi(p^k) = p^k - p^k-1 = p^k-1(p-1)
Die Aufgaben lauten:
Es werde die Gruppe (Zn*, ×) mit n = 2×7×17 = 238 betrachtet.
a) Berechnen Sie die Anzahl der Elemente von (Zn*, ×).
b) Existiert das zu a = 65 multiplikativ inverse Element a^-1? (Antwort mit Begründung!)
c) Berechnen Sie mit Hilfe des Erweiterten Euklidischen Algorithmus das zu a = 57 multiplikativ inverse Element a^-1. Bestätigen Sie Ihr Ergebnis mit einer Proberechnung.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von yuro123: 15.07.2015 15:07.
|
|
15.07.2015 14:53 |
|
|
yuro123
Mitglied
Dabei seit: 09.12.2013
Beiträge: 35
|
|
Also n ist ja das Produkt von 3 Primzahlen.. (2,7,17) = 238 ... dann müsst ich den 3. Fall nehmen mit den Potenzen oder?
|
|
15.07.2015 15:06 |
|
|
yuro123
Mitglied
Dabei seit: 09.12.2013
Beiträge: 35
|
|
d.h. dann hätte ich:
(a-1) * (b-1) * (c-1)
(2-1) * (7-1) * (17-1)
1 * 6 * 16
= 96
Das wäre aber dann nicht das Ergebnis oder? Da ja 96 keine Primzahl ist.
|
|
16.07.2015 23:46 |
|
|
|
Das heißt, dass es 96 Zahlen gibt, die zu 238 teilerfremd sind und für die es somit ein multiplikativ inverses gibt.
Etwas pari/gp, um die besagten Zahlen zu bestimmen:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
|
? for(i=1,238,if(gcd(i,238)==1,printf("%8d",i)))
1 3 5 9 11 13 15 19 23 25
27 29 31 33 37 39 41 43 45 47
53 55 57 59 61 65 67 69 71 73
75 79 81 83 87 89 93 95 97 99
101 103 107 109 111 113 115 117 121 123
125 127 129 131 135 137 139 141 143 145
149 151 155 157 159 163 165 167 169 171
173 177 179 181 183 185 191 193 195 197
199 201 205 207 209 211 213 215 219 223
225 227 229 233 235 237
|
|
Es sind nicht zwingend Primzahlen, sondern nur Zahlen, die nicht durch 2, 7 oder 17 teilbar sind.
Die 9(=3*3) oder die 125(5^3) sind in der Liste vorhanden.
__________________ Syntax Highlighting fürs Board (Link)
|
|
17.07.2015 14:34 |
|
|
BonKeri
Grünschnabel
Dabei seit: 23.07.2015
Beiträge: 3
|
|
Hallo,
könntest du bitte die Antwort B) besser beschreiben, ich verstehe es nicht so richtig ?
Danke
|
|
23.07.2015 15:11 |
|
|
|
Dass ein multiplikativ Inverses existiert, heißt:
Wenn 65 und 238 teilerfremd sind, wird man in Restklasse 238 jeden Wert in [0;237] erhalten, folglich auch 1.
__________________ Syntax Highlighting fürs Board (Link)
|
|
23.07.2015 16:21 |
|
|
BonKeri
Grünschnabel
Dabei seit: 23.07.2015
Beiträge: 3
|
|
danke erstmal für die schnelle Antwort.
Ich meinte eigentlich, ob du mir zeigen könntest wie er die 11 herausgefunden hat?
Vielen Dank im voraus
|
|
23.07.2015 18:42 |
|
|
|