Diophantische Gleichung mit Hilfe von Kongruenzrechnen lösen

Neue Frage »

Mathemuppi Auf diesen Beitrag antworten »
Diophantische Gleichung mit Hilfe von Kongruenzrechnen lösen
Meine Frage:
Hallo zusammen,
Folgende Aufgabe ist zu lösen:
"Lösen Sie die diophantische Gleichung 9x+16y=2".


Meine Ideen:
Also:
1. Existenz einer Lösung?
Berechnung des ggT(9,16) mit Hilfe des Euklidischen Algorithmus ergibt 1. Wenn ggT(a,b) | c dann existieren ganzzahlige Lösungen für die Gleichung. In diesem Fall: 1 | 2 und somit ist die Gleichung lösbar.

2. Bestimmung der Lösungen:
Den Rechenweg über den Euklidischen Algorithmus rückwärts und am Ende einsetzen in die Lösungsgleichung: L={(x0+(b|ggT(a,b))*t; yo-(a|ggT(a,b))*t | t element von Z)} kenne ich, jedoch sollen wir den nicht anwenden sondern die Gleichung mit Hilf von Kongruenzrechnung lösen.

Das würde folgende Folgerungskette bedeuten:

Es gilt weiter 9x+16y=2

--> (9|1)x + (16|1)y = 2|1
:ggT

--> 9x + 16y = 2

--> 9x = 2 - 16y
nach
x auf.

--> 9 | 2 - 16y
Def.
Teiler

--> 2 ? 16y (mod 9)
Def.
Kongruenz

Ab dieser Stelle besteht das Problem.
Ich bin mir bewusst, dass ich die Gleichung nach x und y auflösen muss um eine Lösung zu bekommen. Wie rechne ich jetzt weiter?

Folgende Überlegungen:
--> 2 | 16 ? y (mod 9)
:16

--> y = ???
Wie lese ich jetzt y ab und kann ich einfach mit die 2 durch 16 dividieren?

Leider stellt sich bei mir bei jedem Lösen von Diophantischen Gleichungen immer bei diesem Schritt das Problem!! Mit dem Euklid rückwärts ist das kein Problem dafür bekomme ich werte für x= -14 und y= 8 Also L1(-14|8).

Vielen Dank smile
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mathemuppi
Leider stellt sich bei mir bei jedem Lösen von Diophantischen Gleichungen immer bei diesem Schritt das Problem!! Mit dem Euklid rückwärts ist das kein Problem dafür bekomme ich werte für x= -14 und y= 8 Also L1(-14|8).

Na dann nimm doch Euklid. Wenn dir das bei so kleinen Modulen als zu aufwändig erscheint, dann ist "Probieren" auch eine gute Wahl (auch wenn manche dabei die Nase rümpfen): Bei die nur neun möglichen Varianten für hier durchzuprobieren ist ja wohl nicht die Welt. Augenzwinkern

Schneller geht's natürlich, wenn man erkennt, dass man die Gleichung auch als schreiben kann.
Mathemuppi Auf diesen Beitrag antworten »

Hallo @HAL 9000

Lieben Dank für deine schnelle Antwort.
Leider wird beim Bearbeiten dieser Aufgabe nur das Kongruenzrechnen erwartet, somit kann ich die Aufagbe leider nicht mit dem Euklidischen Algorithmus lösen.
Ich muss also verstehen wieso und besonders wie man weiter folgert um am End auf die Lösung zu kommen.

Meine Frage ist also. Ist deine Kongruent "7y kongruent zu 2 mod 9" ein Beispiel oder der nächste Schritt in meiner Rechnung.

Wie komme ich denn jetzt weiter meine Aufgabe muss ich ja nach y auflösen um sie dann in x einzusetzen. Dann kann ich ja Lösungen erhalten.
Wäre es möglich mir innerhalb meiner oben aufgeführten Kongruenzrechnung weiter zu helfen? oder ist diese schon falsch.

Viele Grüße

Wink
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mathemuppi
Meine Frage ist also. Ist deine Kongruent "7y kongruent zu 2 mod 9" ein Beispiel oder der nächste Schritt in meiner Rechnung.

Ich dachte, das wäre klar: Wenn man die Gleichung modulo 9 betrachtet, kommt doch die genannte Kongruenz raus.

Und nochmal: Die Zeit, in der du hier lang und breit debattierst, wie man das denn irgendwie lösen könnte (vielleicht fällt auch noch das Wort "rechnerisch"), hättest du längst die 9 Varianten y=0,1,...,8 durchprobieren können.


Zitat:
Original von Mathemuppi
Wäre es möglich mir innerhalb meiner oben aufgeführten Kongruenzrechnung weiter zu helfen? oder ist diese schon falsch.

Sie ist wegen der seltsamen Fragezeichen unzumutbar zu lesen. Wenn du willst, dass die jemand liest, darfst du das nicht so achtlos "hinkippen".
Mathemuppi Auf diesen Beitrag antworten »

Ok den ersten Teil deiner Nahricht habe ich verstanden. Durch Einsetzen von y = ...

Zum zweiten Teil deiner Nachricht. Die Fragezeichen sollen Das Kongreunzzeichen darstellen. Auf meinem Rechner ist das auch so zu erkennen (mit der zeichentabelle von Word eines Macs eingefügt. Anscheinend ist das Zeichen aber nicht immer zu erkennen - wie ich gerade von einem anderem PC aus sehe. Ich werde die Rechnung noch einmal anhängen in der Hoffnung dass es diesmal klappt.
Mathemuppi Auf diesen Beitrag antworten »

1. Existenz einer Lösung?
Berechnung des ggT(9,16) mit Hilfe des Euklidischen Algorithmus ergibt 1. Wenn ggT(a,b) | c dann existieren ganzzahlige Lösungen für die Gleichung. In diesem Fall: 1 | 2 und somit ist die Gleichung lösbar.

2. Bestimmung der Lösungen:
Den Rechenweg über den Euklidischen Algorithmus rückwärts und am Ende einsetzen in die Lösungsgleichung: L={(x0+*t; yo-*t | t Element von Z)} kenne ich, jedoch sollen wir den nicht anwenden sondern die Gleichung mit Hilf von Kongruenzrechnung lösen.

Das würde folgende Folgerungskette bedeuten:

Es gilt weiter 9x+16y=2

--> x + y =
:ggT

--> 9x + 16y = 2

--> 9x = 2 - 16y
nach
x auf.

--> 9 | 2 - 16y
Def.
Teiler

--> 2 16y (mod 9)
Def.
Kongruenz

Ab dieser Stelle besteht das Problem.
Ich bin mir bewusst, dass ich die Gleichung nach x und y auflösen muss um eine Lösung zu bekommen. Wie rechne ich jetzt weiter?

Folgende Überlegungen:
--> y (mod 9)
:16

--> y = ???


Wie gebe ich jetzt y in Angängigkeit von x an um dies dann wieder in die Gleichung einzusetzen.
 
 
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mathemuppi
Anscheinend ist das Zeichen aber nicht immer zu erkennen

Ersetzen wr das "nicht immer" durch "nie", jedenfalls nicht mit ASCII, und anderes sollte im Editor-Fenster auch nicht benutzt werden. unglücklich

Zitat:
Original von Mathemuppi
--> 2 16y (mod 9)

Genau, diese Kongruenz ist zu lösen. Und am einfachsten wie ich oben gesagt habe: Probieren - sofern du nicht das oben bereits erwähnte erkennst, was sofort zur Lösung führt.
Mathemuppi Auf diesen Beitrag antworten »

Danke.
Siehst du das einfach so dass man die kongruenz auch so schreiben kann oder hast du eine folgerungsbegrünDung. Also hast du ein Gesetz angewendet dass aus 2 kongruent zu 16y modulo 9 bei dir 7 y kongruent zu 2 modulo 9 und am ende -2 kongruent zu 2 modulo Neun und dann y = -1 modulo 9 ist. Welche Gesetze wendest du an?

Leier schreibe ich gerade mit dem Handy und kann die Zeichen nicht emühen. Mir ist es wirklich nicht ersichtlich wie du die Schritte folgerSt.
Mathemuppi Auf diesen Beitrag antworten »

Hallo,

Habe den Zusammenhang verstanden zwischen den Schritten.
Keine weitere Hilfe notwendig. Danke für den Ansatz smile

Lieben Gruß
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »