Zeige: irgendein Lösungspaar einer linearen Gleichung, haben die Form ..

Question

Aufgabe:

Seien a,b ∈ ℤ teilerfremd. Zeige: Ist x_0,y₀, ∈ ℤ irgendein Lösungspaar der linearen Gleichung xa + yb = c, so haben alle Lösungspaare die Form:

x = x₀ + bt

y = y₀  - at  mit t ∈ ℤ

Problem/Ansatz:

Als Ansatz habe ich folgendes:

Für 2 teilerfremde Zahlen p1 und p2 existieren s1 und s2 mit : p1s1 + p2s2 = 1

Aber ich weiß nicht, ob mir dieser Ansatz überhaupt etwas bringt....

Answer 1

Hallo,

Setze die Lösungspaare doch einfach in die Gleichung ein:$$\begin{aligned} xa + yb &= c \\ (x_0 + bt) a + (y_0 - at)b &= c \\ (\underbrace{x_0a + y_0b}_{=c}) + abt - abt &= c\end{aligned}$$... ist doch offensichtlich das selbe.

Jetzt steht noch aus zu zeigen, dass da kein Lösungspaar fehlt. Das geht über die Teilerfremdheit von \(a\) und \(b\).

Comments

Wie kann ich das denn mit der Teilerfremdheit zeigen? Also dann steht ja da:

c + abt - abt = c und daraus folgt ja sowieso schon c = c

---

Wie kann ich das denn mit der Teilerfremdheit zeigen? Also dann steht ja da:
c + abt - abt = c und daraus folgt ja sowieso schon c = c

Augenblick - nicht das eine mit dem anderen durcheinander bringen.

Ich habe oben lediglich gezeigt, dass der Ansatz $$\begin{aligned} x &= x_0 + bt && \mid\, t \in \mathbb Z\\ y &= y_0 - at \end{aligned}$$für jedes \(t\) korrekt ist, da nach der Voraussetzung \((x_0;y_0) \in \mathbb L\) auf beiden Seiten des Gleichheitszeichens dasselbe steht.

Du sollst aber auch zeigen, dass 'alle Lösungspaare' diese Form haben. Und dazu ist es notwendig, dass \(a\) und \(b\) teilerfremd sind.

---

Könntest du mir vielleicht noch ein tipp geben, wie genau ich das machen kann. Also was wäre dein ansatz?

---

Also was wäre dein ansatz?

z.B. ein Widerspruchsbeweis.

Angenommen es existiert eine Lösung \((x_1;y_1)\) wobei \(x_1 \ne x_0 + bt\) und \(t \in \mathbb Z\).  Daraus folgt$$ b \nmid x_1 - x_0$$Dann ziehe von dieser Lösung die bekannte Gleichung mit der bekannten Lösung \((x_0;y_0)\) ab:$$x_1 a + y_1b = c \\ x_0 a + y_0 b= c$$ziehe beide von einander ab:$$(x_1- x_0) a + (y_1 - y_0)b = 0 \\ \implies (x_1- x_0) a = (y_0 - y_1)b$$Da lt. Vorausetzung aber \(a\) und \(b\) teilerfremd sind, muss $$b \mid x_1 - x_0$$das ist aber ein Widerspruch zur Annahme oben.

---

Vielen Dank!