Zeigen, dass Gleichung lösbar ist

13.12.2013, 17:35

Gnus

Zeigen, dass Gleichung lösbar ist

Guten Abend! Wink

Ich habe ein Problem mit folgender Aufgabe.

Die Aufgabe:
Seien $\begin{eqnarray*} a,b \in \mathbb N \end{eqnarray*}$ mit $\begin{eqnarray*} ggT(a,b)=1 \end{eqnarray*}$ .
a) Zeigen Sie, dass es für die Gleichung $\begin{eqnarray*} ax+by=1 \end{eqnarray*}$ genau eine Lösung $\begin{eqnarray*} (x,y) \in \mathbb Z^2 \end{eqnarray*}$ gibt für die $\begin{eqnarray*} 0\leq x<b \end{eqnarray*}$ und $\begin{eqnarray*} -a>y\geq 0 \end{eqnarray*}$ gilt.
b) Zeigen Sie, dass die Gleichung $\begin{eqnarray*} a^2 x+by=1+a+3b \end{eqnarray*}$ mit $\begin{eqnarray*} (x,y) \in \mathbb Z^2 \end{eqnarray*}$ lösbar ist.

Meine Ansätze:
a)
Da ggT(a,b)=1 und a und b nicht Null sind, ex. nach dem Satz von Bezout $\begin{eqnarray*} x,y \in \mathbb Z \end{eqnarray*}$ mit $\begin{eqnarray*} xa+yb=1 \end{eqnarray*}$ .
Mir ist auch klar, dass es dann eine Lösung gibt, für die $\begin{eqnarray*} 0\leq x<b \end{eqnarray*}$ gilt, da wenn dies nicht gilt finden wir mit $\begin{eqnarray*} (x-k,y+k) \end{eqnarray*}$ , $\begin{eqnarray*} k\in \mathbb Z \end{eqnarray*}$ eine Lösung für die $\begin{eqnarray*} 0\leq x<b \end{eqnarray*}$ gilt.
Allerdings komme ich nicht darauf, wie ich auf die zweite Bedingung schließen kann.

b)
$\begin{eqnarray*} a^2 x+by=1+a+3b \end{eqnarray*}$
$\begin{eqnarray*} \Leftrightarrow a(ax-1)+b(y-3)=1 \end{eqnarray*}$
Analog zu a) folgt mit Bezout, dass es $\begin{eqnarray*} x,y \in \mathbb Z \end{eqnarray*}$ mit $\begin{eqnarray*} ax+by=1 \end{eqnarray*}$ gibt.
Setzen wir nun $\begin{eqnarray*} \tilde{x}=\frac{x+1}{a}, \tilde{y}=y+3 \end{eqnarray*}$ , haben wir mit $\begin{eqnarray*} (\tilde{x},\tilde{y}) \end{eqnarray*}$ eine Lösung gefunden.
Nun weiß ich allerdings nicht, wie ich daraus auf eine ganzzahlige Lösung schließen kann. $\begin{eqnarray*} \tilde{x} \end{eqnarray*}$ ist ja nicht notwendigerweise aus $\begin{eqnarray*} \mathbb Z \end{eqnarray*}$ .

Hilfe wäre toll. Freude

MfG

13.12.2013, 19:29

URL

Auf diesen Beitrag antworten »

RE: Zeigen, dass Gleichung lösbar ist
Dass du für $\begin{eqnarray*} a \in \mathbb N \end{eqnarray*}$ kein y mit $\begin{eqnarray*} -a>y\geq 0 \end{eqnarray*}$ findest, wundert mich nicht.

13.12.2013, 22:02

Gnus

Auf diesen Beitrag antworten »

RE: Zeigen, dass Gleichung lösbar ist
Es muss natürlich -a kleiner y kleiner gleich 0 heissen, Verzeihung. Hammer

13.12.2013, 22:33

URL

Auf diesen Beitrag antworten »

RE: Zeigen, dass Gleichung lösbar ist
Für b=1 folgt aber doch x=0 und damit 1=y verwirrt

Edit: Fehlen in den Paaren $\begin{eqnarray*} (x-k,y+k) \end{eqnarray*}$ , $\begin{eqnarray*} k\in \mathbb Z \end{eqnarray*}$ nicht a und b damit es Lösungen von Bezout sind?
y>-a kann man einfach aus 1=ax+by direkt durch Auflösen nach y (und Verwendung der Eigenschaften von x ) zeigen

14.12.2013, 01:05

RavenOnJ

Auf diesen Beitrag antworten »

zu b)
Bei $\begin{eqnarray*} \operatorname{ggT}(a,b)=1 \end{eqnarray*}$ sind mit einer Lösung $\begin{eqnarray*} (\tilde x,\tilde y) \end{eqnarray*}$ von $\begin{eqnarray*} a\tilde x+b\tilde y=1 \end{eqnarray*}$ auch $\begin{eqnarray*} (\tilde x+bk,\tilde y-ak),\forall k\in\mathbb Z \end{eqnarray*}$ Lösungen.

Die Frage, ob $\begin{eqnarray*} a(ax-1)+b(y-3)=1 \end{eqnarray*}$ Lösungen $\begin{eqnarray*} (x,y) \end{eqnarray*}$ hat, ist äquivalent zur Frage, ob es ein $\begin{eqnarray*} k \end{eqnarray*}$ gibt mit $\begin{eqnarray*} (\tilde x+bk,\tilde y-ak) = (ax-1,y-3) \end{eqnarray*}$ bzw. ob $\begin{eqnarray*} \exists k,x\in \mathbb Z:\tilde x+bk = ax-1\; . \end{eqnarray*}$ Die Lösung $\begin{eqnarray*} y = \tilde y-ak +3 \end{eqnarray*}$ folgt dann automatisch. Dass immer so ein $\begin{eqnarray*} k \end{eqnarray*}$ existiert, folgt ebenfalls aus dem Lemma von Bezout (das wäre dann noch zu zeigen!). Damit hätte $\begin{eqnarray*} a(ax-1)+b(y-3)=1 \end{eqnarray*}$ immer eine Lösung.

14.12.2013, 16:12

Gnus

Auf diesen Beitrag antworten »

RE: Zeigen, dass Gleichung lösbar ist
Hallo und danke für Eure Antworten!

Zitat:

Fehlen in den Paaren $\begin{eqnarray*} (x-k,y+k) \end{eqnarray*}$ , $\begin{eqnarray*} k\in \mathbb Z \end{eqnarray*}$ nicht a und b damit es Lösungen von Bezout sind?

Ja, ich habe es jetzt zu $\begin{eqnarray*} (x_k,y_k)=(x_0 -kb, y_0+ka) \end{eqnarray*}$ korrigiert. Danke!
Ich bekomme diesen Aufgabenteil nun gelöst, indem ich zeige, dass alle Lösungen von der oben genannten Form sind, wobei $\begin{eqnarray*} (x_0,y_0) \end{eqnarray*}$ die aus Bezout folgende Lsg. ist und dann zeige, dass es nur ein $\begin{eqnarray*} k \in \mathbb Z \end{eqnarray*}$ gibt, für dass $\begin{eqnarray*} 0 \leq x_k <b \end{eqnarray*}$ gilt. Für eben diese Lösung folgt dann aber $\begin{eqnarray*} -a<y \leq 0 \end{eqnarray*}$ ist.
(Dies folgt, wie du erwähnt hast, nicht für $\begin{eqnarray*} x=0 \end{eqnarray*}$ . Ich gehe aber davon aus, dass dies ein Fehler / eine Ungenauigkeit in der Aufgabenstellung ist, da die Schlüsse bis hierhin ja richtig sein müssten.)

Zitat:

Dass immer so ein $\begin{eqnarray*} k \end{eqnarray*}$ existiert, folgt ebenfalls aus dem Lemma von Bezout

Ich kann alles was du sagt soweit nachvollziehen.
Aus Bezout erhalten wir unsere partikuläre Lsg. $\begin{eqnarray*} (x_0,y_0) \end{eqnarray*}$ und dann lassen sich alle Lsg schreiben als $\begin{eqnarray*} (x_k,y_k)=(x_0-kb,y_0+ka) \end{eqnarray*}$ (ich verwende -kb und +ka, um bei unserem Skript zu bleiben).
Nun fällt es mir allerdings schwer zu zeigen, dass ein k ex. mit
$\begin{eqnarray*} x_k=x_0-kb=ax-1 \end{eqnarray*}$ . Ich sehe nicht, wie dies aus dem Lemma von Bezout folgen soll. Ich habe versucht die Gleichung umzustellen:
$\begin{eqnarray*} 1=ax-x_0+kb \end{eqnarray*}$
Und für 1 die Darstellung $\begin{eqnarray*} 1=x_0a+y_0b \end{eqnarray*}$ einzusetzen:
$\begin{eqnarray*} x_0a+y_0b=ax-x_0+kb \end{eqnarray*}$
Egal wie ich jetzt umforme sehe ich nicht, wie mich das weiter bringt...

14.12.2013, 18:34

URL

Auf diesen Beitrag antworten »

RE: Zeigen, dass Gleichung lösbar ist
Zu zeigen ist, dass es ganzzahliges k und x gibt, so dass $\begin{eqnarray*} x_k=x_0-kb=ax-1 \end{eqnarray*}$ oder also $\begin{eqnarray*} ax+kb=1+x_0 \end{eqnarray*}$ .
Das ergibt sich aber sofort, wenn du $\begin{eqnarray*} ax_0+by_0=1 \end{eqnarray*}$ mit $\begin{eqnarray*} 1+x_0 \end{eqnarray*}$ multiplizierst.

14.12.2013, 19:26

Gnus

Auf diesen Beitrag antworten »

RE: Zeigen, dass Gleichung lösbar ist
Okay, also multipliziere ich mit $\begin{eqnarray*} x_0+1 \end{eqnarray*}$ und erhalte:
$\begin{eqnarray*} x_0+1=a(x_0(x_0+1))+b(y_0(x_0+1)) \end{eqnarray*}$ .
Setzen wir $\begin{eqnarray*} x:=x_0(x_0+1) \end{eqnarray*}$ und $\begin{eqnarray*} y:=y_0(x_0+1) \end{eqnarray*}$ haben wir also gezeigt, dass k und x ex. mit $\begin{eqnarray*} x_k=x_0-kb=ax-1 \end{eqnarray*}$ .

Wir erhalten über das gefundene k ein zu $\begin{eqnarray*} x_k \end{eqnarray*}$ gehörendes $\begin{eqnarray*} y_k \end{eqnarray*}$ . Weil $\begin{eqnarray*} (x_k,y_k) \end{eqnarray*}$ die Gleichung $\begin{eqnarray*} ax_k+by_k=1 \end{eqnarray*}$ löst und
$\begin{eqnarray*} ax_k+by_k=a(ax-1)+by_k=1 \end{eqnarray*}$ gilt, können wir $\begin{eqnarray*} y=y_k+3 \end{eqnarray*}$ setzen und erhalten ein ganzzahliges y, sodass gilt:
$\begin{eqnarray*} ax_k+by_k=a(ax-1)+b(y-3)=1 \end{eqnarray*}$ .

Fertig.

Habe ich das soweit korrekt verstanden?

Ich danke Dir schoneimal ganz herzlich für deine Hilfe, URL. Auch an RavenOnJ ein Dankeschön! Wink

14.12.2013, 19:51

URL

Auf diesen Beitrag antworten »

RE: Zeigen, dass Gleichung lösbar ist
sieht für mich gut aus Freude

Neue Frage »

Antworten »

Zeigen, dass Gleichung lösbar ist

Verwandte Themen