Diophantische Gleichung, erweiterter Euklidischer Algorithmus: 27x + 45y = 18.

Question

Ich muss eine Diophantische Gleichung lösen und wollte den erweiterten Euklidischen Algorithmus anwenden aber es scheint nicht zu funktionieren!

Hier ist ein Foto von meinem Versuch. Was mache ich falsch?

EDIT (Lu) Gleichung in der Überschrift dem Kommentar angepasst. Konnte die Handschrift nicht lesen.

Comments

Was hast du denn jetzt raus?

Answer 1

Wenn du für x und y keine negativen Werte haben willst, scheint das nicht zu gehen. Die blaue Linie im 1. Quadranten liegt sozusagen "zu weit unten".

Sonst aber schon.

Comments

Aber wieso geht der erweiterte Euklidische Algorithmus nicht?

Wie kann ich es sonst lösen?

---

Hast du ein Beispiel einer Gleichung, bei der es funktioniert hat?

Wenn du das hochladen kannst, könnte ich später mal vergleichen.

Suchst du ganzzahlige oder natürliche Lösungspaare?

Natürliche gibt es nicht.

---

Suche nur ganzzahlige Lösungen. 

Dieses YouTube Video zeigt wie es gehen sollte.

---

Ahh ich sehe gerade, du hast auch 49 statt 45 geschrieben. Es sieht bei mir zwar aus wie 49, aber es 45.

Im Titel hat auch jemand 49 geschrieben, das war nicht ich.

Answer 2

(1)  49 : 27 = 1  Rest  22
⇔ 22 = 49 - 1·27

(2)  27 : 22 = 1  Rest  5
⇔ 5 = 27 - 1·22 = 27 - 1·(49 - 1·27) = 2·27 - 1·49

(3)  22 : 5 = 4  Rest  2
⇔ 2 = 22 - 4·5 = (49 - 1·27) - 4·(2·27 - 1·49) = 5·49 - 9·27

(4)  5 : 2 = 2  Rest  1
⇔ 1 = 5 - 2·2 = (2·27 - 1·49) - 2·(5·49 - 9·27) = 20·27 - 11·49.


18 = 360·27 - 198·49
18 = (360 + 49·n)·27 + (-198 - 27·n)·49
18 = (17 + 49·n)·27 + (-9 - 27·n)·49.

Comments

Danke, aber es ist 45, nicht 49. Jemand hat den Titel des Threads verändert.

---

Die korrekte Aufgabenstellung lautet also \(27x+45y=18\)?
Dies ist äquivalent zu \(3x+5y=2\).
Auch ohne Algorithmus erkennt man sofort die Lösung \(x_1=-1,\,y_1=1\).