Informatiker Board | Druckvorschau: Elemente einer abelschen Gruppe berechnen

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Elemente einer abelschen Gruppe berechnen (http://www.informatikerboard.de/board/thread.php?threadid=2392)

Geschrieben von yuro123 am 15.07.2015 um 12:29:

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?

Geschrieben von eulerscheZahl am 15.07.2015 um 14:37:

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

Geschrieben von yuro123 am 15.07.2015 um 14:53:

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.

Geschrieben von yuro123 am 15.07.2015 um 15:06:

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?

Geschrieben von eulerscheZahl am 15.07.2015 um 15:15:

Den zweiten Fall, bzw. eine Abwandlung davon:
$[latex]\varphi(a\cdot b \cdot c) = (a-1) \cdot (b-1) \cdot (c-1)[/latex]$

Geschrieben von yuro123 am 16.07.2015 um 23:46:

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.

Geschrieben von eulerscheZahl am 17.07.2015 um 14:34:

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.

Geschrieben von yuro123 am 18.07.2015 um 16:55:

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?

Geschrieben von eulerscheZahl am 18.07.2015 um 18:23:

richtig gerechnet. Daumen hoch

Geschrieben von BonKeri am 23.07.2015 um 15:11:

Hallo,

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

Danke

Geschrieben von eulerscheZahl am 23.07.2015 um 16:21:

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.