Euklidischer Algorithmus 91x+77y=14 . Diophantische Gleichung

Question

Halloooooooo,

ich soll folgende Gleichung mittels des erweiterten euklidischen Algorithmus lösen 91x+77y=14.

Ich habe jetzt durch den Algorithmus den ggT von 91 und 77 ausgerechnet, der lautet 7, sprich -5*91+6*77=7 . So jetzt lag es auf der Hand, dass man x und y einfach verdoppelt damit auch das Ergebnis veroppelt wird also 14 rauskommt.

Das habe ich jetzt aber nur intuitiv gemacht und weiß dementscprechend nicht, wie man x und y so wählt das 14 rauskommt. Ich habe das Gefühl, dass das echt simpel ist, habe aber keine Ahung ^^.

   -Clara

Answer 1

das hier müsste dir weiterhelfen:

https://www.youtube.com/watch?v=yKqq25BD7Qo

Comments

jeeeein soweit war ich ja auch mehr oder weniger aber dieser Verfahren gibt mir ja nur ein x und y paar zu Lösung der Gleichung, meine Aufgabe verlangt aber 2 Paare und wenn man die hier raten könnte muss ich ja das Prinzip verstehen :/ naja trz danke

---

Naja, das hattest du nicht erwähnt.

"So jetzt lag es auf der Hand, dass man x und y einfach verdoppelt damit auch das Ergebnis veroppelt wird also 14 rauskommt. "

Du berechnest ja den größten gemeinsamen Teiler mit euklid. In deinem Fall ist das die 7.Gleichungen der Form : ax+bx=c haben nur ganzzahlige Lösungen, wenn c durch den ggT teilbar ist.  Du wirst also entweder deine Gleichung multiplizieren können und eine Lösung erhalten oder du wirst es nicht ganzzahlig multiplizieren können um auf c zu kommen, dann gibt es aber auch keine ganzzahlige Lösung.

Wenn du die eine Lösung oben nimmst, erhältst du mit:

x = (-10+g*77)

y= (12-g*91)

weitere Lösungen.

(Allgemein würde es sein:

x = x₀+ g *b
y= y_o - g*a

)

Answer 2

Hallo Clara,

welch Zufall. In meiner Übung muss ich auch zwei Zahlen x, y ∈ ℤ finden. Jedoch steht nix von zwei Zahlenpaaren.

Deine Antwort liegt damit bereits in der Frage:

91x + 77y = 7 | *2  (dein Ergebnis des ggT so multiplizieren das 14 rauskommt)

91*(-5)*2 +  77*6*2 = 14

91*(-10) + 77*12 = 14

Also x = -10 und y = 12

Setze sie mal ein und du siehst das es funktioniert.

Ist vielleicht jetzt eine ziemlich primitive Methode im Gegensatz zu dem Video hier, liefert jedoch das richtige Ergebnis. Im Skript ist auch kein echter Bezug zu den Rechenwegen der Lösung diophantischer Gleichungen nach dem Euklid.

Grüße aus Darmstadt