Elemente einer abelschen Gruppe berechnen

Neue Frage »

Auf diesen Beitrag antworten »
yuro123 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?
 
Auf diesen Beitrag antworten »
eulerscheZahl

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
Auf diesen Beitrag antworten »
yuro123

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.
Auf diesen Beitrag antworten »
yuro123

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?
 
Auf diesen Beitrag antworten »
eulerscheZahl

Den zweiten Fall, bzw. eine Abwandlung davon:
[latex]\varphi(a\cdot b \cdot c) = (a-1) \cdot (b-1) \cdot (c-1)[/latex]
Auf diesen Beitrag antworten »
yuro123

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.
Auf diesen Beitrag antworten »
eulerscheZahl

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.
Auf diesen Beitrag antworten »
yuro123

Ok.. nur frage ich mich ob es das richtige Ergebnis ist?

Zur B) hab ich berechnet, dass ggT(65, 238) = 1 gilt und ein multiplikatives Inverses Element existiert a^-1 = 11.. soweit das richtig ist.

Zur C) der ggT(57,238) = 1 ergibt die folgende Rückwärtsberechnung:

1 = 7 -2 * 3
= 7 -2 * (10-1*7) = -2*10+3*7
= -2*10+3(57-5*10) = 3*57-17*10
= 3*57-17(238-4*57) = -17*238+71*57

Daraus ergibt sich: 71*57 mod 238 = 1

Das modulare Inverse ist somit 71?!

Stimmt das so?
Auf diesen Beitrag antworten »
eulerscheZahl

richtig gerechnet. Daumen hoch
Auf diesen Beitrag antworten »
BonKeri

Hallo,

könntest du bitte die Antwort B) besser beschreiben, ich verstehe es nicht so richtig ?

Danke
Auf diesen Beitrag antworten »
eulerscheZahl

Dass ein multiplikativ Inverses existiert, heißt:
[latex]65 \cdot n \equiv 1 \mod 238[/latex]
Wenn 65 und 238 teilerfremd sind, wird man in Restklasse 238 jeden Wert in [0;237] erhalten, folglich auch 1.
Auf diesen Beitrag antworten »
BonKeri

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
Auf diesen Beitrag antworten »
eulerscheZahl

Schau mal, ob du den Wikipediaartikel verstehst.
Wenn nicht, schreibe ich noch ein paar Zeilen.

erweiterter euklidscher Algorithmus
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »