Worksheet: Unterschied zwischen den Versionen

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche
Zeile 1: Zeile 1:
 
__NOTOC__
 
__NOTOC__
 
[http://wiki.zum.de/index.php?title=PH_Heidelberg/Bausteine/Diophantische_Gleichungen/Worksheet&printable=yes Druckversion]
 
[http://wiki.zum.de/index.php?title=PH_Heidelberg/Bausteine/Diophantische_Gleichungen/Worksheet&printable=yes Druckversion]
 +
 +
 +
== Motivation ==
 +
 +
Wir haben neulich festgestellt, dass es sich mit Gleichungen folgender Form etwas seltsam verhält:
 +
 +
# <math>2\cdot x + 1\cdot y = 1</math>: Diese Gleichung hat unendlich viele Lösungen, nämlich z.B.: ______________________________
 +
# <math>6\cdot x + 9\cdot y = 18</math>: Diese hat _____________________ Lösungen.
 +
# <math>6\cdot x + 9\cdot y = 14</math>: 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 <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>.
 +
 +
Das gelingt durch Rückwärtsarbeiten. Aus der vorletzten Zeile wissen wir:
 +
 +
<math>2 = 26 - 3\cdot 8</math>
 +
 +
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>
 +
 +
Voilá!
 +
 +
{{#ev:youtube|bNa_fLCs5GA}}
 +
 +
Das klappt auf diese Weise natürlich immer. Betrachten wir das mal allgemein, und zwar zwei aufeinanderfolgende Schritte im Euklidischen Algorithmus:
 +
 +
* ...
 +
* <math>a_i = q_i\cdot b_i + r_i</math>
 +
* <math>a_{i+1} = q_{i+1}\cdot b_{i+1} + r_{i+1}</math>
 +
* ...
 +
 +
Das Rückwärtsarbeiten wie oben hat uns folgende Gleichung beschert:
 +
 +
<math>ggT(a,b) = x_{i+1}\cdot a_{i+1} + y_{i+1}\cdot b_{i+1}</math>
 +
 +
Außerdem wissen wir, dass <math>a_{i+1} = b_{i}</math> ist, und dass <math>b_{i+1} = r_i = a_i-q_i\cdot b_i</math>
 +
 +
Einsetzen, umstellen und freuen: <math>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</math>
 +
 +
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:
 +
 +
{| class="wikitable"
 +
 +
|-
 +
| '''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>34</math> || <math>26</math> || <math>1</math> || <math>8</math> || <math>-3</math> || <math>1-1\cdot(-3)=4</math>
 +
|-
 +
| <math>26</math> || <math>8</math> || <math>3</math> || <math>2</math> || <math>1</math> || <math>0-3\cdot 1 = -3</math>
 +
|-
 +
| <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 ==
 
== Aussage ==
Zeile 203: Zeile 286:
  
 
{{PHHDLückeGroß}}
 
{{PHHDLückeGroß}}
 +
 +
 +
 +
 +
 +
 +
 +
=== Satz ===
 +
 +
Der <math>ggT(a,b)</math> kann als Linearkombination von <math>a</math> und <math>b</math> geschrieben werden. Die Gleichung <math>a\cdot x + b\cdot y = ggT(a,b)</math> ist also lösbar.
 +
 +
 +
=== 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>.
 +
 +
Beweis:
 +
 +
1. Sei <math>(x_0, y_0)</math> eine Lösung der Gleichung. Dann gilt <math>a\cdot x_0 + b\cdot y_0 = c</math>. Sei <math>d=ggT(a,b)</math>. Weil <math>d</math> die linke Seite der Gleichung teilt, muss <math>d</math> auch die rechte Seite der Gleichung teilen, also <math>ggT(a,b)|c</math>.
 +
 +
2. Es gelte <math>ggT(a,b)|c</math>, somit existiert ein <math>z\in\mathbb{Z}</math> mit  <math>c=z\cdot ggT(a,b)</math>. Wir wissen mittlerweile, dass es ein Paar <math>(x_0, y_0)</math> gibt mit <math>a\cdot x_0 + b\cdot y_0 = ggT(a,b)</math>. Wir multiplizieren beide Seiten der Gleichung mit <math>z</math>, dann ergibt sich: <math>a\cdot (z\cdot x_0) + b\cdot (z\cdot y_0) = z\cdot ggT(a,b)</math>. Also haben wir mit <math>(z\cdot x_0, z\cdot y_0)</math> eine Lösung gefunden.
 +
 +
 +
Hieraus lässt sich direkt ableiten:
 +
 +
* Der <math>ggT(a,b)</math> ist die kleinste natürliche Zahl, die als Linearkombination von <math>a</math> und <math>b</math> darstellbar ist.
 +
* Die diophantische Gleichung <math>a\cdot x + b\cdot y = 1</math> ist genau dann lösbar, wenn <math>a</math> und <math>b</math> teilerfremd sind.
 +
* Damit gilt auch: Wenn <math>a</math> und <math>b</math> teilerfremd sind, dann ist jede ganze Zahl als Linearkombination von <math>a</math> und <math>b</math> darstellbar.
 +
 +
=== 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>.
 +
 +
Beweis: Sei <math>z\in\mathbb{Z}</math>. Dann ist <math>(x_0+\frac{z\cdot b}{ggT(a,b)}, y_0-\frac{z\cdot a}{ggT(a,b)})</math> tatsächlich eine Lösung, denn: <math>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</math>
 +
 +
Es ist auch tatsächlich jede Lösung von dieser Form, wie folgende Überlegung zeigt:
 +
 +
Sei <math>(x,y)</math> eine weitere Lösung. Wir wissen also: <math>a\cdot x + b\cdot y = c</math> und <math>a\cdot x_0 + b\cdot y_0 = c</math> . Die Subtraktion der beiden Gleichungen liefert
 +
 +
<math>a\cdot (x-x_0) + b\cdot (y-y_0) = 0</math>
 +
 +
also
 +
 +
<math>a\cdot (x-x_0) = b\cdot (y_0-y)</math>
 +
 +
Wir können außerdem beide Seiten durch <math>ggT(a,b)</math> teilen:
 +
 +
<math>\frac{a}{ggT(a,b)}\cdot (x-x_0) = \frac{b}{ggT(a,b)}\cdot (y_0-y)</math>
 +
 +
Wir wissen, dass <math>\frac{a}{ggT(a,b)}</math> und <math>\frac{b}{ggT(a,b)}</math> teilerfremd sind, also muss gelten <math>\frac{b}{ggT(a,b)}|(x-x_0)</math>, somit existiert ein <math>z\in\mathbb{Z}</math> mit  <math>(x-x_0)=z\cdot \frac{b}{ggT(a,b)}</math>.In die Gleichung eingesetzt ergibt sich:
 +
 +
<math>\frac{a}{ggT(a,b)}\cdot z\cdot \frac{b}{ggT(a,b)} = \frac{b}{ggT(a,b)}\cdot (y_0-y)</math>
 +
 +
Somit ist <math>(y_0-y)=z\cdot \frac{a}{ggT(a,b)}</math>
 +
 +
Wenn man jeweils nach <math>x</math> und <math>y</math> umformt, ergibt sich gerade die oben genannte Form.
 +
 +
=== 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>.
 +
 +
Wir müssen zunächst einmal den <math>ggT(168,238)</math> bestimmen und testen, ob dieser die Zahl <math>126</math> teilt (ansonsten könnten wir sofort aufhören).
 +
 +
Der erweiterte Euklidische Algorithmus ergibt:
 +
 +
{| class="wikitable"
 +
|-
 +
| '''a''' || '''b''' || '''q'''|| '''r'''|| '''x'''|| '''y'''
 +
|-
 +
| <math>238</math> || <math>168</math> || <math>1</math>|| <math>70</math> || <math>5</math> || <math>-7</math>
 +
|-
 +
| <math>168</math> || <math>70</math> || <math>2</math>|| <math>28</math> || <math>-2</math> || <math>5</math>
 +
|-
 +
| <math>70</math> || <math>28</math> || <math>2</math>|| <math>14</math> || <math>1</math> || <math>-2</math>
 +
|-
 +
| <math>28</math> || <math>14</math> || <math>2</math>|| <math>0</math> || <math>0</math> || <math>1</math>
 +
|}
 +
 +
Somit ist <math>ggT(168,238)=14=168\cdot(-7)+238\cdot 5</math>.
 +
 +
Außerdem gilt: <math>14|126</math>, nämlich <math>126=14\cdot 9</math>.
 +
 +
Wir müssen also die Gleichung mit <math>9</math> multiplizieren und erhalten:
 +
 +
<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>

Version vom 15. November 2012, 11:33 Uhr

Druckversion


Motivation

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

  1. 2\cdot x + 1\cdot y = 1: Diese Gleichung hat unendlich viele Lösungen, nämlich z.B.: ______________________________
  2. 6\cdot x + 9\cdot y = 18: Diese hat _____________________ Lösungen.
  3. 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:

  •  128 = 3\cdot 34 + 26
  •  34 = 1\cdot 26 + 8
  •  26 = 3\cdot 8 + 2
  •  8 = 4\cdot 2 + 0

Der ggT(128,34) ist als 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. Aus der vorletzten Zeile wissen wir:

2 = 26 - 3\cdot 8

WIe kam die 8 zustande? Aus der Zeile drüber mit 8 = 34 - 1\cdot 26. Eingesetzt und zusammengefasst:

2 = 26 - 3\cdot(34-1\cdot 26) = 26 - 3\cdot 34 + 3\cdot 26 = -3\cdot 34 + 4\cdot 26

Wie kam die 26 zustande? Naja, wiederum aus der Zeile vorher mit 26 = 128 - 3\cdot 34. Eingesetzt und zusammengefasst:

2 = -3\cdot 34 + 4\cdot (128 - 3\cdot 34) = 4\cdot 128 -15\cdot 34

Voilá!

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 3 26 4 -3-3\cdot4=-15
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 unterste Zeile ergibt sich einfach aus b = 0\cdot a + 1\cdot b).

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:

Eine Aussage ist


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