Löse eine Diophantische Gleichung mithilfe des Euklidischen Algo

Question

Aufgabe:

Löse eine Diophantische Gleichung mithilfe des Euklidischen Algo

Problem/Ansatz:

Hi, ich habe ein generelles Problem den Lösungsweg von einer Diophantischen Gleichung (ax+by=c mit ganzzahligen Lösungen) nachzuvollziehen. In den Vorlesungen hat man uns einen Lösungsweg über die Anwendung des Euklidischen Algorythmuses, jedoch bleibe ich immer an der Stelle hängen wo ich den Algo dann durchgezugen habe aber dann nicht weiter weiß wie ich weiter vorzugehen habe um auf die Lösung zu kommen.

Es sollte ja irgendwas in der Form von ner konstante + ein skalierbarer Wert herauskommen, aber ich weiß nicht wie ich auf den komme. Würde mich freuen wenn mir das jemand erklären könnte, denn meine Tutoren haben mich nur auf die Vorlesungsfolien verwiesen auf denen kein Verständnistext steht.

Danke schonmal im Voraus.

Comments

Der relevante Lösungsweg fehlt.

---

Eine sehr hilfreiche  Seite findest  du hier:

https://www.arndt-bruenner.de

Oder auch, wenn du deinen Kopf in die Richtung bewegst:  ↓

Answer 1

Ich nehme mal die Gleichung

5·a + 3·b = 1

Wir stellen damit den erweiterten euklidischen Algorithmus auf

Der ggT ist also 1 und den können wir darstellen als

5·(-1) + 3·(2) = 1

Da dies nur die Gründlösung ist kannst du auch die allgemeinen Lösungen in Abhängigkeit einer ganzen Zahl k darstellen.

5·(-1 + 3·k) + 3·(2 - 5·k) = 1

(x, y) = (-1 + 3·k, 2 - 5·k)

Die Tabelle habe ich nach dem Schema von Wikipedia erstellt, nur das ich die unbekannten hier x und y genannt habe statt s und t.

Solltest du noch Schwierigkeiten haben, dass mit deinen Werten nachzuvollziehen kann ich dabei auch helfen. Dann solltest du nur das a, b und c mitteilen, bzw. die Gleichung die gelöst werden soll.

Comments

Oiiiiiiiii,

Danke für die Antwort. Ja das bringt mich meilenweit weiter.

Die Gleichung an der ich gerade arbeite ist 45x+24y=6, welche ich zu 15x+8y=2 runtergekürzt habe. Ich habe den erweiterten euklidischen Algo angewendet und als GGT 1 heraus gekriegt. x und y sind ja dann auch -1 und 2. wodurch ich ja dann

15*(-1)+8*2=1 herauskriegen würde. was ich ja dann doch eigentlich irgenwie auf =2 hochskalieren müsste. Aber wie mache ich das? Einfach *2?

---

Ja, einfach "*2", in der Tat:

45(-2)+24*4=6

Bleibt noch die Frage, ob Du eine oder alle Lösungen finden sollst / willst.