Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Elemente einer abelschen Gruppe berechnen » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 10 Beiträge
eulerscheZahl

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

erweiterter euklidscher Algorithmus
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
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.
BonKeri

Hallo,

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

Danke
eulerscheZahl

richtig gerechnet. Daumen hoch
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?
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.
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.
eulerscheZahl

Den zweiten Fall, bzw. eine Abwandlung davon:
[latex]\varphi(a\cdot b \cdot c) = (a-1) \cdot (b-1) \cdot (c-1)[/latex]
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?
Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen.