Gleichungen mit ganzzahligen Lösungen

20.10.2008, 02:34

Bjoern1982

Gleichungen mit ganzzahligen Lösungen

Hallo

Womöglich hätte ich das jetzt auch in der Schulmathematik posten können aber ich bin mir nicht so ganz sicher Augenzwinkern

(1)

Ich möchte ein notwendiges und ein hinreichendes Kriterium für die Lösbarkeit von $\begin{eqnarray*} \sum_{i=1}^n~a_ix_i=b \end{eqnarray*}$ (*) mit n aus IN und $\begin{eqnarray*} a_i,b,x_i \end{eqnarray*}$ aus IZ angeben.

a_i ungleich null für alle i von 1 bis n und b ungleich null ist wohl ein notwendiges Kriterium aber wie könnte ein hinreichendes lauten ?

(2)

27x+69y+1002z=10000
43x+37y+997z=10000

Hier soll man jeweils (wenn möglich) eine ganzzahlige Lösung mit x*y*z ungleich null angeben. Hierzu habe ich leider noch keinen Ansatz verwirrt

Bitte um Hilfe.

Björn

20.10.2008, 07:35

Auf diesen Beitrag antworten »

RE: Gleichungen mit ganzzahligen Lösungen
Das Kriterium ist wohlbekannt: Notwendig und hinreichend für die Lösbarkeit dieser Gleichung ist die Bedingung

$\begin{eqnarray*} \operatorname{ggT}(a_1,\ldots,a_n) \;\Big|\; b \end{eqnarray*}$ .

Zitat:

Original von Bjoern1982
a_i ungleich null für alle i von 1 bis n und b ungleich null ist wohl ein notwendiges Kriterium

Nein, wieso?

20.10.2008, 10:55

Bjoern1982

Auf diesen Beitrag antworten »

Aha, das hätte ich jetzt mal überhaupt nicht vermutet...
Ist das offensichtlich und vielleicht sogar trivial und ich bin grad etwas blind und erkenne den Zusammenhang nicht oder wie kommt diese Bedingung zustande ?
Das Stichwort in diesem Zusammenhang ist wohl "lineare diophantische Gleichung" oder ?

Bezogen auf die beiden Gleichungen wäre dann also die erste mit ggt(27,69,1002)=3, was kein Teiler von 10000 ist, nicht lösbar.
Die zweite Gleichung mit ggt(43,37,997)=1 hingegen auf jeden Fall.

Bleibt nun die Frage wie ich systematisch an eine Lösung komme verwirrt

Gruß Björn

Edit:

Zitat:

Zitat:
Original von Bjoern1982
a_i ungleich null für alle i von 1 bis n und b ungleich null ist wohl ein notwendiges Kriterium

Nein, wieso?

Naja ich dachte hier direkt an ein Kriterium, was zu einer falschen Aussage der Form 0=b mit b ungleich null führt - ich sehe aber nun ein dass es darauf nicht so ankommt sondern eher auf ein Kriterium für die Existenz GANZZAHLIGER Lösungen.

20.10.2008, 13:13

Auf diesen Beitrag antworten »

Der Fall n=2 dürfte (sollte) bekannt sein, mit dem EEA bzw. dem Lemma von Bézout.

Und der Rest ist Vollständige Induktion , basierend auf

$\begin{eqnarray*} \operatorname{ggT}(a_1,\ldots,a_n) = \operatorname{ggT}(\operatorname{ggT}(a_1,\ldots,a_{n-1}),a_n) \end{eqnarray*}$ .

20.10.2008, 15:22

Bjoern1982

Auf diesen Beitrag antworten »

Zwei Fragen:

1)

Die Aufgabenstellung lautet "Geben sie ein notwendiges und hinreichendes Kriterium für die Lösbarkeit der Gleichung (*) an"

Da steht im Prinzip ja nichts von einem Beweis oder einer Herleitung sondern nur das Angeben einer Bedingung oder würdest du sagen, dass ein Beweis durch Induktion hier auch noch mit rein sollte ?

2)

Für die untere Gleichung kam ich nach zahlreichen Umformungen auf

x=-12a-35c+25
y=-13a-121c+349
z=a+6c-4

und für a=c=0 dann auf ein mögliches Lösungstripel (25,349,-4)

Gibt es eine elegante, schnelle Variante, bei der man mit weniger Umformungen bzw Rückwärtseinsetzen auskommt ? Wie würdest eine mögliche Lösung bestimmen ?

20.10.2008, 16:12

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Zwei Fragen:

1)

Die Aufgabenstellung lautet "Geben sie ein notwendiges und hinreichendes Kriterium für die Lösbarkeit der Gleichung (*) an"

Da steht im Prinzip ja nichts von einem Beweis oder einer Herleitung sondern nur das Angeben einer Bedingung oder würdest du sagen, dass ein Beweis durch Induktion hier auch noch mit rein sollte ?

Also dass das Kriterium notwendig ist, ist leicht zu sehen: Jeder der Summanden $\begin{eqnarray*} a_ix_i \end{eqnarray*}$ ist durch den genannten ggT teilbar, also auch deren Summe. Wenn es also eine Lösung geben soll, dann muss die rechte Seite $\begin{eqnarray*} b \end{eqnarray*}$ notwendig auch durch diesen ggT teilbar sein.

Nur für den hinreichenden Teil ist dann der erwähnte Induktionsbeweis nötig.

Zitat:

Original von Bjoern1982
Wie würdest eine mögliche Lösung bestimmen ?

Auch rekursiv, von der Gleichung ausgehend: Es ist ggT(43,37)=1, also betrachte ich zuerst

$\begin{eqnarray*} 1\cdot a + 997 z = 10000 \end{eqnarray*}$

mit Hilfsvariable $\begin{eqnarray*} a \end{eqnarray*}$ . Wegen der "1" vorn ist z natürlich beliebig wählbar, der Einfachheit halber wähle ich mal $\begin{eqnarray*} z=10 \end{eqnarray*}$ (das geht natürlich nicht immer so einfach, nur wegen der "1"). Das bedingt dann $\begin{eqnarray*} a=30 \end{eqnarray*}$ .

Im zweiten Schritt muss ich dann

$\begin{eqnarray*} 43x+37y=30 \end{eqnarray*}$

lösen. Es gibt natürlich den Weg über Bézout und EEA, aber wenn ich das "von Hand" ausrechnen müsste, würde ich das abkürzen und diese Gleichung modulo 37 betrachten:

$\begin{eqnarray*} 6x \equiv 30 \mod 37 \end{eqnarray*}$

mit Lösung $\begin{eqnarray*} x\equiv 5\mod 37 \end{eqnarray*}$ . Mit der 30 habe ich da unverschämt Glück gehabt, andernfalls hätte ich noch etwas probieren müssen. Augenzwinkern

Dann gleich mal $\begin{eqnarray*} x=5 \end{eqnarray*}$ nehmen, womit $\begin{eqnarray*} y = \frac{30-43\cdot 5}{37} = -5 \end{eqnarray*}$ folgt, insgesamt also das Lösungstripel $\begin{eqnarray*} (5,-5,10) \end{eqnarray*}$

20.10.2008, 20:25

Bjoern1982

Auf diesen Beitrag antworten »

Hehe, also war wohl der Schlüssel zum Erfolg dass 43 kongruent 6 modulo 37 ist und sich deshalb z=10 gerade anbietet für a=30=43x+37y

Was mich noch etwas irritiert ist dein gezieltes Hinweisen auf die 1 vor dem a.
Ich dachte a=43x+37y ist eh nur eine ganz normale Substitution gewesen.
Würde man da noch einen anderen Faktor vorschreiben würde man sich doch nur unnötig das Leben schwer machen, da unter Umständen nachher für a keine ganze Zahl mehr durch die Division durch diesen Faktor resultiert oder verstehe ich dich falsch und du wolltest damit auf etwas anderes hinaus ?

Neue Frage »

Antworten »

Gleichungen mit ganzzahligen Lösungen

Verwandte Themen