#1 29. Dezember 2010 hi @ all häng grad bei ner aufgabe zu chin. restsatz...ich weis einfach nicht wie das multiplikative inverse funktionieren soll... Stand ist dass ich jetzt 5t=3mod 19 habe....und um die 5 da weg zu bekommen bräuchte ich dass multiplikative inverse von 5.... dann gibt es diese formel a*x+b*y = ggT(a,b) aber ich weis nicht was jetzt a, b, x und y ist ich hoffe ihr könnt mir helfen + Multi-Zitat Zitieren
#2 29. Dezember 2010 AW: chinesischer restsatz mit multiplikativem inveresem Ich arbeite mich selbst grade erst wieder ein, also pass gut auf, damit Du Dir das später sparst (man braucht sowas tatsächlich mal...) Folgendes freies (und kostenloses) Buch kann ich nur wärmsten empfehlen: Victor Shoup, "A Computational Introduction to Number Theory and Algebra", PDF: A Computational Introduction to Number Theory and Algebra Dort unter 4, bzw. 4.3 ist, was Du suchst. Ich muss mich, wiegesagt, erst selbst langsam wieder einlesen, sonst würde ich Dir etwas konkreter helfen + Multi-Zitat Zitieren
#3 29. Dezember 2010 AW: chinesischer restsatz mit multiplikativem inveresem ich verstehe gerade nicht ganz, wozu du den chinesischen restsatz hier brauchst, da du ja nur eine kongruenzgleichung hast, aber hier is eine ganz gute erklärung wie man deine kongruenzgleichung lösen kann(ganz unten bei "Ende der Aufgabe!"): http://www.mpipks-dresden.mpg.de/~mueller/download/old_uni/mathe/ChinesischerRestsatzUeb33-v4.pdf Wobei der ganze Artikel für dich interessant sein könnte bei dir wäre das dann: 5t = 3mod19 => 5t = 3+3*19 mod 19 => 5t = 60 mod 19 => t = 12 mod 19 + Multi-Zitat Zitieren
#4 30. Dezember 2010 AW: chinesischer restsatz mit multiplikativem inveresem Also in besagtem Buch ist es eigentlich ganz gut erklärt. Alles, was Du brauchst ist der erweiterte euklidische Algorithmus. Dein Modulus sei p=19 und Du willst das Inverse von a=5, dann setzt Du an: (d,s,t) <- gcd(p,a) Damit ein multiplikatives Inverse existiert, muss d=1 also a und p müssen relativ prim sein. Der erw. Euklid liefert Dir zudem s und t mit p*s + a*t = d = 1. Das multiplikative Inverse ist dann identisch mit diesem t, sofern t>0, andernfalls ist es t+p. Berechnen kannst Du das etwa händisch, indem Du genau den erw. Euklid durchgehst, oder meinetwegen auch mit MATLAB: [d,s,t]=gcd(p,a). Die genaue Begründung und den Beweis, warum das alles so ist, findest Du in dem besagten Buch. Demnacht ist 5^-1 = 4 (mod 19) Probe: 5*4 mod 19 = 1, stimmt. Für Dein Problem: 5t = 3 (mod 19) 5*4*t = 3*4 (mod 19) t = 12 (mod 19) Probe: 5*12 = 3 (mod 19), stimmt (Also wie Andi85 auch schon festgestellt hatte + Multi-Zitat Zitieren