Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Lineare Diophantische Gleichung
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Community-Forum -> Lineare Diophantische Gleichung
 
Autor Nachricht
Sören
Gast






BeitragVerfasst am: 15 Feb 2005 - 20:32:18    Titel: Lineare Diophantische Gleichung

Hallo!

Ich habe folgende LDG zu lösen:

228x+86y=74

Lösungsweg: Entweder Euklischer Algorithmus oder Modulo.

Komme aber bei beiden Wegen nicht weiter.

Einzig das Lösbarkeitskriterium hab ich geschafft. 2 teilt 74.

Wäre nett, wenn mir jemand zumindest einen Lösungsweg ausführlich aufschreiben könnte. Wäre sehr nett!!!

Gruß Sören
jens
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 08.02.2005
Beiträge: 44

BeitragVerfasst am: 16 Feb 2005 - 15:04:00    Titel:

Es soll die diophantische Gleichung 228x + 86y = 74 gelöst werden.

Das von Euler entwickelte Verfahren ist eng verwandt mit dem euklidischen Algorithmus.
Man betrachtet nur die jeweiligen Reste bei der Division durch einen der Koeffizienten,
geeigneterweise den mit dem kleinsten Betrag, und reduziert die Reste dadurch solange,
bis nur noch ein ganzzahliger Rest bleibt.

Die Variable mit dem kleinsten Koeffizienten ist y. Die Gleichung wird nach y umgeformt:

86y = 74 - 228x

74 - 228x
y = ———————————
86

Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:

74 - 56x
y = -2x + ——————————
86

Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.
Der ganzzahlige Parameter a wird eingeführt und dem Bruch gleichgesetzt:

74 - 56x
a = ——————————
86

86a = 74 - 56x


Die Variable mit dem kleinsten Koeffizienten ist x. Die Gleichung wird nach x umgeformt:

56x = 74 - 86a

74 - 86a
x = ——————————
56

Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:

18 - 30a
x = 1 - a + ——————————
56

Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.
Der ganzzahlige Parameter b wird eingeführt und dem Bruch gleichgesetzt:

18 - 30a
b = ——————————
56

56b = 18 - 30a


Die Variable mit dem kleinsten Koeffizienten ist a. Die Gleichung wird nach a umgeformt:

30a = 18 - 56b

18 - 56b
a = ——————————
30

Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:

18 - 26b
a = -b + ——————————
30

Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.
Der ganzzahlige Parameter c wird eingeführt und dem Bruch gleichgesetzt:

18 - 26b
c = ——————————
30

30c = 18 - 26b


Die Variable mit dem kleinsten Koeffizienten ist b. Die Gleichung wird nach b umgeformt:

26b = 18 - 30c

18 - 30c
b = ——————————
26

Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:

18 - 4c
b = -c + —————————
26

Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.
Der ganzzahlige Parameter d wird eingeführt und dem Bruch gleichgesetzt:

18 - 4c
d = —————————
26

26d = 18 - 4c


Die Variable mit dem kleinsten Koeffizienten ist c. Die Gleichung wird nach c umgeformt:

4c = 18 - 26d

18 - 26d
c = ——————————
4

Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen
Koeffizienten und den Rest zerlegt:

2 - 2d
c = 4 - 6d + ————————
4

Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.
Der ganzzahlige Parameter e wird eingeführt und dem Bruch gleichgesetzt:

2 - 2d
e = ————————
4

4e = 2 - 2d


Die Variable mit dem kleinsten Koeffizienten ist d. Die Gleichung wird nach d umgeformt:

2d = 2 - 4e

2 - 4e
d = ————————
2

d = 1 - 2e

Nun ist auf der rechten Seite der Gleichung kein Bruch und keine der Variablen mehr
enthalten. Durch Einsetzen in umgekehrter Reihenfolge werden nun in allen Gleichungen,
in denen eine Variable isoliert wurde, die anderen Variablen eliminiert.

Eliminiere die Unbekannte(n) durch Einsetzen in die Gleichung für c:


18 - 26d 18 - 26·(1 - 2e)
c = —————————— = —————————————————— = -2 + 13e
4 4


Eliminiere die Unbekannte(n) durch Einsetzen in die Gleichung für b:


18 - 30c 18 - 30·(-2 + 13e)
b = —————————— = ———————————————————— = 3 - 15e
26 26


Eliminiere die Unbekannte(n) durch Einsetzen in die Gleichung für a:


18 - 56b 18 - 56·(3 - 15e)
a = —————————— = ——————————————————— = -5 + 28e
30 30


Eliminiere die Unbekannte(n) durch Einsetzen in die Gleichung für x:


74 - 86a 74 - 86·(-5 + 28e)
x = —————————— = ———————————————————— = 9 - 43e
56 56


Eliminiere die Unbekannte(n) durch Einsetzen in die Gleichung für y:


74 - 228x 74 - 228·(9 - 43e)
y = ——————————— = ———————————————————— = -23 + 114e
86 86



Damit hängen alle Variablen nur noch von freien Parametern ab, die unabhängig
voneinander die Menge der ganzen Zahlen durchlaufen können:

x = 9 - 43e
y = -23 + 114e
matetex
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 16.06.2018
Beiträge: 1

BeitragVerfasst am: 16 Jun 2018 - 23:43:17    Titel:

Es gibt auch einen Online-Rechner, der lineare diophantische Gleichungen per EEA löst. Also ein adnerer Lösungsweg als im vorherigen Post. Die Frage ist zwar schon älter, aber vielleicht hilft es noch jemand anderem.

Lösung für diese Gleichung: http://uni-module.de/algorithmen/lineare-diophantische-gleichung-mit-eea?a=228&b=82&c=74 (mit Rechenweg, auch vom euklidischen Algorithmus).
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Community-Forum -> Lineare Diophantische Gleichung
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum