Finde ganze Zahlen a,b,c derart, dass 56a+63b+72c = 1.

Question

Aufgabe:

Finde ganze Zahlen a,b,c derart, dass 56a+63b+72c = 1.

Hinweis: (56,63,72) = [(56,63),72.]

Problem/Ansatz:

Hallo, bei dieser Aufgabe weiß ich nicht wie ich anfangen soll mit dem gegebenen Hinweis.

Einfach Zahlen einsetzen für a,b,c das 1 rauskommt würde ja durch Ausprobieren gehen ist aber glaub ich nicht der richtige Weg.

Comments

Hinweis: (56,63,72) = [(56,63),72.]

Das vermutlich ggT(56,63,72) = ggT[ggT(56,63),72] bedeuten.

Answer 1

56a + 63b + 72c = 1

Das ist eine lineare diophantische Gleichung. Du kannst wie unter http://www.arndt-bruenner.de/mathe/scripts/diophant.htm vorgemacht vorgehen

Es soll die diophantische Gleichung 56a + 63b + 72c = 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 a. Die Gleichung wird nach a umgeformt:

  56a = 1 - 63b - 72c

        1 - 63b - 72c
  a = ———————————————
              56

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

                  1 - 7b - 16c
  a = -b - c +  ——————————————
                      56

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

        1 - 7b - 16c
  p = ——————————————
            56

  56p = 1 - 7b - 16c


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

  7b = 1 - 16c - 56p

        1 - 16c - 56p
  b = ———————————————
              7

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

                    1 - 2c
  b = -2c - 8p +  ————————
                      7

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

        1 - 2c
  q = ————————
          7

  7q = 1 - 2c


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

  2c = 1 - 7q

        1 - 7q
  c = ————————
          2

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

              1 - q
  c = -3q +  ———————
                2

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

        1 - q
  r = ———————
          2

  2r = 1 - q


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

  q = 1 - 2r

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:


        1 - 7q     1 - 7·(1 - 2r)
c =  ————————  =  ————————————————  =  -3 + 7r
          2                2


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


        1 - 16c - 56p     1 - 16·(-3 + 7r) - 56p
b =  ———————————————  =  ————————————————————————  =  7 - 8p - 16r
              7                      7


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


        1 - 63b - 72c     1 - 63·(7 - 8p - 16r) - 72·(-3 + 7r)
a =  ———————————————  =  ——————————————————————————————————————  =  -4 + 9p + 9r
              56                            56



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

  a = -4 + 9p + 9r
  b = 7 - 8p - 16r
  c = -3 + 7r

Du kannst also für p und r hier ganze Zahlen einsetzen und erhältst damit die Lösungen die das Gleichungssysstem erfüllen.

Answer 2

Für alle $x,y\in \mathbb{Z}$ gibt es $\alpha, \beta \in \mathbb{Z}$, so dass

        $\operatorname{ggT}(x,y) = \alpha x + \beta y$

ist. Passende $\alpha$ und $\beta$ können mit dem erweiterten euklidischen Algorithmus gefunden werden.

56a+63b+72c = 1

Es ist

        $7 = 63 - 56$

Bestimme $\operatorname{ggT}(72,7) = \alpha\cdot 72 + \beta \cdot 7$ mit dem erweiterten euklidischen Algorithmus. Wegen $\operatorname{ggT}(72,7) = 1$ ist dann

        $\alpha\cdot 72 + \beta \cdot 63 - \beta\cdot 56 = 1$.

Answer 3

"Hinguck-Methode":

Es gilt: $56=7\cdot 8, \;63=7\cdot 9,\; 72=8\cdot 9$, woraus sich sofort ergibt:

$7=7\cdot9-7\cdot 8,\; 9=8\cdot 9-7\cdot 9$.

Mit $1=4\cdot 7-3\cdot 9$ ergibt sich

$1=4\cdot(63-56)-3\cdot(72-63)=-4\cdot 56+7\cdot 63-3\cdot 72$