Wie ermittle ich ganzzahlige Lösungen für eine diophantische Gleichung? (außer ausprobieren)

Aufrufe: 416     Aktiv: 27.01.2021 um 16:13
0

Zunächst überprüfe ich, ob es überhaupt ganzz. Lösungen gibt, indem ich gucke ob der GGT auch das Ergebniss der Gleichung teilt. Soweit easy!

z.B:  72x-44y=124

 

Mit Euklid ermittelt: ggT(72,44)=4   , die 4 teilt 124, also gibt es ganzz. Lösungen.

Bei einfachen Gleichungen, ist es jetzt easy x und y einfach durch überlegen rauszufinden. Aber was ist meine andere Option? Ich hab düster was im Kopf mit Euklid Rückwärts, kann mir da jemand weiterhelfen? Habe leider kein verständliches Lehrvideo gefunden, evtl kann mir das jemand anhand dieses recht einfachen Beispiels erklären.

 

 

 

Diese Frage melden
gefragt

Punkte: 14

 
Kommentar schreiben
1 Antwort
1

Für den euklidischen Algorithmus rechnest du ja \begin{align*}72&=1\cdot 44+28,\\44&=1\cdot28+16,\\28&=1\cdot16+12,\\16&=1\cdot 12+4,\\12&=3\cdot 4.\end{align*}

Jetzt setzt du das rückwärts wieder ein: \begin{align*}4&=16-12\\&=16-(28-16)\\&=2\cdot16-28\\&=2(44-28)-28\\&=2\cdot44-3\cdot28\\&=2\cdot44-3(72-44)\\&=5\cdot44-3\cdot72\end{align*}

Das ist der sogenannte Erweiterte Euklidische Algorithmus. So kannst du zu gegebenen \(x,y\) immer \(a,b\) finden, sodass \(ax+by=ggt(x,y)\) gilt. Jetzt musst du diese Gleichung nur noch passend erweitern (hier mit \(124/4=31\)), um auf eine Lösung deiner Originalgleichung zu kommen.

Diese Antwort melden
geantwortet

Punkte: 11.27K

 
Vielen Dank, das war sehr hilfreich! Ich habs jetzt bei paar Aufgaben ausprobiert und der erweiterte Euklid ist soweit klar. Das einzige was mir noch ein wenig unklar ist: Nach dem erweitern steht ja: 124 = 155 * 44 - 93 * 72

wieso sind mein x und y jetzt (laut lösung) -93 und -155? Muss ich einfach die positiven und negativen Werte ausprobieren für meine gleichung oben?
  ─   sonti 27.01.2021 um 16:06

Kommentar schreiben