Lineare Dioph. Gl. (3 Unbek.) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:34 Mi 07.10.2009 | | Autor: | daN-R-G |
| Aufgabe | | Lösen sie die lineare diophantische Gleichung 35x+55y+77z = 3 |
Hallo! Ich habe da mal ne Frage zu der Gleichung.
Wie ich dioph. Gleichungen mit 2 Unbekannten löse ist mir eigentlich klar. Aber bei dieser mit 3 Unbekannten komme ich nicht so recht weiter.
Damit die Gleichung überhaupt lösbar ist, muss ja gelten
ggT(35, 55, 77) | 3
Es gilt ja ggT(35, 55) = 5 und ggT(5, 77) = 1. Und da 1 auch 3 teilt, ist die Gleichung lösbar.
Hätte ich eine Gleichung mit 2 Unbekannten, sagen wir einmal 2x + 7y = 4
Der ggT(2,7) ist also 1. Somit schonmal lösbar
Erster Weg:
2x [mm] \equiv [/mm] 4 (mod 7) [mm] \gdw [/mm] x [mm] \equiv [/mm] 2 (mod 7) [mm] \Rightarrow [/mm] x = 7k+2
in die Gleichung eingesetzt und umgeformt ergibt y = -2k
Zweiter Weg:
1 = [mm] 2x_0 [/mm] + [mm] 7y_0
[/mm]
1 = 2(4) + 7(-1) (Also gilt [mm] x_0 [/mm] = 4 und [mm] y_0 [/mm] = -1 bis hierhin)
4 = 2(16) + 7(-4) (Also ist [mm] x_0 [/mm] = 16 und [mm] y_0 [/mm] = -4 eine spezielle Lösung)
Um alle Lösungen zu berechnen, errechne ich nunr folgendes, wobei d := ggT(2,7) = 1
a' = 2/d = 2 und b' = 7/d = 7
Die Lösungen haben also nun die Form [mm] (x_0 [/mm] -bt, [mm] y_0 [/mm] + at), im speziellen Fall also (16 - 7t, -4 + 2t) mit t [mm] \in \IZ
[/mm]
Hoffe das stimmt so weit.
Aber wie gehe ich denn nun am besten vor, wenn ich 3 Unbekannte habe? Substituiere ich? Gibt es nen klaren Algorithmus?
Hoffe mir kann jemand helfen :)
Edit: Es geht natürlich nur um ganzzahlige Lösungen!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:00 Mi 07.10.2009 | | Autor: | felixf |
Hallo!
> Lösen sie die lineare diophantische Gleichung 35x+55y+77z
> = 3
> Hallo! Ich habe da mal ne Frage zu der Gleichung.
>
> Wie ich dioph. Gleichungen mit 2 Unbekannten löse ist mir
> eigentlich klar. Aber bei dieser mit 3 Unbekannten komme
> ich nicht so recht weiter.
Du fuehrst das auf den Fall zurueck:
Sagen wir, du hast die Gleichung $a x + b y + c z = d$. Ist $d = ggT(a, b)$, so kannst du $a a' + b b' = d$ schreiben mit $a', b' [mm] \in \IZ$. [/mm] Also kannst du die Wertemenge von [mm] $\{ a x + b y \mid x, y \in \IZ \}$ [/mm] durch [mm] $\{ (a a' + b b') x' \mid x' \in \IZ \}$ [/mm] beschreiben, und es reicht die Gleichung $(a a' + b b') x' + c z = d$ loesen mit zwei Unbekannten: aus einer Loesung bekommst du dann mit $x = a' x'$ und $y = b' x'$ eine Loesung von $a x + b y + c z = d$.
Alternativ stellst du $ggT(a, b, c) = a a' + b b' + c c'$ dar mit $a', b', c' [mm] \in \IZ$: [/mm] dann sind $x = a' [mm] \frac{d}{ggT(a, b, c)}$, [/mm] $y = b' [mm] \frac{d}{ggT(a, b, c)}$, [/mm] $z = c' [mm] \frac{d}{ggT(a, b, c)}$ [/mm] eine Loesung.
Wie du daraus dann die allgemeinen Loesungen bekommst, darfst du erstmal selber versuchen :) So schwer ist es nicht...
> Damit die Gleichung überhaupt lösbar ist, muss ja gelten
> ggT(35, 55, 77) | 3
> Es gilt ja ggT(35, 55) = 5 und ggT(5, 77) = 1. Und da 1
> auch 3 teilt, ist die Gleichung lösbar.
Genau.
>
> Hätte ich eine Gleichung mit 2 Unbekannten, sagen wir
> einmal 2x + 7y = 4
> Der ggT(2,7) ist also 1. Somit schonmal lösbar
>
> Erster Weg:
> 2x [mm]\equiv[/mm] 4 (mod 7) [mm]\gdw[/mm] x [mm]\equiv[/mm] 2 (mod 7) [mm]\Rightarrow[/mm] x
> = 7k+2
> in die Gleichung eingesetzt und umgeformt ergibt y = -2k
>
> Zweiter Weg:
> 1 = [mm]2x_0[/mm] + [mm]7y_0[/mm]
> 1 = 2(4) + 7(-1) (Also gilt [mm]x_0[/mm] = 4 und [mm]y_0[/mm] = -1 bis
> hierhin)
> 4 = 2(16) + 7(-4) (Also ist [mm]x_0[/mm] = 16 und [mm]y_0[/mm] = -4 eine
> spezielle Lösung)
Ja.
> Um alle Lösungen zu berechnen, errechne ich nunr
> folgendes, wobei d := ggT(2,7) = 1
>
> a' = 2/d = 2 und b' = 7/d = 7
>
> Die Lösungen haben also nun die Form [mm](x_0[/mm] -bt, [mm]y_0[/mm] + at),
Du musst $a$ und $b$ noch durch den ggT (hier: 1) teilen. Ansonsten bekommst du nicht alle Loesungen.
> im speziellen Fall also (16 - 7t, -4 + 2t) mit t [mm]\in \IZ[/mm]
>
> Hoffe das stimmt so weit.
Ja.
> Aber wie gehe ich denn nun am besten vor, wenn ich 3
> Unbekannte habe? Substituiere ich? Gibt es nen klaren
> Algorithmus?
Siehe oben: ich wuerde das reduzieren um eine Variable auf 2 machen. (Insbesondere um alle Loesungen zu bestimmen, da kannst du dann immer das obige Verfahren benutzen was du schon fuer zwei Variablen kennst.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:36 Mi 07.10.2009 | | Autor: | daN-R-G |
Erstmal herzlichen Danke! :)
Erstmal hierzu:
> Du musst $ a $ und $ b $ noch durch den ggT (hier: 1) teilen. Ansonsten bekommst du nicht alle Loesungen.
Natürlich! Habe ja eigentlich a' und b' berechnet, aber die dann nicht in meiner allgemeinen Lösung verwendet.
Nun zu deinem Vorschlag: Habe das leider noch nicht ganz verstanden.
> Ist $ d = ggT(a, b) $, so kannst du $ a a' + b b' = d $ schreiben mit $ a', b' [mm] \in \IZ [/mm] $.
Du meinst damit jetzt aber nicht, dass der ggT(a,b) = d, also der Lösung der Gleichung sein soll, oder? ggT(35, 55) = 5 != 3.
Oder ist das d nun einfach nur doppelt vergeben?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:19 Mi 07.10.2009 | | Autor: | felixf |
Hallo!
> > Du musst [mm]a[/mm] und [mm]b[/mm] noch durch den ggT (hier: 1) teilen.
> > Ansonsten bekommst du nicht alle Loesungen.
>
> Natürlich! Habe ja eigentlich a' und b' berechnet, aber
> die dann nicht in meiner allgemeinen Lösung verwendet.
Ok :)
> Nun zu deinem Vorschlag: Habe das leider noch nicht ganz
> verstanden.
>
> > Ist [mm]d = ggT(a, b) [/mm], so kannst du [mm]a a' + b b' = d[/mm] schreiben
> mit [mm]a', b' \in \IZ [/mm].
>
> Du meinst damit jetzt aber nicht, dass der ggT(a,b) = d,
> also der Lösung der Gleichung sein soll, oder? ggT(35, 55)
> = 5 != 3.
> Oder ist das d nun einfach nur doppelt vergeben?
Aeh ja, das $d$ ist doppelt vergeben. Sorry :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:34 Mi 07.10.2009 | | Autor: | daN-R-G |
Dann will ich mal versuchen, ob ich das irgendwie auf die Reihe bekomme. Das will ich heute noch unbedingt schaffen :) Ich versuchs einfach mal Schritt für Schritt und hoffe, dass der Groschen dann fällt.
Wenn ich das jetzt richtig verstanden habe, müsste ich zuerst aa' + bb' = ggT(a,b) berechnen:
35a' + 55b' = 5
Wenn ich durch 5 teilen würde, bekäme ich
7a' + 11b' = 1 (Dies wäre nun z.B. der fall für a' = -3 und b' = 2)
Aber irgendwie befürchte ich, dass ich das ganze System noch nicht so recht verstanden habe. Bin ich damit schon auf dem richtigen Weg?
Ich schreib lieber nochmal alles auf nen Zettel...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:09 Mi 07.10.2009 | | Autor: | felixf |
Hallo!
> Dann will ich mal versuchen, ob ich das irgendwie auf die
> Reihe bekomme. Das will ich heute noch unbedingt schaffen
> :) Ich versuchs einfach mal Schritt für Schritt und hoffe,
> dass der Groschen dann fällt.
>
> Wenn ich das jetzt richtig verstanden habe, müsste ich
> zuerst aa' + bb' = ggT(a,b) berechnen:
> 35a' + 55b' = 5
>
> Wenn ich durch 5 teilen würde, bekäme ich
>
> 7a' + 11b' = 1 (Dies wäre nun z.B. der fall für a' = -3
> und b' = 2)
Genau.
> Aber irgendwie befürchte ich, dass ich das ganze System
> noch nicht so recht verstanden habe. Bin ich damit schon
> auf dem richtigen Weg?
Du bist auf dem richtigen Weg. Allerdings: kennst du den ![[]](/images/popup.gif) Erweiterten Euklidischen Algorithmus (EEA)? Das ist ein einfacher Algorithmus, der dir direkt $a'$ und $b'$ liefert mit $a a' + b b' = ggT(a, b)$ (und den ggT rechnet er auch mit aus). Wenn du jetzt also nicht so schoene kleine Zahlen hast, sondern z.B. $981237843 x + 12898198912 y = 879879871821$ und schauen willst ob es loesbar ist und wenn ja, wie die Loesungen aussehen, dann hilft dir der EEA wesentlich weiter :)
Fuer lineare diophantische Gleichungen mit zwei Unbestimmten schaue uebrigens auch hier. Das hier koennte dich auch interessieren.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:38 Mi 07.10.2009 | | Autor: | daN-R-G |
Also von dem Algorithmus habe ich schon gehört. Den werde ich mir auf jedenfall auch noch einprägen.
Aber in so einem Fall, wo man die Werte schon recht einfach erraten kann, wäre man glaube ich ein wenig schneller.
Also gut. Ich habe dann jetzt als a' = -3 und b' = 2
Somit hätte ich nun (aa' + bb')x' + cz = d, also
(35*(-3) + 55*2)x' + 77c = 3
[mm] \gdw [/mm] -5x' + 77z = 3
Wenn ich ggT(-5,77) berechne, bekomme ich 1 und diese Gleichung wäre auch lösbar.
Das ganze kann ich dann ja auch als Kongruenz schreiben:
-5x' [mm] \equiv [/mm] 3 (mod 77) [mm] \gdw [/mm] -5x' [mm] \equiv [/mm] 80 (mod 77) [mm] \gdw [/mm] x' [mm] \equiv [/mm] -20 (mod 77)
Somit hätte ich dann herraus, dass [mm] x_0' [/mm] = 77k -20 wäre und wenn ich das in die Gleichung einsetze um z zu berechnen, bekomme ich
-5 (77k -20) +77z = 3 [mm] \gdw [/mm] 5*77k + 100 +77z = 3 [mm] \gdw [/mm] 77z = 97 +55*77k
Jetzt habe ich das Problem, dass 97/77 nicht ganz wäre, also muss ja irgendwo ein Fehler sein :/
Habe ich doch noch was falsch gemacht?
Aber vielen Dank für deine Geduld!
|
|
|
| |
|
Hallo daN-R-G,
> Also von dem Algorithmus habe ich schon gehört. Den werde
> ich mir auf jedenfall auch noch einprägen.
> Aber in so einem Fall, wo man die Werte schon recht
> einfach erraten kann, wäre man glaube ich ein wenig
> schneller.
>
> Also gut. Ich habe dann jetzt als a' = -3 und b' = 2
> Somit hätte ich nun (aa' + bb')x' + cz = d, also
> (35*(-3) + 55*2)x' + 77c = 3
> [mm]\gdw[/mm] -5x' + 77z = 3
>
> Wenn ich ggT(-5,77) berechne, bekomme ich 1 und diese
> Gleichung wäre auch lösbar.
>
> Das ganze kann ich dann ja auch als Kongruenz schreiben:
>
> -5x' [mm]\equiv[/mm] 3 (mod 77) [mm]\gdw[/mm] -5x' [mm]\equiv[/mm] 80 (mod 77) [mm]\gdw[/mm] x'
> [mm]\equiv[/mm] -20 (mod 77)
Diese Lösung stimmt nicht, da
[mm]\left(-5\right)*\left(-20\right)=100 \equiv 23 \not=3 \operatorname{(mod \ 77)}[/mm]
>
> Somit hätte ich dann herraus, dass [mm]x_0'[/mm] = 77k -20 wäre
> und wenn ich das in die Gleichung einsetze um z zu
> berechnen, bekomme ich
> -5 (77k -20) +77z = 3 [mm]\gdw[/mm] 5*77k + 100 +77z = 3 [mm]\gdw[/mm] 77z =
> 97 +55*77k
Für die Bestimmung von z kannst Du die Gleichung
[mm] -5x' + 77z = 3 [/mm]
modulo 5 betrachten.
>
> Jetzt habe ich das Problem, dass 97/77 nicht ganz wäre,
> also muss ja irgendwo ein Fehler sein :/
>
> Habe ich doch noch was falsch gemacht?
>
> Aber vielen Dank für deine Geduld!
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:22 Mi 07.10.2009 | | Autor: | daN-R-G |
Hallo MathePower
Natürlich stimmt das nicht *g* Oh man... 80/5 sollte natürlich 16 sein.
Dann bekäme ich für [mm] x_0' [/mm] = 77k -16
Wenn ich das dann in die Gleichung einsetze, bekomme ich für z = 5k-1
> Für die Bestimmung von z kannst Du die Gleichung
> $ -5x' + 77z = 3 $
> modulo 5 betrachten.
Das versteh ich grad leider nicht so ganz, wieso das so wäre.
Als Kongruenz geschrieben wäre das doch -5 [mm] \equiv [/mm] 3 (mod 77)
Kann ich das eigentlich auch als 77z [mm] \equiv [/mm] 3 (mod 5) schreiben? Falls du das meinst?
Nun nochmal zu meinen Lösungen oben. Das sieht ja eigentlich schonmal ganz gut aus. Nun hätte ich dann Spezielle Lösungen von x' und z.
Aber wie komme ich dann auf die allgemeinen Lösungen von x, y und z
Irgendwie verstehe ich den Zusammenhang leider noch nicht so ganz. Sofern mein Ergebnis überhaupt korrekt ist.
Ich hoffe mir ist noch zu helfen...
|
|
|
| |
|
Hallo daN-R-G,
> Hallo MathePower
>
> Natürlich stimmt das nicht *g* Oh man... 80/5 sollte
> natürlich 16 sein.
>
> Dann bekäme ich für [mm]x_0'[/mm] = 77k -16
>
> Wenn ich das dann in die Gleichung einsetze, bekomme ich
> für z = 5k-1
![[ok]](/images/smileys/ok.gif "[ok]")
>
> > Für die Bestimmung von z kannst Du die Gleichung
> > [mm]-5x' + 77z = 3[/mm]
> > modulo 5 betrachten.
>
> Das versteh ich grad leider nicht so ganz, wieso das so
> wäre.
Wenn Du das modulo 5 betrachtest, dann steht da
[mm]77z \equiv 2z \equiv 3 \ \operatorname{mod \ 5}[/mm]
Als Lösung ergibt sich hier: [mm] z \equiv 4 \ \operatorname{mod \ 5}[/mm]
Woraus sich [mm]z=4+5*l[/mm] ergibt.
Setze ich die gewonnenen Erkenntniss in die Gleichung
[mm]-5*x'+77*z=3[/mm]
ein, dann folgt [mm]l=k-1[/mm].
Hieraus ergibt sich wiederum [mm]z=5+5*\left(k-1\right)=5*k-1[/mm].
>
> Als Kongruenz geschrieben wäre das doch -5 [mm]\equiv[/mm] 3 (mod
> 77)
> Kann ich das eigentlich auch als 77z [mm]\equiv[/mm] 3 (mod 5)
> schreiben? Falls du das meinst?
>
> Nun nochmal zu meinen Lösungen oben. Das sieht ja
> eigentlich schonmal ganz gut aus. Nun hätte ich dann
> Spezielle Lösungen von x' und z.
> Aber wie komme ich dann auf die allgemeinen Lösungen von
> x, y und z
> Irgendwie verstehe ich den Zusammenhang leider noch nicht
> so ganz. Sofern mein Ergebnis überhaupt korrekt ist.
>
> Ich hoffe mir ist noch zu helfen...
>
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:13 Mi 07.10.2009 | | Autor: | daN-R-G |
Ahhh. Okay! Das habe ich schonmal verstanden!
Vielen Dank! :)
Das Ergebnis scheint dann bis dahin ja auch schonmal zu stimmen.
Leider weiß ich noch nicht, wie ich auf die allgemeinen Lösungen zu x, y und z komme.
Im Prinzip habe ich ja nun [mm] x_0' [/mm] und [mm] z_0 [/mm] als spezielle Lösungen
Ich vermute, dass z = [mm] (z_0), [/mm] x = [mm] x_0' [/mm] - b'/d * t und y = [mm] y_0 [/mm] +a'/d*t oder etwas ähnliches gelten muss.
|
|
|
| |
|
Hallo daN-R-G,
> Ahhh. Okay! Das habe ich schonmal verstanden!
>
> Vielen Dank! :)
>
> Das Ergebnis scheint dann bis dahin ja auch schonmal zu
> stimmen.
Die Gleichung lautet doch
[mm]\red{+}5*x'+77*z=3[/mm]
,da [mm]35*\left(-3\right)+55*2=5 \not= -5[/mm].
Welche als Lösungen
[mm]x'=16+77*k, \ z= -1-5*k[/mm]
besitzt.
>
> Leider weiß ich noch nicht, wie ich auf die allgemeinen
> Lösungen zu x, y und z komme.
>
> Im Prinzip habe ich ja nun [mm]x_0'[/mm] und [mm]z_0[/mm] als spezielle
> Lösungen
>
> Ich vermute, dass z = [mm](z_0),[/mm] x = [mm]x_0'[/mm] - b'/d * t und y =
> [mm]y_0[/mm] +a'/d*t oder etwas ähnliches gelten muss.
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:18 Do 08.10.2009 | | Autor: | felixf |
Hallo!
> Nun nochmal zu meinen Lösungen oben. Das sieht ja
> eigentlich schonmal ganz gut aus. Nun hätte ich dann
> Spezielle Lösungen von x' und z.
Genau.
> Aber wie komme ich dann auf die allgemeinen Lösungen von
> x, y und z
Erstmal: die allgemeine Loesung von $5 x' + 77 z = 3$ kannst du ja bestimmen.
Zu jedem $z$ ist $x'$ eindeutig bestimmt: du kannst nun zu jedem solchen $x'$ wieder die allgemeine Loesung fuer $a x + b y = 5 x'$ finden.
Etwas konkreter: die allgemeine Loesung von $5 x' + 77 z = 3$ ist ja $(x', z) = (16 - 77 k, -1 + 5 k)$, $k [mm] \in \IZ$.
[/mm]
Jetzt suchen wir die allgemeine Loesung fuer $35 x + 55 y = 5 [mm] \cdot [/mm] (16 - 77 k)$. Die allgemeine Loesung fuer $35 x + 55 y = 5$ ist gegeben durch $(-3 - 11 [mm] \ell, [/mm] 2 + 7 [mm] \ell)$ [/mm] mit [mm] $\ell \in \IZ$, [/mm] also ist die allgemeine Loesung fuer $35 x + 55 y = 5 (16 - 77 k)$ gegeben durch $((-3) (16 - 77 k) - 11 [mm] \ell, [/mm] 2 (16 - 77 k) + 7 [mm] \ell)$ [/mm] (einfach die spezielle Loesung skalieren).
Die allgemeine Loesung fuer $35 x + 55 y + 77 z = 3$ ist also gegeben durch $(-3 [mm] \cdot [/mm] 16 + 3 [mm] \codt [/mm] 77 k - 11 [mm] \ell, [/mm] 32 - 2 [mm] \cdot [/mm] 77 k + 7 [mm] \ell, [/mm] -1 + 5 k)$ mit $k, [mm] \ell \in \IZ$.
[/mm]
LG Felix
|
|
|
|
