Modulo Gleichungssystem lösen

Neue Frage »

0664jester Auf diesen Beitrag antworten »
Modulo Gleichungssystem lösen
Hallo, smile



kann mir jemand helfen wie man auf die Lösung kommt, Ich habe schon einiges durchprobiert...

Lösungsansatz, welcher falsch ist:
meine Rechnung:
m=4*5 = 20, // m gesamt
m/m1=5, // 20/4 = 5
m/m2=4 // 20/5 = 4


//ggt(5/4), wobei m/m1 = 5 und 4 = m1
1 0 1 = ai
0 0 -1
- - 1
5 4 1

//ggt(4/5)
1 0 1 -1 = ai
0 1 0 1
- - 0 1
4 5 4 1

ci*ai*(m/mi)
0*1*4+1*(-1)*5 = -5


Wolfram alpha sagt aber 16.

Gruß,
jester
mYthos Auf diesen Beitrag antworten »

Was bzw. wie du das gerechnet hast, weiss ich jetzt nicht, aber 16 ist nicht die einzige Lösung, sondern 16 mod 20.

Bei Modulo-Rechnungen kann man auch einen Ansatz verfolgen, der auf Gleichungen mit ganzzahligen Variablen beruht (sh. auch euklid'scher Algorithmus).

Die Angabe kann umgeschrieben werden zu

x = 4r
x = 5s + 1
-------------
Bei Gleichsetzen entsteht
4r = 5s + 1

Die Lösungen - vorzugsweise mittels einer weiteren gemeinsamen Variablen (t) parametrisiert, sind in die obigen Gleichungen einzusetzen (r = 4, s = 3 ist ein einzelnes Lösungspaar).
Man sollte schließlich x = 20t + 16 erhalten.

mY+
 
 
0664jester Auf diesen Beitrag antworten »

Gib es einen Namen für diese Umschreibung?
Damit ich danach googlen kann.


Danke,
jester
mYthos Auf diesen Beitrag antworten »

Ich denke, es ist der erweiterte euklidischer Algorithmus, z.B. steht hier etwas darüber.

Aus Zeitmangel habe ich mir allerdings jetzt nicht genauer angesehen, ob dies deine Aufgabe vollständig abdeckt ...

mY+
0664jester Auf diesen Beitrag antworten »

Ich habe jetzt schon so viele Varianten gesehen.

Ich bin mehr oder weniger nach diesem vorgegangen, weil der generator so rechnet, wie ich es gelernt habe.
Aber dieses Mal spuckt er wieder kein Brauchbares ergebnis raus.


Link

Vielleicht macht mein Gekritzel weiter oben jetzt mehr Sinn.

Ich vermute, da es diese 0 bei 0 mod 4 gibt und nicht wie gewöhnlich bei 1 beginnt.



jester
mYthos Auf diesen Beitrag antworten »

Der Calculator ermittelt x = - 4 als Lösung, dazu muss aber festgehalten werden, dass diese modulo 20 gilt. Und damit ist sie ja auch richtig, denn addierst du 20, so erhältst du 16, welche die erste positive Lösung ist.

Im Übrigen war mein Hinweis zu dem erweiterten euklidischen Algorithmus doch zielführend, oder?
Der ursprünglich gezeigte Lösungsweg funktioniert im Grunde genommen ja auch damit.

mY+
MatheMaster_93 Auf diesen Beitrag antworten »

Die rechnung funktioniert ganz einfach, wenn man mit Hilfe des euklidsichen Algorthmus das Inverse modulo einer Zahl findet, um die Gleichung mit dieser Zahl zu multiplzieren, um dann eben die 1 vor der Variablen stehen zu haben:

Aus x = 4r = 5s + 1 folgt ja



Mit dem euklidischen Algorithmus kann man das Inverse von 4 mod 5 berechnen. Das kann man bei solchen Zahlen auch ausprobieren. Multipliziert man dann die Gleichung mit dem Inversen steht schon das gwünschte da.
0664jester Auf diesen Beitrag antworten »

ich habs nun begriffen smile

danke euch Freude
Neue Frage »
Antworten »



Verwandte Themen

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