0 Daumen
341 Aufrufe

Hallo Leute kann mir jemand kurz und knapp diese Frage beantwortet? Danke :)


Sei \( a x+b y=c \) eine lösbare diophantische Gleichung und \( x_{0}, y_{0} \) die Lösung, die durch den euklidischen Algorithmus gefunden wird. Warum ist dann immer genau eine der beiden Zahlen
\( x_{0} \) und \( y_{0} \) positiv und die andere negativ?

Avatar von

2 Antworten

0 Daumen

Hallo,

ich gehe von positiven a,b aus. Dann findet man ja mit dem EuAlg eine Darstellung für den größten gemeinsamen Teiler g von a und b: Wenn man jetzt die kleinstmöglichen positiven x und y nimmt, also x=1 und y=1, dann

$$g=ax+by \geq g+g=2g$$

Gruß

Avatar von 14 k

Hallo,

ich hatte nur an den EuAlg gedacht. Die Lösung von Werner-Salomon liefert wichtig weitergehende Infos.

Gruß

0 Daumen

Hallo,

Willkommen in der Mathelounge!

zunächst mal ist das nicht der Fall, dass bei einer Lösung \((x_0;\,y_0)\) der diophantischen Gleichung $$ax + by = c$$immer eine der beiden Zahlen negativ ist. Ein einfaches Gegenbeispiel ist $$3x+ 5 y = 11$$Hier ist \((2;\, 1)\) eine Lösung dieser Gleichung und beide Zahlen sind positiv.

Du fragtest aber

... die durch den euklidischen Algorithmus gefunden wird. ...

Der erweiterte euklidische Algorithmus liefert zunächst die Lösung für \(ax' + by' = 1\). Ist hier eine Lösung für \((x'_0;\,y'_0)\) gefunden, so ist eine Lösung für \(ax + by = c\) schlicht $$(x_0;\,y_0) = (x'_0\cdot c;\, y'_0 \cdot c)$$Und bei der Lösung zu $$ax' + by' = 1$$muss zwangsläufig eine der beiden Zahlen \(x'\) oder \(y'\) negativ sein, wenn \(a\) oder \(b\) größer als \(1\) ist, was praktisch immer der Fall ist.

Nehmen wir das Beispiel von oben$$3x' + 5y' = 1 \implies (x_0';\, y_0') = (2;\, -1)$$Wieder ist eine der beiden Zahlen negativ und nach dem Vorgehen oben wäre nun$$(x_0;\, y_0) = (11x_0';\, 11y_0') = (22;\,-11)$$Das ist die Lösung, die Dir der übliche Lösungsweg liefern würde. Und hier ist tatsächlich prakisch immer eine der beiden Zahlen des Lösungspaar negativ. Daran ändert die Multiplikation mit \(c\) rein gar nichts.

Das ist aber nicht die einzige Lösung, denn mit dem Vielfachen der Lösung von folgender Gleichung$$3 u + 5 v = 0 \implies (u;\,v) = (-5;\,3)$$kann man eine gefundene Lösung addieren und bekommt eine neue. Hier ganz konkret$$(22;\, -11) + 4 \cdot (-5;\,3) = (22 - 4\cdot 5;\, -11 + 4\cdot 3) = (2;\,1)$$Zwei positive Zahen erhält man nur dann, wenn das \(c\) ausreichend groß ist, und die beiden Koeffizienten \(a\) und \(b\) 'passen'.

Das stellt man sich am besten graphisch vor. Die Gleichung \(ax+by = c\) beschreibt auch eine Gerade in der Ebene, deren Normalenvektor in Richtung des ersten Quadranten verläuft. Für unser Beispiel:

blob.png

Die Lösungen sind die Punkte, an denen die Gerade ganzzahlige Koordinaten hat. Da die Gerade aber immer einen Normalenvektor besitzt, der im ersten Quadranten liegt, durchquert die Gerade im wesentlichen den 2. und 4. Quadranten. Und dort ist immer genau eine der Koordinaten negativ.

Die Lösung \((2;\,1)\) ist in unserem Beispiel offensichtlich auch die einzige, bei der das nicht so ist.

Avatar von 48 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community