Euklidischer Algorithmus mit modulo

Question

hab eine Frage zur folgenden Aufgabe:  a) und b) habe ich schon gerechnet und mit den musterlösungen verglichen stimmt auch alles soweit. Also bei a) kommt ggT(84,35)=7 und bei b) die Gleichung -2*84+5*35=7, also ist x=-2 und y=5.So nur bei der c) hab ich ein paar Schwierigkeiten. Mein Ansatz war folgender: 
aus b) wissen wir schon: 7=5*35 (mod 84) | das multipliziere ich jetzt mit 6 um links 42 rauszubekommen 7*6=6*(5*35) (mod 84) | das Z eine Gruppe ist, gilt auch die assoziativität42=(6*5)*35 (mod 84) 42=30*35 (mod 84) Also wäre z=30
Nach der musterlösung ist z aber 6. ist mein Ergebnis aber trotzdem richtig, da 30 nur ein Vielfaches von 6 ist?

Comments

Was genau ist mit .84 gemeint?
 ist mein Ergebnis aber trotzdem richtig, da 30 nur ein Vielfaches von 6 ist? 

Wenn 30 und 6 die angegebene "Gleichung" erfüllen, sind beide richtig. (Hast du zur Kontrolle nachgerechnet? ) Deine Begründung müsstest vermutlich du noch "begründen". 

Du sollst aber einfach eine Lösung der "Gleichung" angeben. Daher: Wenn 30 (auch) stimmt, bist du fertig.
Kann aber sein, dass die Frage mal so formuliert ist, dass du die "kleinste Lösung" angeben sollst. Daher wäre es gut, wenn du diese auch finden könntest.

Answer 1

  Infos zu dem Euklidischen Algoritmus.

  Ich wurde darauf hingewiesen, dass seine Konvergenzgeschwindigkeit = 2 * Stellenzahl.Ich hielt mich ferner für den Entdecker einer Modifikation von Euklid, bei welcher ab Quotient .5 aufgerundet wird, um die Konvergenz zu beschleunigen. So lange jedermann glaubte, ich sei der Entdecker, wurde ich angemacht ohne Ende, " das bringt doch nichts "

    In Wirklichkeit hat schon Kronecker diese Modifikation angegeben; er bewies gleichzeitig, dass sie die schnellst mögliche ist.

   Wie komplex ist die Suche nach dem ggt? Mehr wie Bitshift braucht es nicht; ===> Steinalgoritmus.

   Falls du das unstillbare Verlangen verspüren solltest, ===> lineare diophantische Gleichungen zu lösen. ===> Arndt Brünner hat ein ausgezeichnetes KI Werkzeug ins Netz gestellt.