Worksheet: Unterschied zwischen den Versionen

Version vom 18. Dezember 2012, 14:53 Uhr

Motivation

Wir haben neulich festgestellt, dass es sich mit Gleichungen folgender Form etwas seltsam verhält:

$2\cdot x + 1\cdot y = 1$ : Diese Gleichung hat unendlich viele Lösungen, nämlich z.B.: ______________________________
$6\cdot x + 9\cdot y = 18$ : Diese hat _____________________ Lösungen.
$6\cdot x + 9\cdot y = 14$ : Diese hat _____________________ Lösungen.

Wann gibt es Lösungen für solche Gleichungen? Und wie findet man die?

Erweiterter Euklidischer Algorithmus

Wir beschäftigen uns zunächst mit speziellen diophantischen Gleichungen, und zwar wollen wir wissen, ob eine Lösung für die Gleichung $a\cdot x + b\cdot y = ggT(a,b)$ existiert. Alternative Frage: Ist der $ggT(a,b)$ immer als Linearkombination von $a$ und $b$ darstellbar?

Wir schauen erst einmal an einem konkreten Beispiel, was da zu machen ist. Wir berechnen den $ggT(128,34)$ mit dem Euklidischen Algorithmus:

Der $ggT(128,34)$ ist also $2$ . Wir wollen also nun versuchen, $x$ und $y$ zu finden derart, dass $2 = 128\cdot x + 34\cdot y$ .

Das gelingt durch Rückwärtsarbeiten. Schreibe die Rechnungen, mit denen man $x$ und $y$ findet:

Das klappt auf diese Weise natürlich immer. Betrachten wir das mal allgemein, und zwar zwei aufeinanderfolgende Schritte im Euklidischen Algorithmus:

...
$a_i = q_i\cdot b_i + r_i$
$a_{i+1} = q_{i+1}\cdot b_{i+1} + r_{i+1}$
...

Das Rückwärtsarbeiten wie oben hat uns folgende Gleichung beschert:

$ggT(a,b) = x_{i+1}\cdot a_{i+1} + y_{i+1}\cdot b_{i+1}$

Außerdem wissen wir, dass $a_{i+1} = b_{i}$ ist, und dass $b_{i+1} = r_i = a_i-q_i\cdot b_i$

Einsetzen, umstellen und freuen: $ggT(a,b) = x_{i+1}\cdot b_i + y_{i+1}\cdot (a_i-q_i\cdot b_i) = y_{i+1}\cdot a_i + (x_{i+1} - q_i\cdot y_{i+1})\cdot b_i$

Also ergibt sich folgende Regel: $x_i=y_{i+1}$ und $y_i=x_{i+1} - q_i\cdot y_{i+1}$ .

Dies resultiert im erweiterten Euklidischen Algorithmus, der in Tabellenform einfach und schnell durchzuführen ist:

a	b	q	r	x	y
$128$	$34$
$34$	$26$	$1$	$8$	$-3$	$1-1\cdot(-3)=4$
$26$	$8$	$3$	$2$	$1$	$0-3\cdot 1 = -3$
$8$	$2$	$4$	$0$	$0$	$1$

Die allgemeine Umformung lässt deutlich werden: Das klappt immer. Insofern können wir aus diesem konstruktiven Beweis folgern:

Junktoren

Fülle die folgenden Tabellen aus!

Negation ( $\neg$ ; NICHT)

$A$	$\neg A$
f
w

Konjunktion ( $\wedge$ ; UND)

$A$	$B$	$A\wedge B$
f	f
f	w
w	f
w	w

Disjunktion ( $\vee$ ; ODER)

$A$	$B$	$A\vee B$
f	f
f	w
w	f
w	w

Implikation ( $\Rightarrow$ ; WENN...DANN...)

$A$	$B$	$A\Rightarrow B$

Äquivalenz ( $\Leftrightarrow$ ; GENAU DANN WENN)

$A$	$B$	$A\Leftrightarrow B$

Prioritäten

Ähnlich wie bei der Punkt-vor-Strichrechnung gibt es Prioritäten der einzelnen Junktoren. Es gilt:

$\neg$ vor $\wedge$ vor

Man kann nichts falsch machen, wenn man zusätzliche Klammern spendiert, um die Sachlage eindeutig zu machen.

Beweise mit Wahrheitstafeln

Wir haben die Vermutung, dass $A \Leftrightarrow B$ dasselbe ist wie $(A \Rightarrow B)\wedge (B\Rightarrow A)$ . Anhand einer Wahrheitstafel kann man diese Vermutung beweisen. Fülle die Tabelle vollständig aus.

$A$	$B$	$A\Rightarrow B$	$B\Rightarrow A$	$(A \Rightarrow B)\wedge (B\Rightarrow A)$	$A\Leftrightarrow B$

Woran erkennt man, dass $A \Leftrightarrow B$ und $(A \Rightarrow B)\wedge (B\Rightarrow A)$ äquivalent sind?

Fragen

Hast du noch Fragen? Notiere sie dir hier, damit du sie in deiner Lerngruppe, in der Übungsstunde oder in der nächsten Plenumssitzung klären kannst!

Satz

Der $ggT(a,b)$ kann als Linearkombination von $a$ und $b$ geschrieben werden. Die Gleichung $a\cdot x + b\cdot y = ggT(a,b)$ ist also lösbar.

Lösbarkeit linearer diophantischer Gleichungen

Satz: Lineare diophantische Gleichungen der Form $a\cdot x + b\cdot y = c$ mit $a,b,c\in \mathbb{Z}$ sind genau dann lösbar, wenn $ggT(a,b)|c$ .

Beweis:

1. Sei $(x_0, y_0)$ eine Lösung der Gleichung. Dann gilt $a\cdot x_0 + b\cdot y_0 = c$ . Sei $d=ggT(a,b)$ . Weil $d$ die linke Seite der Gleichung teilt, muss $d$ auch die rechte Seite der Gleichung teilen, also $ggT(a,b)|c$ .

2. Es gelte $ggT(a,b)|c$ , somit existiert ein $z\in\mathbb{Z}$ mit $c=z\cdot ggT(a,b)$ . Wir wissen mittlerweile, dass es ein Paar $(x_0, y_0)$ gibt mit $a\cdot x_0 + b\cdot y_0 = ggT(a,b)$ . Wir multiplizieren beide Seiten der Gleichung mit $z$ , dann ergibt sich: $a\cdot (z\cdot x_0) + b\cdot (z\cdot y_0) = z\cdot ggT(a,b)$ . Also haben wir mit $(z\cdot x_0, z\cdot y_0)$ eine Lösung gefunden.

Hieraus lässt sich direkt ableiten:

Der $ggT(a,b)$ ist die kleinste natürliche Zahl, die als Linearkombination von $a$ und $b$ darstellbar ist.
Die diophantische Gleichung $a\cdot x + b\cdot y = 1$ ist genau dann lösbar, wenn $a$ und $b$ teilerfremd sind.
Damit gilt auch: Wenn $a$ und $b$ teilerfremd sind, dann ist jede ganze Zahl als Linearkombination von $a$ und $b$ darstellbar.

Lösungen linearer diophantischer Gleichungen

Wir wissen nun, wann eine lineare diophantische Gleichung lösbar ist, und wir können auch eine Lösung einfach über den erweiterten Euklidischen Algorithmus finden. Gibt es aber weitere Lösungen? Die Antwort lautet: Ja, und zwar unendlich viele. Wenn man eine Lösung $(x_0, y_0)$ gefunden hat, dann findet man die gesamte Lösungsmenge mit: $\{(x_0+\frac{z\cdot b}{ggT(a,b)}, y_0-\frac{z\cdot a}{ggT(a,b)})|z\in\mathbb{Z}\}$ .

Beweis: Sei $z\in\mathbb{Z}$ . Dann ist $(x_0+\frac{z\cdot b}{ggT(a,b)}, y_0-\frac{z\cdot a}{ggT(a,b)})$ tatsächlich eine Lösung, denn: $a\cdot (x_0+\frac{z\cdot b}{ggT(a,b)}) + b\cdot (y_0-\frac{z\cdot a}{ggT(a,b)}) = a\cdot x_0 + \frac{z\cdot a\cdot b}{ggT(a,b)} + b\cdot y_0 - \frac{z\cdot a\cdot b}{ggT(a,b)} = a\cdot x_0 + b\cdot y_0 = c$

Es ist auch tatsächlich jede Lösung von dieser Form, wie folgende Überlegung zeigt:

Sei $(x,y)$ eine weitere Lösung. Wir wissen also: $a\cdot x + b\cdot y = c$ und $a\cdot x_0 + b\cdot y_0 = c$ . Die Subtraktion der beiden Gleichungen liefert

$a\cdot (x-x_0) + b\cdot (y-y_0) = 0$

also

$a\cdot (x-x_0) = b\cdot (y_0-y)$

Wir können außerdem beide Seiten durch $ggT(a,b)$ teilen:

$\frac{a}{ggT(a,b)}\cdot (x-x_0) = \frac{b}{ggT(a,b)}\cdot (y_0-y)$

Wir wissen, dass $\frac{a}{ggT(a,b)}$ und $\frac{b}{ggT(a,b)}$ teilerfremd sind, also muss gelten $\frac{b}{ggT(a,b)}|(x-x_0)$ , somit existiert ein $z\in\mathbb{Z}$ mit $(x-x_0)=z\cdot \frac{b}{ggT(a,b)}$ .In die Gleichung eingesetzt ergibt sich:

$\frac{a}{ggT(a,b)}\cdot z\cdot \frac{b}{ggT(a,b)} = \frac{b}{ggT(a,b)}\cdot (y_0-y)$

Somit ist $(y_0-y)=z\cdot \frac{a}{ggT(a,b)}$

Wenn man jeweils nach $x$ und $y$ umformt, ergibt sich gerade die oben genannte Form.

Beispiel

Wir wollen wissen, ob die Gleichung $168x+238y=126$ lösbar ist, und wenn ja, für welche $(x,y)$ .

Wir müssen zunächst einmal den $ggT(168,238)$ bestimmen und testen, ob dieser die Zahl $126$ teilt (ansonsten könnten wir sofort aufhören).

Der erweiterte Euklidische Algorithmus ergibt:

a	b	q	r	x	y
$238$	$168$	$1$	$70$	$5$	$-7$
$168$	$70$	$2$	$28$	$-2$	$5$
$70$	$28$	$2$	$14$	$1$	$-2$
$28$	$14$	$2$	$0$	$0$	$1$

Somit ist $ggT(168,238)=14=168\cdot(-7)+238\cdot 5$ .

Außerdem gilt: $14|126$ , nämlich $126=14\cdot 9$ .

Wir müssen also die Gleichung mit $9$ multiplizieren und erhalten:

$126=168\cdot(-63)+238\cdot 45$ .

Allgemein sind die Lösungen: $x=-63+\frac{z\cdot 238}{14}=-63+17z$ und $y=45-\frac{z\cdot 168}{14}=45-12z$

@@ Zeile 62: / Zeile 62: @@
 Die allgemeine Umformung lässt deutlich werden: Das klappt immer. Insofern können wir aus diesem konstruktiven Beweis folgern:
-== Aussage ==
-Vervollständige den folgenden Satz:
-{{PHHDLückeMitText|Eine Aussage ist <br><br>
-}}
 == Junktoren ==

Worksheet: Unterschied zwischen den Versionen

Version vom 18. Dezember 2012, 14:53 Uhr

Motivation

Erweiterter Euklidischer Algorithmus

Junktoren

Negation ( $\neg$ ; NICHT)

Konjunktion ( $\wedge$ ; UND)

Disjunktion ( $\vee$ ; ODER)

Implikation ( $\Rightarrow$ ; WENN...DANN...)

Äquivalenz ( $\Leftrightarrow$ ; GENAU DANN WENN)

Prioritäten

Beweise mit Wahrheitstafeln

Fragen

Satz

Lösbarkeit linearer diophantischer Gleichungen

Lösungen linearer diophantischer Gleichungen

Beispiel

Navigationsmenü

Meine Werkzeuge

Namensräume

Varianten

Ansichten

Aktionen

Suche

Navigation

ZUM.de

Hilfen

Werkzeuge

Worksheet: Unterschied zwischen den Versionen

Version vom 18. Dezember 2012, 14:53 Uhr

Motivation

Erweiterter Euklidischer Algorithmus

Junktoren

Negation (; NICHT)

Konjunktion (; UND)

Disjunktion (; ODER)

Implikation (; WENN...DANN...)

Äquivalenz (; GENAU DANN WENN)

Prioritäten

Beweise mit Wahrheitstafeln

Fragen

Satz

Lösbarkeit linearer diophantischer Gleichungen

Lösungen linearer diophantischer Gleichungen

Beispiel

Navigationsmenü

Suche

Negation ( $\neg$ ; NICHT)

Konjunktion ( $\wedge$ ; UND)

Disjunktion ( $\vee$ ; ODER)

Implikation ( $\Rightarrow$ ; WENN...DANN...)

Äquivalenz ( $\Leftrightarrow$ ; GENAU DANN WENN)