0 Daumen
904 Aufrufe
(Alle Zahlen sind relativ prim. Gibt es einen einfach weg an die LΓΆsung zu kommen, ohne ca 30 mal + 317 zu rechnen?
Avatar von

2 Antworten

0 Daumen

Wir bestimmen zunΓ€chst das Inverse zu \(84\) modulo \(317\).

Da ggT\((84,317)=1\) ist, kann man den euklidischen Algorithmus auf das Paar \(84,317\)
anwenden und erhΓ€lt

\(117\cdot 84-31\cdot 317=1\), d.h.
\(84\cdot z\equiv 1\) mod \(317\) hat als LΓΆsung \(z\equiv 117\) mod \(317\).

Damit ist \(x\equiv 61\cdot 117\equiv 163\) mod \(317\).

Avatar von 29 k
0 Daumen

Ich habe hier http://www.arndt-bruenner.de/mathe/scripts/diophant.htm benutzt.

Es soll die diophantische Gleichung  84x - 317y = 61  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 x. Die Gleichung wird nach x umgeformt:

  84x = 61 + 317y

        61 + 317y
  x = β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
            84

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

              61 + 65y
  x = 3y +  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
                84

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

        61 + 65y
  a = β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
          84

  84a = 61 + 65y


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

  65y = -61 + 84a

        -61 + 84a
  y = β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
            65

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

            -61 + 19a
  y = a +  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
                65

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

        -61 + 19a
  b = β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
            65

  65b = -61 + 19a


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

  19a = 61 + 65b

        61 + 65b
  a = β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
          19

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

                  4 + 8b
  a = 3 + 3b +  β€”β€”β€”β€”β€”β€”β€”β€”
                    19

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

        4 + 8b
  c = β€”β€”β€”β€”β€”β€”β€”β€”
          19

  19c = 4 + 8b


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

  8b = -4 + 19c

        -4 + 19c
  b = β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”
            8

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

              -4 + 3c
  b = 2c +  β€”β€”β€”β€”β€”β€”β€”β€”β€”
                8

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

        -4 + 3c
  d = β€”β€”β€”β€”β€”β€”β€”β€”β€”
          8

  8d = -4 + 3c


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

  3c = 4 + 8d

        4 + 8d
  c = β€”β€”β€”β€”β€”β€”β€”β€”
          3

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

                  1 + 2d
  c = 1 + 2d +  β€”β€”β€”β€”β€”β€”β€”β€”
                    3

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

        1 + 2d
  e = β€”β€”β€”β€”β€”β€”β€”β€”
          3

  3e = 1 + 2d


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

  2d = -1 + 3e

        -1 + 3e
  d = β€”β€”β€”β€”β€”β€”β€”β€”β€”
          2

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

            -1 + e
  d = e +  β€”β€”β€”β€”β€”β€”β€”β€”
                2

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

        -1 + e
  f = β€”β€”β€”β€”β€”β€”β€”β€”
          2

  2f = -1 + e


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

  e = 1 + 2f

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


        -1 + 3e     -1 + 3Β·(1 + 2f)
d =  β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  1 + 3f
          2                2


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


        4 + 8d     4 + 8Β·(1 + 3f)
c =  β€”β€”β€”β€”β€”β€”β€”β€”  =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  4 + 8f
          3                3


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


        -4 + 19c     -4 + 19Β·(4 + 8f)
b =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  9 + 19f
            8                  8


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


        61 + 65b     61 + 65Β·(9 + 19f)
a =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  34 + 65f
          19                19


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


        -61 + 84a     -61 + 84Β·(34 + 65f)
y =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  43 + 84f
            65                  65


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


        61 + 317y     61 + 317Β·(43 + 84f)
x =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”β€”  =  163 + 317f
            84                  84



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

  x = 163 + 317f
  y = 43 + 84f





___________________________________________________________________________________________
                            Javascript von Arndt BrΓΌnner

Avatar von 493 k πŸš€

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community