Modulo rechnen

Neue Frage »

Pätti Auf diesen Beitrag antworten »
Modulo rechnen
Meine Frage:
Hallöchen smile
alsooo ich hab ein problem.

Bestimme eine Zahl a ? {0, 1, . . . , 4710} mit:


Kann mir jemand sagen wie ich a sinnvoll bestimme?



Meine Ideen:
Ich hab versucht den Euklidischen Algorithmus anzuwenden und somit das Multiplikativ Inverse von 1001 mod 4711 zu bestimmen. Kam als Ergebnis -80 raus. kann aber nicht sein laut Aufgabenstellung.

Hab viele Sachen hin und her probiert kam aber nicht aufs Ergebnis.
Habs dann Mittels "Bruthe Force" und Excel gelöst. Das Ergebnis ist 593.

Aber da ich darauf auch in der Prüfung ohne Taschenrechner kommen soll bin ich absolut hilflos .. kann mir einer eklären wie ich schneller auf die Lösung komme.

Eyklisdischer Algorithmus bei diesen Zahlen ist übrigens auch nicht besonders schnell.

Vielen Dank schon mal
chrizke Auf diesen Beitrag antworten »

-80 ist richtig, du musst es nur noch in den passenden Intervall 'umrechnen'.
 
 
Pätti Auf diesen Beitrag antworten »

ok habsch gemacht

komm ich auf a = 4151 ... kann aber nicht die lösung sein weil
1001*4151 = 49 (mod 4711) und nicht = 7...jetzt bin ich verwirrt Hammer

also wie gesagt mit excel und bruthe force komme ich auf 593 und dann stimmt die gleichung auch .. kannst du mir das noch anders erklären?
chrizke Auf diesen Beitrag antworten »

Es ist ja auch



Es gilt vielmehr:

mYthos Auf diesen Beitrag antworten »

brute force, alles andere ist brutal und nicht bruthal Big Laugh

mY+
Pätti Auf diesen Beitrag antworten »

Ahhh ok klar verrechnet ^^ weiß wie du das meinst

Danke smile

Gibt es noch eine andere Möglichkeit das zu berechnen?
Bei diesen Zahlen wird das ganz schnell ziemlich stressig das zu berechen.

Warum gibt es eig. mehrere Lösungen?
AD Auf diesen Beitrag antworten »

Zur Lösung solcher linearer Kongruenzen



mit "großen" Modulen zieht du am besten den Erweiterten Euklidischer Algorithmus (EEA) zur Bestimmung von hinzu:

Der bestimmt nämlich zum einen selbst, was zur Klärung der Lösbarkeit von (*) benötigt wird, denn (*) besitzt genau dann Lösungen, wenn . Ist das der Fall, dann ermöglichen die vom EEA gelieferten Koeffizienten mit der Eigenschaft auch gleich den Schlüssel zur Lösung. Dann folgt aus (*) nämlich , was zu den Lösungen

mit

führt.


Hier eine Javascript-Seite zur Online-Berechnung mittels EEA: http://www.mirsky.de/ggt.php, die liefert für die Werte mit den Lösungen

für .
Pätti Auf diesen Beitrag antworten »

huiii ... danke !!!

hab zwar ne weile gebraucht bis ich kapiert hab was da stand ^^ .. aber das macht die sache um einiges einfacher smile
Neue Frage »
Antworten »



Verwandte Themen

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