Erweiterter Euklidischer Algorithmus?

Neue Frage »

Fetterchefkoch Auf diesen Beitrag antworten »
Erweiterter Euklidischer Algorithmus?
ich habe eine wirklich einfache Aufgabe...nur weiss ich nicht wie ich genau vorgehen soll.
Aufgabe:

Mein Ansatz (der leider falsch ist):
Mit dem Erweitertem Euklidschen Algorithmus!

Was ich jetzt als Resultat habe ist was ja auch stimmt... Was aber eigentlich nicht gewollt ist. Ich habe es auch schon probiert wie es bei Wikipedia (Erweiterter Euklidischer Algorithmus) steht. Jedoch hat auch das mir nicht weitergeholfen, da ich keine möglichkeit sehe wie ich in den Algorithmus einfügen muss.

Wolframalpha (Wolframalpha) sagt mir die Lösung ist was auch auf meiner Musterlösung stimmt. Leider wird mir nicht gesagt wie ich auf dieses Resultat komme (oder besser gesagt man sagt mir "verwende Erweiterter Euklidischen Algorithmus oder rate!").

Ich bedanke mich schon herzlichst im Voraus Big Laugh
lgrizu Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Du solltest den ggT(13,17)=1 mit dem Lemma von Bezout darstellen.

Zuerst einmal die Frage, was überhaupt ist, es ist die Restklasse mod 13, für die gilt .

Nun stelle einmal ggT(13,17) mit Euklid dar und dann rechne "Rückwärts".
Fetterchefkoch Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Bevor ich jetzt gefragt habe, versuchte ich trotzdem noch deinen Tipp irgendwie nutzbar zu machen. Das war schon sehr viel wert aber jetzt hab ich trotzdem doch noch ein problem mit deinem Tipp, nämlich:
Zitat:
Original von lgrizu
Nun stelle einmal ggT(13,17) mit Euklid dar und dann rechne "Rückwärts".


ggT(13,17) hab ich ja schon dargestellt. Dies ist 1.

Jedoch hab ich nicht ganz verstanden wie du das mit dem "Rückwärts" rechnen gemeint hast. Wäre hierbei noch um eine Erklärung froh.

Edit:
Du hast aber nicht zufälligerweise gemeint das ichs jetzt als linearkombination aufschreiben soll? Also oder?
lgrizu Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Okay, wir haben mit Euklid:

1.) 17=1*13+4
2.) 13=3*4+1
Nun ergibt sich aus 2.) 1=13-3*4 und aus 1.) 4=17-1*13 Wir setzen 4=17-1*13 in die Gleichung 1=13-3*4 ein und erhalten 1=13-3*(17-1*13)=4*13-3*17.

Nun ist sicherlich , also und damit haben wir das Inverse zu 17 gefunden, es ist -3, nun noch den kleinsten positiven Repräsentanten der Restklasse mod 13 bestimmen, in der -3 liegt und wir sind fertig.
Fetterchefkoch Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Hammer
Wow... ich hatte die Lösung also schon nach den ersten 5 min aber ich hab sie einfach nicht gesehen. Danke, dass du mich darauf aufmerksam gemacht hast, dass ich schlecht bin im Modulo rechnen.

Mein letztes wirkliches Problem ist: Wie komme ich von auf . Jedoch hab ich jetzt vollends kapiert wie man EEA macht Big Laugh
lgrizu Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Na, welche Elemente liegen denn in der selben Restklasse mod 13 wie -3?
 
 
Fetterchefkoch Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Zitat:
Original von lgrizu
Na, welche Elemente liegen denn in der selben Restklasse mod 13 wie -3?


Wie wäre es z.b. mit 1, 19, -5 und 8???

Scherz!
-29, -16, -3, 10, 23, 36
lgrizu Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Na also, und welches ist der kleinste positive Repräsentant dieser Restklasse?
Fetterchefkoch Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Natürlich die 10...
Vielen, vielen Dank Gott

Bin froh das ichs jetzt richtig gecheckt hab :P.

Geh jetzt endlich ins Bett xD. Gute nacht auch dir noch :P
lgrizu Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Okidokey, wenn du noch Fragen hast, melden. Wink
Fetterchefkoch Auf diesen Beitrag antworten »
RE: Erweiterter Euklidischer Algorithmus?
Ich hätte da grad nochmals ne Frage die dazu passt.
Wenn ich nun eine grosse Zahl Modulo rechnen muss wie muss ich dass denn machen?

z.B.:
das einzige was ich gefunden habe ist die "Square-and-Multiply"-Methode aber wenn ich keinen Taschenrechner benutzen darf dann brauch ich au für das extrem lange. (in der Prüfung wird wohl erwartet das man das in circa 5 min hat).
René Gruber Auf diesen Beitrag antworten »

In gewissen Konstellationen kann der Satz von Fermat bzw. Fermat-Euler die Berechnung vereinfachen helfen. Im vorliegenden Fall sieht das allerdings nicht danach aus.
Fetterchefkoch Auf diesen Beitrag antworten »

Danke für die schnelle Antwort, werde also auch noch den Satz von Fermat ein bisschen anschauen.

Gibts noch andere Möglichkeiten, wie ich Modulo schneller berechnen kann?
lgrizu Auf diesen Beitrag antworten »

Quadratzahlen und Primteiler kennen und erkennen, dabei hilft üben , üben, üben. Augenzwinkern
Fetterchefkoch Auf diesen Beitrag antworten »

Könntest du mir anhand dieses Beispieles sagen wie du vorgehen würdest?

Ich kann ja mal sagen was ich mir so überlegt habe:
ja... da hab ich schon keinen bock mehr im kopf zu rechnen.

Falls du also auch keine Lust hast dann verstehe ich das sehr sehr sehr sehr sehr gut.

Jedoch hab ich noch ne andere Frage zum EEA mit einem Erweiterungskörper:
Aufgabe: (weiss auch nicht wieso das die Klammer bei ist. Die macht für mich keinen Sinn)

Was ich probiert habe: ist eine Variable die ich nachher ersetze damit ich möglichst wenig Rest bekomme. Also:
. Ich hätte jetzt gedacht der Rest wird minimal wenn ich wähle jedoch sagt mir meine Musterlösung das ich wählt (zumindest glaub ich dass es mir das sagen will Big Laugh ). Ich habe das dann auch eingesetzt jedoch habe ich dann den wesentlich grösseren Rest bekommen.

Ich habe jetzt also keine Ahnung wie man auf die Lösung kommen sollte. Vielleicht hab ich schon von anfang an einen Fehler gemacht :P. Wäre jedenfalls sehr froh um Hilfe smile
lgrizu Auf diesen Beitrag antworten »

Es ist



usw.

Kann man im Kopf rechnen....
Neue Frage »
Antworten »



Verwandte Themen

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