Bestimmen Sie (falls möglich) die ganzzahlige Lösung der Gleichungen

Question

Aufgabe:
Bestimmen Sie (falls möglich) die ganzzahlige Lösung der Gleichungen
215x + 3242y = −1562
mit der kleinsten positiven Zahl x.

Problem/Ansatz:
1. Ich rechne ggT(3242, 215) = 1 aus
2. Mit dem erweiterten Eukl. Algo. bekomme ich: 1 = 38 * 3242 - 573 * 215
3. Das muss ich vom ggT=1 auf die -1562 bringen * (c / ggT(a,b)): x0 = 895026; y0 = -59356
4. Für alle Lösungen bekomme ich folgenden Satz: {(895026+t*3242, -59356-t*215) | teZ} weil bspw. x = x0 + t * (b / ggT(a,b)), für y = y0  + t * (a / ggT(a,b))
5. Für t rechne ich:
(y =) -59356 - t*215 >= 0   | t <= 276
(x =) 895026 + t*3242 >= 0  | t >= 276
6. Ich setze 276 in Pkt. 5 jeweils ein, damit ich x und y erhalte, bekomme aber y=-118696 und x=1789818, raus

In der Lösung steht allerdings x = 234, y = −16
Wie komme ich bitte auf folgendes x und y? Ich habe sehr große Zahlen rausbekommen :/

Comments

In Punkt 6 versuche mal t = -276.

---

Danke für den Tipp. Ich wusste das, aber wie komme ich auf die minus 276. etwas weiter unten vom Beitrag kommentierte ich gleichfalls zur selben Thematik.

Answer 1

Ich komme mit dem Algorithmus nach Arndt Brünner auf

\(\small IX \, :=  \, \left(\begin{array}{r}3242 \; t_5 + 234\\-215 \; t_5 - 16\\\end{array}\right)\)

Dem nach ist Deine Lösung dabei, insbesondere die für t₅=0

ohne die 6 Schritte hier aufzulisten siehe Details zum Lösungsweg

http://www.arndt-bruenner.de/mathe/scripts/diophant.htm#script

Comments

Hallo Wächter,
! Gelöst, ich hatte tatsächlich beim Umformen die Vorzeichen nicht genau berücksichtigt..., danke aber für die Unterstützung mit der Website, die hilft sehr sehr weiter!!
LG Leeroy

Answer 2

215x + 3242y = −1562

Wir nehmen die Gleichung modulo 215:

0x + 17 y ≡ 158 mod 215

und ersetzen 158 durch (158-215=) -57.

17 y ≡ -57 mod 215

Wegen 215=43*5 lässt sich das aufspalten in

17 y ≡ 3 mod 5  und

17 y ≡ -13 mod 43

Wegen 17≡ -26 mod 43 lässt sich letzteres Umformen zu

-26 y ≡ -13 mod 43 und vereinfachen zu

2y ≡ 1 mod 43.

Eine Lösung davon ist y=22, die nächste 65, die übernächste 108, dann 151 und 194.

Eine dieser 5 Lösungen muss auch 17 y ≡ 3 mod 5  erfüllen, was für y=194 gilt.

Die Lösungen für y sind 194 + k*215 (Für k=-1 ergibt sich dein y=-16 der Musterlösung).

Löse nun die Gleichung 215x + 3242y = −1562 in Form von

215x + 3242*(194 + k*215) = −1562 nach x auf.

Dein

y=-118696 und x=1789818,

habe ich nicht getestet. Falls diese Zahlen richtig sind, ist auch

y=-118696+215k und x=1789818 -3242k eine Lösung.

Comments

Danke für deine Antwort! Ab (158-215=-57) verstehe ich leider nicht mehr viel, bis auf ich glaube die Primfaktorzerlegung, um aufzuspalten, tut Leid, weiß da dann nicht weiter.

Aber zurück zu meinem Rechenweg, ich denke, dass ich da mit dem Vorzeichen/einer Rechenregel durcheinanderkomme, weil folgendes
(y =) -59356 - t*215 >= 0  | (NICHT: t <= 276) Sondern t=-276

(x =) 895026 + t*3242 >= 0  | (NICHT: t >= 276)  Sondern t=-276

auch x = 234, y = −16 rauskommt ^^

Ich wüsste nicht wie ich da mit dem <=/>= nun richtig rechne, ich denke aufgrund von -1562, kommt hier das Finale ordentlich durcheinander...

---

Hallo Abakus,
! Gelöst, ich hatte tatsächlich beim Umformen die Vorzeichen nicht genau berücksichtigt..., danke für den Beitrag.
LG Leeroy

Answer 3

Hallo Leeroy,

Du hast ja bereits eine Lösung gefunden! Addiere diese mit 0 ;-) in der Form$$215 a + 3242 b = 0$$Für \(a\) und \(b\) lässt sich leicht ein Paar finden:$$215 \cdot(-3242) + 3242 \cdot 215 = 0$$Das braucht man nicht auszurechnen, das sieht man so, das da 0 raus kommt. Und mit einer ganzen Zahl \(k \in \mathbb{Z}\) kan man es auch multiplizieren:$$215 \cdot(-3242k) + 3242 \cdot 215k = 0$$Jetzt addiere dies zu Deiner Lösung$$\begin{aligned} 215 \cdot 1789818 + 3242 \cdot (-118696)&= −1562 \\215 \cdot(-3242k) + 3242 \cdot 215k &= 0\end{aligned}$$Dann kommt raus$$215(1789818 -3242k) + 3242 (-118696 + 215k) = −1562$$ Das 'richtige' \(k\) zu finden, sollte jetzt für Dich kein Problem sein (zur Kontrolle \(k=552\)). Sonst frage einfach nach.

Gruß Werner

Comments

Hallo Werner,
! Gelöst, ich hatte tatsächlich beim Umformen die Vorzeichen nicht genau berücksichtigt..., und das genau bei beiden Variablen x und y, sodass bei beiden t=-276 rauskommt, und somit x=234 und y=-16 als Lösung dastehet. Tut Leid wegen meiner Blindheit, ich bedanke mich für die tatkräftige Unterstützung!
LG Leeroy