Finden Sie eine ganzzahlige Lösung x, y von 75x + 38y = 1

Question

kann mir bitte jemand erklären wie diese Aufgabe funktioniert?

Finden Sie eine ganzzahlige Lösung x, y von 75x + 38y = 1

Dankeschön.

PS. Geben Sie jeweils alle Rechenschritte an und begründen Sie Ihre Antwort.

Answer 1

75*(-1) + 38*2 = 1                      

(In dieser Form ist das eine Kopfrechenaufgabe und es ist weiter ersichtlich, dass hieraus auch eine Lösung für deine andere Aufgabe abgeleitet werden kann.)

Answer 2

Nach y auflösen liefert y = - (75x - 1) / 38.

Damit y bei ganzahligem x ganzzahlig ist, muss 75x-1 ≡ 0 mod 38 sein.

Löse diese Kongruenz.

Answer 3

http://www.arndt-bruenner.de/mathe/scripts/diophant.htm

Es soll die diophantische Gleichung  75x + 38y = 1  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:

     38y = 1 - 75x

          1 - 75x

     y = —————————

             38

Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen

Koeffizienten und den Rest zerlegt:

                1 - 37x

     y = -x +  —————————

                   38

Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.

Der ganzzahlige Parameter a wird eingeführt und dem Bruch gleichgesetzt:

          1 - 37x

     a = —————————

             38

     38a = 1 - 37x

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

     37x = 1 - 38a

          1 - 38a

     x = —————————

             37

Nun wird der Bruch durch komponentenweise Division mit Rest in einen Teil mit ganzzahligen

Koeffizienten und den Rest zerlegt:

                1 - a

     x = -a +  ———————

                  37

Da alle anderen Summanden ganzzahlig sind, muß auch der Restbruch ganzzahlig sein.

Der ganzzahlige Parameter b wird eingeführt und dem Bruch gleichgesetzt:

          1 - a

     b = ———————

            37

     37b = 1 - a

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

     a = 1 - 37b

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 x:

          1 - 38a       1 - 38·(1 - 37b)

   x  =  —————————  =  ——————————————————  =  -1 + 38b

             37                37

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

          1 - 75x       1 - 75·(-1 + 38b)

   y  =  —————————  =  ———————————————————  =  2 - 75b

             38                 38

Damit hängen alle Variablen nur noch von freien Parametern ab, die unabhängig

voneinander die Menge der ganzen Zahlen durchlaufen können:

     x = -1 + 38b

     y = 2 - 75b