Worksheet: Unterschied zwischen den Versionen
(→Erweiterter Euklidischer Algorithmus) |
(→Aussage) |
||
Zeile 62: | Zeile 62: | ||
Die allgemeine Umformung lässt deutlich werden: Das klappt immer. Insofern können wir aus diesem konstruktiven Beweis folgern: | Die allgemeine Umformung lässt deutlich werden: Das klappt immer. Insofern können wir aus diesem konstruktiven Beweis folgern: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Junktoren == | == Junktoren == |
Version vom 18. Dezember 2012, 14:53 Uhr
Motivation
Wir haben neulich festgestellt, dass es sich mit Gleichungen folgender Form etwas seltsam verhält:
-
: Diese Gleichung hat unendlich viele Lösungen, nämlich z.B.: ______________________________
-
: Diese hat _____________________ Lösungen.
-
: 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 existiert. Alternative Frage: Ist der
immer als Linearkombination von
und
darstellbar?
Wir schauen erst einmal an einem konkreten Beispiel, was da zu machen ist. Wir berechnen den mit dem Euklidischen Algorithmus:
Der ist also
. Wir wollen also nun versuchen,
und
zu finden derart, dass
.
Das gelingt durch Rückwärtsarbeiten. Schreibe die Rechnungen, mit denen man und
findet:
Das klappt auf diese Weise natürlich immer. Betrachten wir das mal allgemein, und zwar zwei aufeinanderfolgende Schritte im Euklidischen Algorithmus:
- ...
-
-
- ...
Das Rückwärtsarbeiten wie oben hat uns folgende Gleichung beschert:
Außerdem wissen wir, dass ist, und dass
Einsetzen, umstellen und freuen:
Also ergibt sich folgende Regel: und
.
Dies resultiert im erweiterten Euklidischen Algorithmus, der in Tabellenform einfach und schnell durchzuführen ist:
a | b | q | r | x | y |
![]() |
![]() |
||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
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 (
|
![]() |
![]() |
f | |
w |
Konjunktion (
; UND)
![]() |
![]() |
![]() |
f | f | |
f | w | |
w | f | |
w | w |
Disjunktion (
; ODER)
![]() |
![]() |
![]() |
f | f | |
f | w | |
w | f | |
w | w |
Implikation (
|
![]() |
![]() |
![]() |
Äquivalenz (
; GENAU DANN WENN)
![]() |
![]() |
![]() |
Prioritäten
Ähnlich wie bei der Punkt-vor-Strichrechnung gibt es Prioritäten der einzelnen Junktoren. Es gilt:
vor
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 dasselbe ist wie
. Anhand einer Wahrheitstafel kann man diese Vermutung beweisen. Fülle die Tabelle vollständig aus.
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Woran erkennt man, dass und
ä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 kann als Linearkombination von
und
geschrieben werden. Die Gleichung
ist also lösbar.
Lösbarkeit linearer diophantischer Gleichungen
Satz: Lineare diophantische Gleichungen der Form mit
sind genau dann lösbar, wenn
.
Beweis:
1. Sei eine Lösung der Gleichung. Dann gilt
. Sei
. Weil
die linke Seite der Gleichung teilt, muss
auch die rechte Seite der Gleichung teilen, also
.
2. Es gelte , somit existiert ein
mit
. Wir wissen mittlerweile, dass es ein Paar
gibt mit
. Wir multiplizieren beide Seiten der Gleichung mit
, dann ergibt sich:
. Also haben wir mit
eine Lösung gefunden.
Hieraus lässt sich direkt ableiten:
- Der
ist die kleinste natürliche Zahl, die als Linearkombination von
und
darstellbar ist.
- Die diophantische Gleichung
ist genau dann lösbar, wenn
und
teilerfremd sind.
- Damit gilt auch: Wenn
und
teilerfremd sind, dann ist jede ganze Zahl als Linearkombination von
und
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 gefunden hat, dann findet man die gesamte Lösungsmenge mit:
.
Beweis: Sei . Dann ist
tatsächlich eine Lösung, denn:
Es ist auch tatsächlich jede Lösung von dieser Form, wie folgende Überlegung zeigt:
Sei eine weitere Lösung. Wir wissen also:
und
. Die Subtraktion der beiden Gleichungen liefert
also
Wir können außerdem beide Seiten durch teilen:
Wir wissen, dass und
teilerfremd sind, also muss gelten
, somit existiert ein
mit
.In die Gleichung eingesetzt ergibt sich:
Somit ist
Wenn man jeweils nach und
umformt, ergibt sich gerade die oben genannte Form.
Beispiel
Wir wollen wissen, ob die Gleichung lösbar ist, und wenn ja, für welche
.
Wir müssen zunächst einmal den bestimmen und testen, ob dieser die Zahl
teilt (ansonsten könnten wir sofort aufhören).
Der erweiterte Euklidische Algorithmus ergibt:
a | b | q | r | x | y |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Somit ist .
Außerdem gilt: , nämlich
.
Wir müssen also die Gleichung mit multiplizieren und erhalten:
.
Allgemein sind die Lösungen: und