Diophantische Gleichung lösen

30.07.2022, 11:19

Guss123

Diophantische Gleichung lösen

Hallo,

ich habe die Diophantische Gleichung gegeben:

11x +26y = 3

Mein Ansatz zur Lösung sieht nun so aus:

11x = 3 mod 26

Das kann man einmal durchprobieren und erhält dann x = 5 mod 26 als Lösung, was dann x = 26n +5 entspricht, wobei $\begin{eqnarray*} n \in \mathbb{Z} \end{eqnarray*}$ ist.

Mein Ansatz für den zweiten Teil sieht nun so aus:

26y = 3 mod 11

Auch hier habe ich etwas durchprobiert und erhalte als Lösung y = 9 mod 11, was dann y = 11n + 9 entspricht, wobei $\begin{eqnarray*} n \in \mathbb{Z} \end{eqnarray*}$ ist.

Jetzt sieht man hier relativ gut, dass dann:
11x +26y = 3 --> 11(26n +5) +26(11n + 9) = 3
so nicht passen kann d.h. ich habe irgendwo einen Fehler gemacht.

Ich habe dann folgendes versucht (*1*):
11x +26y = 3, mit x = 26n +5 eingesetzt, erhält man dann y = -11n -2

Jetzt sieht man hier relativ gut, dass dann:
11x +26y = 3 --> 11(26n +5) +26(-11n -2) = 3
für n=1, schon mal passt!

Es ergeben sich jetzt einige Fragen für mich:
1.) Warum komme ich nicht auf Anhieb auf die zweite Lösung (y = -11n -2) durch meinen Ansatz 26y = 3 mod 11 durch versuchen zu lösen, ähnlich wie ich es gleich zu Anfang gemacht habe? (Es scheint also besser zu sein eine Lösung einfach in die Gleichung einzusetzen, wie ich es in *1* gemacht habe...)

2.) Ich habe angenommen, dass x = 26n +5 für den ersten Ansatz richtig ist, es könnte aber auch sein, dass y = 11n + 9 richtig ist, setze ich das in die Gleichung ein 11x +26y = 3 und löse auf, so erhalte ich x = -26n -21... Wie entscheidet man sich hier?

3.) Wie würde man das ohne probieren lösen? Euklidischer Algorithmus?!

Danke für aufkommende Antworten! smile

30.07.2022, 12:11

Mathema

Auf diesen Beitrag antworten »

Ich kann was zu 3) sagen. Das läuft über den erweiterten euklidischen Algorithmus:

$\begin{eqnarray*} 26=2\cdot 11+4 \end{eqnarray*}$

$\begin{eqnarray*} 11=4\cdot 2+3 \end{eqnarray*}$

$\begin{eqnarray*} 4=3\cdot 1+1 \end{eqnarray*}$

Und nun rückwärts:

$\begin{eqnarray*} 1=4-3=4-(11-4\cdot 2)=-11+3\cdot 4=-11+3(26-2\cdot 11)=-7\cdot 11+3\cdot 26 \end{eqnarray*}$

Multiplizieren wir die Gleichung mit $\begin{eqnarray*} 3 \end{eqnarray*}$ erhalten wir also $\begin{eqnarray*} -21\cdot 11+9\cdot 26=3 \end{eqnarray*}$ und somit die speziellen Lösungen $\begin{eqnarray*} x_0=-21 \end{eqnarray*}$ und $\begin{eqnarray*} y_0=9 \end{eqnarray*}$ . Die allgemeinen Lösungen lauten dann $\begin{eqnarray*} x=-21+26k \end{eqnarray*}$ und $\begin{eqnarray*} y=9-11k \end{eqnarray*}$ für $\begin{eqnarray*} k \in \mathbb{Z} \end{eqnarray*}$ .

30.07.2022, 13:49

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Guss123
Jetzt sieht man hier relativ gut, dass dann:
11x +26y = 3 --> 11(26n +5) +26(11n + 9) = 3
so nicht passen kann d.h. ich habe irgendwo einen Fehler gemacht.

Der Fehler ist, dass du nicht dasselbe $\begin{eqnarray*} n \end{eqnarray*}$ für beide Lösungen nehmen kannst!!! Du hast $\begin{eqnarray*} x=26n+5 \end{eqnarray*}$ sowie $\begin{eqnarray*} y=11m+9 \end{eqnarray*}$ mit einander gekoppelten (aber nicht gleichen!) ganzen Zahlen $\begin{eqnarray*} n,m \end{eqnarray*}$ .

Wie du dann später auch gesehen hast, ist diese Kopplung nun gerade $\begin{eqnarray*} m=-n-1 \end{eqnarray*}$ .

30.07.2022, 15:34

adder

Auf diesen Beitrag antworten »

Zitat:

Jetzt sieht man hier relativ gut, dass dann:
11x +26y = 3 --> 11(26n +5) +26(-11n -2) = 3
für n=1, schon mal passt!

Nicht nur für n=1 sondern für alle n, denn das n fällt weg, wodurch die Gleichung 3=3 unabhängig von n immer wahr ist.

Modulo 11 (verglichen mit 26 erstmal umgänglicher) führt die Gleichung 11x+26y=3 direkt zu $\begin{eqnarray*} 4y \equiv 3 \end{eqnarray*}$ was die Zahlen überschaubar klein und $\begin{eqnarray*} y \equiv 9 \equiv -2 \end{eqnarray*}$ relativ leicht einsehbar macht.

Ansonsten könnte man für $\begin{eqnarray*} ax+by=c \end{eqnarray*}$ hier im Beispiel auch direkt sowas wie $\begin{eqnarray*} 11x+26y=3=55-52=11 \cdot 5-26 \cdot 2 \end{eqnarray*}$ sehen und hat damit schon mal mit $\begin{eqnarray*} x_p=5 \ ~ \text{und} \ ~ y_p=-2 \end{eqnarray*}$ eine spezielle Lösung gefunden und die Menge aller Lösungen folgt dann durch $\begin{eqnarray*} x=x_p \pm bk \ ~ \text{und} \ ~ y=y_p \mp ak \end{eqnarray*}$ für alle ganzen Zahlen k.
Dass das stimmt, zeigt sich durch Einsetzen :

$\begin{eqnarray*} a \cdot (x_p \pm bk)+b \cdot(y_p \mp ak)=a \cdot x_p+b \cdot y_p \pm abk \mp bak=c+0=c \ ~ \ \checkmark \end{eqnarray*}$

Neue Frage »

Antworten »

Diophantische Gleichung lösen

Verwandte Themen