Wie finde ich die ganzzahligen Lösungen einer diophantischen Gleichung?

30.01.2015, 12:33

brushmate

Wie finde ich die ganzzahligen Lösungen einer diophantischen Gleichung?

Meine Frage:
Hallo,

ich soll alle $\begin{eqnarray*} x, y \in \mathbb Z \end{eqnarray*}$ finden, für die die diophantische Gleichung $\begin{eqnarray*} 38145x - 80805y = 46425 \end{eqnarray*}$ gilt.

Meine Ideen:
Ich habe zunächst mit dem euklidschen Algorithmus $\begin{eqnarray*} ggT(38145, 80805) \end{eqnarray*}$ bestimmt:

$\begin{eqnarray*} \begin{tabular}{cccc} b & a & q & r \\ 80805 & 38145 & 2 & 4515 \\ 38145 & 4515 & 8 & 2025 \\ 4515 & 2025 & 2 & 465 \\ 2025 & 465 & 4 & 165 \\ 465 & 165 & 2 & 135 \\ 165 & 135 & 1 & 30 \\ 135 & 30 & 4 & 15 \\ 30 & 15 & 2 & 0 \\ \end{tabular} \end{eqnarray*}$

Also $\begin{eqnarray*} ggt(38145, 80805) = 15 \end{eqnarray*}$ . Da $\begin{eqnarray*} 15|46425 \end{eqnarray*}$ gilt, weiß ich, dass es ganzzahlige Lösungen gibt. Diese wollte ich dann mit dem erweiterten euklidschen Algorithmus finden. Dabei kam folgende Tabelle heraus:

$\begin{eqnarray*} \begin{tabular}{cccccc} b & a & q & r &y & x\\ 80805 & 38145 & 2 & 4515 & 1149 & -2434 \\ 38145 & 4515 & 8 & 2025 & -136 & 1149 \\ 4515 & 2025 & 2 & 465 & 61 & -136 \\ 2025 & 465 & 4 & 165 & -14 & 61 \\ 465 & 165 & 2 & 135 & 5 & -14 \\ 165 & 135 & 1 & 30 & -4 & 5 \\ 135 & 30 & 4 & 15 & 1 & -4 \\ 30 & 15 & 2 & 0 & 0 & 1 \\ \end{tabular} \end{eqnarray*}$

Wenn ich die Werte $\begin{eqnarray*} x = -2434 \end{eqnarray*}$ und $\begin{eqnarray*} y = 1149 \end{eqnarray*}$ in die Gleichung $\begin{eqnarray*} 38145x - 80805y \end{eqnarray*}$ einsetze, sollte ich ja eigentlich den ggT, also 15, erhalten. Es gilt jedoch $\begin{eqnarray*} 38145 \cdot (-2434) - 80805 \cdot 1149 = -18568975 \end{eqnarray*}$ . Durch Probieren habe ich herausgefunden, dass eigentlich $\begin{eqnarray*} x = -2434 \end{eqnarray*}$ und $\begin{eqnarray*} y = -1149 \end{eqnarray*}$ gelten müsste, um 15 zu erhalten.

Mit diesen Werten wäre die Lösung dann $\begin{eqnarray*} x = 2543k - 7533230, y = 5387k - 3556155 \end{eqnarray*}$ mit $\begin{eqnarray*} k \in \mathbb Z \end{eqnarray*}$ .

Was habe ich denn bei dem Algorithmus falsch gemacht?

30.01.2015, 12:47

HAL 9000

Auf diesen Beitrag antworten »

Du hast den EEA für die Gleichung

$\begin{align*} 38145x ~{\color{red}+}~ 80805y = \operatorname{ggT}(38145,80805) \end{align*}$

durchgeführt. Da bei dir aber vor der 80805 ein - steht, ist das im Ergebnis nun mal anzupassen.

30.01.2015, 14:00

brushmate

Auf diesen Beitrag antworten »

Ich habe jetzt den EEA für die Gleichung $\begin{eqnarray*} 38145x + 80805y = ggT(38145, -80805) \end{eqnarray*}$ ausgeführt. Damit erhalte ich $\begin{eqnarray*} ggT(38145, -80805) = -15 \end{eqnarray*}$ , $\begin{eqnarray*} x = 2434 \end{eqnarray*}$ , $\begin{eqnarray*} y = 1149 \end{eqnarray*}$ und die Gleichung ist erfüllt. Ist das richtig? Denn $\begin{eqnarray*} 15 \end{eqnarray*}$ teilt $\begin{eqnarray*} -80805 \end{eqnarray*}$ ja auch und $\begin{eqnarray*} -15 < 15 \end{eqnarray*}$ .

09.02.2015, 11:05

brushmate

Auf diesen Beitrag antworten »

Hallo,

es wäre wirklich nett, wenn mir hier noch einmal jemand weiterhelfen könnte.

09.02.2015, 11:30

HAL 9000

Auf diesen Beitrag antworten »

Ja was denn - es war doch alles geklärt:

Zitat:

Original von HAL 9000
Du hast den EEA für die Gleichung

$\begin{align*} 38145x ~{\color{red}+}~ 80805y = \operatorname{ggT}(38145,80805) \end{align*}$

durchgeführt. Da bei dir aber vor der 80805 ein - steht, ist das im Ergebnis nun mal anzupassen.

D.h., dein oben erzieltes Ergebnis $\begin{align*} x = -2434,y = 1149 \end{align*}$ ist eine Lösung eben jener Gleichung $\begin{align*} 38145x + 80805y = 15 \end{align*}$ .

Wenn es aber stattdessen um die Gleichung $\begin{align*} 38145x - 80805y = 15 \end{align*}$ gehen soll, dann ist lediglich das Vorzeichen der y-Lösung zu drehen, d.h. es ist $\begin{align*} x = -2434,y = -1149 \end{align*}$ eine mögliche Lösung dieser Gleichung - fertig.

P.S.: Du wendest den EEA anscheinend auch für negative Zahlen an. Bin mir jetzt nicht ganz sicher, ob das in allen Fällen gutgeht, ist zumindest etwas ungewöhnlich. verwirrt

Neue Frage »

Antworten »

Wie finde ich die ganzzahligen Lösungen einer diophantischen Gleichung?

Verwandte Themen