Worksheet: Unterschied zwischen den Versionen

Aktuelle Version vom 11. Dezember 2016, 18:18 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:

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$

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!

Worksheet: Unterschied zwischen den Versionen

Aktuelle Version vom 11. Dezember 2016, 18:18 Uhr

Motivation

Erweiterter Euklidischer Algorithmus

Satz

Lösbarkeit linearer diophantischer Gleichungen

Lösungen linearer diophantischer Gleichungen

Beispiel

Fragen

Navigationsmenü

Meine Werkzeuge

Namensräume

Varianten

Ansichten

Aktionen

Suche

Navigation

ZUM.de

Hilfen

Werkzeuge

@@ Zeile 1: / Zeile 1: @@
 __NOTOC__
-[http://wiki.zum.de/index.php?title=PH_Heidelberg/Bausteine/Diophantische_Gleichungen/Worksheet&printable=yes Druckversion]
+[https://wiki.zum.de/index.php?title=PH_Heidelberg/Bausteine/Diophantische_Gleichungen/Worksheet&printable=yes Druckversion]
@@ Zeile 18: / Zeile 18: @@
 Wir beschäftigen uns zunächst mit speziellen diophantischen Gleichungen, und zwar wollen wir wissen, ob eine Lösung für die Gleichung <math>a\cdot x + b\cdot y = ggT(a,b)</math> existiert. Alternative Frage: Ist der <math>ggT(a,b)</math> immer als Linearkombination von <math>a</math> und <math>b</math> darstellbar?
-Wir schauen erst einmal an einem konkreten Beispiel, was da zu machen ist. Wir berechnen den <math>ggT(128,34)</math> mit dem Euklidischen Algorithmus:
-* <math> 128 = 3\cdot 34 + 26</math>
-* <math> 34 = 1\cdot 26 + 8</math>
-* <math> 26 = 3\cdot 8 + 2</math>
-* <math> 8 = 4\cdot 2 + 0</math>
-Der <math>ggT(128,34)</math> ist als <math>2</math>. Wir wollen also nun versuchen, <math>x</math> und <math>y</math> zu finden derart, dass <math>2 = 128\cdot x + 34\cdot y</math>.
+[[Kategorie:Arbeitsblatt Mathematik PH Heidelberg|Diophantische Gleichungen]]
-Das gelingt durch Rückwärtsarbeiten. Aus der vorletzten Zeile wissen wir:
+Wir schauen erst einmal an einem konkreten Beispiel, was da zu machen ist. Wir berechnen den <math>ggT(128,34)</math> mit dem Euklidischen Algorithmus:
-<math>2 = 26 - 3\cdot 8</math>
+{{PHHDLückeGroß}}
-WIe kam die 8 zustande? Aus der Zeile drüber mit <math>8 = 34 - 1\cdot 26</math>. Eingesetzt und zusammengefasst:
-<math>2 = 26 - 3\cdot(34-1\cdot 26) = 26 - 3\cdot 34 + 3\cdot 26 = -3\cdot 34 + 4\cdot 26</math>
-Wie kam die 26 zustande? Naja, wiederum aus der Zeile vorher mit <math>26 = 128 - 3\cdot 34</math>. Eingesetzt und zusammengefasst:
-<math>2 = -3\cdot 34 + 4\cdot (128 - 3\cdot 34) = 4\cdot 128 -15\cdot 34</math>
+Der <math>ggT(128,34)</math> ist also <math>2</math>. Wir wollen also nun versuchen, <math>x</math> und <math>y</math> zu finden derart, dass <math>2 = 128\cdot x + 34\cdot y</math>.
-Voilá!
+Das gelingt durch Rückwärtsarbeiten. Schreibe die Rechnungen, mit denen man <math>x</math> und <math>y</math> findet:
-{{#ev:youtube|bNa_fLCs5GA}}
+{{PHHDLückeMitText|<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>}}
 Das klappt auf diese Weise natürlich immer. Betrachten wir das mal allgemein, und zwar zwei aufeinanderfolgende Schritte im Euklidischen Algorithmus:
@@ Zeile 59: / Zeile 48: @@
 Also ergibt sich folgende Regel: <math>x_i=y_{i+1}</math> und <math>y_i=x_{i+1} - q_i\cdot y_{i+1}</math>.
-{{#ev:youtube|nD6psV2vkRU}}
 Dies resultiert im erweiterten Euklidischen Algorithmus, der in Tabellenform einfach und schnell durchzuführen ist:
@@ Zeile 69: / Zeile 56: @@
 | '''a''' || '''b''' || '''q''' || '''r'''|| '''x'''|| '''y'''
 |-
-| <math>128</math> || <math>34</math> || <math>3</math> || <math>26</math> || <math>4</math> || <math>-3-3\cdot4=-15</math>
+| <math>128</math> || <math>34</math> || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  ||  ||  ||
 |-
 | <math>34</math> || <math>26</math> || <math>1</math> || <math>8</math> || <math>-3</math> || <math>1-1\cdot(-3)=4</math>
@@ Zeile 77: / Zeile 64: @@
 | <math>8</math> || <math>2</math> || <math>4</math> || <math>0</math> || <math>0</math> || <math>1</math>
 |}
-(Die unterste Zeile ergibt sich einfach aus <math>b = 0\cdot a + 1\cdot b</math>).
 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 ==
-Fülle die folgenden Tabellen aus!
-{|
-|width="30%" valign="top" |
-==== Negation (<math>\neg</math>; NICHT) ====
-{| border="1"
-|<math>A</math>
-|<math>\neg A</math>
-|-
-|f
-|
-|-
-|w
-|
-|}
-|width="5%"|<!--Diese Spalte bleibt leer und legt den Abstand zwischen Text und Bild fest-->
-|width="30%" valign="top" |
-==== Konjunktion (<math>\wedge</math>; UND) ====
-{| border="1"
-|<math>A</math>
-|<math>B</math>
-|<math>A\wedge B</math>
-|-
-|f
-|f
-|
-|-
-|f
-|w
-|
-|-
-|w
-|f
-|
-|-
-|w
-|w
-|
-|}
-|width="5%"|<!--Diese Spalte bleibt leer und legt den Abstand zwischen Text und Bild fest-->
-|width="30%" valign="top" |
-==== Disjunktion (<math>\vee</math>; ODER) ====
-{| border="1"
-|<math>A</math>
-|<math>B</math>
-|<math>A\vee B</math>
-|-
-|f
-|f
-|
-|-
-|f
-|w
-|
-|-
-|w
-|f
-|
-|-
-|w
-|w
-|
-|}
-|}
-{|
-|width="45%" valign="top" |
-==== Implikation (<math>\Rightarrow</math>; WENN...DANN...) ====
-{| border="1"
-|<math>A</math>
-|<math>B</math>
-|<math>A\Rightarrow B</math>
-|-
-|&nbsp;
-|
-|
-|-
-|&nbsp;
-|
-|
-|-
-|&nbsp;
-|
-|
-|-
-|&nbsp;
-|
-|
-|}
-|width="10%"|<!--Diese Spalte bleibt leer und legt den Abstand zwischen Text und Bild fest-->
-|width="45%" valign="top" |
-==== Äquivalenz (<math>\Leftrightarrow</math>; GENAU DANN WENN) ====
-{| border="1"
-|<math>A</math>
-|<math>B</math>
-|<math>A\Leftrightarrow B</math>
-|-
-|&nbsp;
-|
-|
-|-
-|&nbsp;
-|
-|
-|-
-|&nbsp;
-|
-|
-|-
-|&nbsp;
-|
-|
-|}
-|}
-== Prioritäten ==
-Ähnlich wie bei der Punkt-vor-Strichrechnung gibt es Prioritäten der einzelnen Junktoren. Es gilt:
-{{PHHDLückeMitText|<math>\neg</math> vor <math>\wedge</math> vor <br><br>
-}}
-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 <math>A \Leftrightarrow B</math> dasselbe ist wie <math>(A \Rightarrow B)\wedge (B\Rightarrow A)</math>. Anhand einer Wahrheitstafel kann man diese Vermutung beweisen. Fülle die Tabelle vollständig aus.
-{| border="1"
-|<math>A</math>
-|<math>B</math>
-|<math>A\Rightarrow B</math>
-|<math>B\Rightarrow A</math>
-|<math>(A \Rightarrow B)\wedge (B\Rightarrow A)</math>
-|<math>A\Leftrightarrow B</math>
-|-
-|&nbsp;
-|
-|
-|
-|
-|
-|-
-|&nbsp;
-|
-|
-|
-|
-|
-|-
-|&nbsp;
-|
-|
-|
-|
-|
-|-
-|&nbsp;
-|
-|
-|
-|
-|
-|}
-Woran erkennt man, dass <math>A \Leftrightarrow B</math> und <math>(A \Rightarrow B)\wedge (B\Rightarrow A)</math> äquivalent sind?
-{{PHHDLückeKlein}}
-== 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!
-{{PHHDLückeGroß}}
 === Satz ===
@@ Zeile 300: / Zeile 74: @@
 === Lösbarkeit linearer diophantischer Gleichungen ===
-{{#ev:youtube|ftm-9hgXn4M}}
 Satz: Lineare diophantische Gleichungen der Form <math>a\cdot x + b\cdot y = c</math> mit <math>a,b,c\in \mathbb{Z}</math> sind genau dann lösbar, wenn <math>ggT(a,b)|c</math>.
@@ Zeile 319: / Zeile 92: @@
 === Lösungen linearer diophantischer Gleichungen ===
-{{#ev:youtube|POnADqzkGxk}}
 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 <math>(x_0, y_0)</math> gefunden hat, dann findet man die gesamte Lösungsmenge mit: <math>\{(x_0+\frac{z\cdot b}{ggT(a,b)}, y_0-\frac{z\cdot a}{ggT(a,b)})|z\in\mathbb{Z}\}</math>.
@@ Zeile 349: / Zeile 121: @@
 === Beispiel ===
-{{#ev:youtube|uIA6ypsIuHw}}
 Wir wollen wissen, ob die Gleichung <math>168x+238y=126</math> lösbar ist, und wenn ja, für welche <math>(x,y)</math>.
@@ Zeile 378: / Zeile 150: @@
 <math>126=168\cdot(-63)+238\cdot 45</math>.
-Allgemein sind die Lösungen: <math>x=-63+\frac{z\cdot 238}{14}=-63+17z</math> und <math>y=45-\frac{z\cdot 168}{14}=45-12z</math>
+Allgemein sind die Lösungen: <math>x=-63+\frac{z\cdot 238}{14}=-63+17z</math> und <math>y=45-\frac{z\cdot 168}{14}=45-12z</math><br />
+== 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!
+{{PHHDLückeGroß}}