Diophantische Gleichung und euklidischer Algorithmus

Question

Aufgabe:

Die Diophantische Gleichung 16x+18y=30 hat:

-eine Lösung

-keine Lösung

-unendlich viele Lösungen

-höchstens 30 Lösungen

-nichts davon

Problem/Ansatz:

Der größte gemeinsame Teiler von (16,18)=2 und 2|30, heißt es gibt auf jeden Fall eine Lösung.

Jetzt wollte ich mit dem erweiterten Euklidischen Algorithmus machen, komme da aber nicht ganz weiter.

Euklidischer Algorithmus:

(18,16)=2

18=16*1+2

16=2*8+0

Für den erweiterten komme ich nicht weiter

Comments

Hab es mal versucht und habe x=3 und y=-6 raus, kann ja nicht sein?

---

War dir nicht direkt aufgefallen, dass 18 - 16 = 2 gilt? Da braucht man dann keinen erweiterten euklidischen Algorithmus nehmen. Den nimmt man ja eigentlich nur, wenn du nicht direkt eine Lösung sehen kannst.

Answer 1

\(16a+18b=2\) hat offensichtlich die Lösung \(a=-1, b=1\), damit hat

\(16x+18y=30=2\cdot 15\) die Lösung \(x=-15, y=15\).

Answer 2

Es gibt unendlich viele Lösungen.

Answer 3

x=3, y=-1 ist garantiert eine Lösung.

Answer 4

Alle Lösungen sind

x=3+9s, y=-1-8s

Mit ganzzahligem s

Answer 5

Sei gegrüßt!

Eine diophantische Gleichung ax+by = c ist genau dann in den ganzen Zahlen, wenn ggT(a,b) die c teilt. Dann hat sie sogar unendlich Lösungen in den ganzen Zahlen.

In dem Beispiel ist ggT(a,b) = ggT(16,18) = 2 und die teilt 30 = c.

Somit hat die Gleichung unendlich viele Lösungen.

Liebe Grüsse

Detli Black

Comments

Eine diophantische Gleichung ax+by = c ist genau dann in den ganzen Zahlen, wenn ggT(a,b) die c teilt.

Eine diophantische Gleichung ist IMMER in den ganzen Zahlen. Sonst dürfte sie sich nicht so nennen.

Answer 6

Die Lösungsmenge der Gleichung

16·x + 18·y = 30

ist gleich der Lösungsmenge der Gleichung

8·x + 9·y = 15

Da der ggT von 8 und 9 die 15 teilt, gibt es unendlich viele Lösungen.

Auf eine Lösung kommt man mit 15·[-1, 1] = [-15, 15] recht schnell und für weitere Lösungen könnten wir k·[9, -8] addieren.

Damit erhalten wir die Lösungen

[-15, 15] + k·[9, -8]

Comments

Bei dieser schwierigen Aufgabe ist es natürlich wichtig, daß die Lösung wiederholt wird. Gratulation zu den Punkten.

---

Selbstverständlich. Das ist bei ihm aber auch kein Einzelfall (nach eigener Aussage liest er gar keine anderen Antworten). Ein Duplikat ist es aber wiederum nicht, da er ja nicht 1:1 abgeschrieben hat...

---

Ich denke der aufmerksame Leser findet in meiner Lösung hilfreiche Informationen, die evtl. woanders fehlen.