Wie berechnet man die Diophantischen Gleichungen?

Question

Aufgabe:

Lösen Sie die folgenden diophantischen Gleichungen und geben Sie jeweils zwei spezielle Lösungen an.
a) 33x + 22y = 100

b) 13x + 2y = 7

c) 8x − 5y = −1

Problem/Ansatz:

Wie berechnet man denn die Diophantischen Gleichungen ?

Ich habe recherchiert und rausgefunden das man Euklidische Verfahren anwenden muss aber die frage ist halt, wie man auf die "Zwei spezielle Lösungen" kommt ?

Answer 1

a) hier gibt es keine Lösung weißt du warum ?

b)

13·x + 2·y = 7

Euklid

13 = 6·2 + 1
2 = 2·1 + 0

Der GGT von 13 und 2 ist 1 und damit ist es lösbar

Erweiterter Euklid

1 = 13 - 6·2

jetzt noch mit 7 multiplizieren

7 = 7·13 - 42·2
7 = 9·13 - 55·2
7 = 11·13 - 68·2

Fällt dir an den Lösungen etwas auf?

Comments

Danke :)

Wie muss man es am ende mit 7 multiplizieren ?

---

8·x - 5·y = -1

Euklid
8 = 1·5 + 3
5 = 1·3 + 2
3 = 1·2 + 1
2 = 2·1 + 0

Erweiterter Euklid
1 = 3 - 1·2
1 = 3 - 1·(5 - 1·3) = -1·5 + 2·3
1 = -1·5 + 2·(8 - 1·5) = 2·8 - 3·5

Lösungen
1 = 2·8 - 3·5
-1 = -2·8 - (-3)·5
-1 = 3·8 - 5·5

---

Danke :) Wie muss man es am ende mit 7 multiplizieren ?

Der Erweiterte Euklid liefert dir ja nur eine Lösung für den ggt. Daher musst du eventuell die Gleichung noch multiplizieren damit du auf eine andere Lösung kommst. Ich habe also alles mal 7 genommen.

---

Achsooo ok ich habe es verstanden danke! :) :)

Und bei der a) gibt es keine Lösung, da die 22 die 100 nicht teilen kann. Oder? Also ich habe es so verstanden wenn es stimmt..

---

Der ggt von 33 und 22 ist 11.

100 ist kein vielfaches von 11 und ist daher nicht als Lösung möglich.