x*a mod b = c - Methode zur Berechnung von x ?

Neue Frage »

PeterH Auf diesen Beitrag antworten »
x*a mod b = c - Methode zur Berechnung von x ?
Meine Frage:
Hallo alle miteinander,
Ich habe eine Frage für die ich einfach keine Antwort finde, die in meinen Augen jedoch auf den ersten Blick so lächerlich einfach erscheint, dass ich schon an mir selbst zweifle. Also: Gibt es eine andere Möglichkeit abgesehen vom Ausprobieren herauszufinden, für welche x die Gleichung (x*a mod b = c) gilt?
Vielleicht ein Beispiel, um es etwas deutlicher zu machen. Ich habe die Gleichung (x*13 mod 5 = 5). Nun Frage ich mich, für welche x dies gilt. Durch Probieren, habe ich die x-Werte 4,8,12,16... ermittelt. Also muss jedes x für das die Gleichung gleich 2 ist die allgemeine Gleichung (x = 4*z) gelten, wobei für z immer natürliche Zahlen eingesetzt werden. Aber was ist, wenn man z.B. (x*824781 mod 742 = 413) hat? Es ist doch idiotisch und unpraktisch, jede Zahl von 1 bis 742 einzeln durchzugehen. Gibt es da vielleicht eine (oder sogar mehrere) bessere Möglichkeit? Im Grunde reicht es ja schon, wenn man den ersten x-Wert, für den dies gilt herausfindet, da man ja dann für die folgenden eine allgemeine Formel herleiten kann (wie eben x = 4*z). Gibt es da irgendeine effektivere Möglichkeit?
Ich wäre über jede Art von Hilfe sehr dankbar.
Mit freundlichen Grüßen,
maddio14

Meine Ideen:
Bisher habe ich mir überlegt, dass sich diese Frage möglicherweise mit dem euklidischen Algorithmus angehen lässt, bin jedoch nicht sicher, wo ich anfangen soll.
AD Auf diesen Beitrag antworten »

Modulo rechnen
PeterH Auf diesen Beitrag antworten »

Schon erstaunlich, wie schnell und leicht es gehen kann. Ich hätte vorher wohl doch ein wenig recherchieren sollen. Danke dafür!
Neue Frage »
Antworten »



Verwandte Themen

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