Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Euklidischer Algorithmus

Euklidischer Algorithmus

Schüler Mittlere u. höhere Anstalten der Lehrer- u. Erzieherbildung, 5. Klassenstufe

Tags: Euklid Algorithmus, Gleichungen

Composer

11:22 Uhr, 20.11.2009

Hallo,

Ich versuche gerade ein Beispiel zu checken, aber komme einfach nicht weiter.
Ich habe zwar die Lösung

(x = 9, y = - 11),

aber ich weiß nicht, wie man auf sowas kommt.
Kann mir bitte jemand weiterhelfen? Danke!!

Das Beispiel wäre:
Man bestimme alle ganzen Zahlen

x, y,

welche die Gleichung

243 \cdot x + 198 \cdot y = 9

erfüllen.

mfg,
Composer

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

arrow30

14:33 Uhr, 20.11.2009

erstmal man berechnet den ggt(243,198)
Euklidischer Algorithmus :

243 = 198 \cdot 1 + 45

198 = 45 \cdot 4 + 18

45 = 18 \cdot 2 + 9

18 = 9 \cdot 2 + 0

damit ist ggt(243,198)=9 und die 9 teilt die 9 also jetzt vereinfachen wir die Gleichung zu

27 \cdot x + 22 \cdot y = 1

Euklidischer Algorithmus noch mal :

27 = 22 \cdot 1 + 5

22 = 4 \cdot 5 + 2

5 = 2 \cdot 2 + 1

2 = 2 \cdot 1 + 0

\to

ggt(27,22)=1
nun

1 = 5 - 2 \cdot 2

2 = 22 - 4 \cdot 5

5 = 27 - 22 \cdot 1

1 = 27 - 22 \cdot 1 - 2 (22 - 4 \cdot 5)) = 27 - 22 \cdot 1 - 2 \cdot (22 - 4 \cdot (27 - 22 \cdot 1)

1 = 27 - 22 \cdot 1 - 2 \cdot 22 + 8 \cdot 27 - 8 \cdot 22

1 = 27 \cdot 9 + 22 \cdot (- 11) \mapsto (X_{0}, Y_{0}) = (9, - 11)

arrow30

14:44 Uhr, 20.11.2009

und die gesamte Lösungsmenge ist

: (X, Y) = (9 + k \cdot 22, - 11 - k \cdot 27)

mit

k

eine ganze Zahl

Composer

18:20 Uhr, 20.11.2009

danke für die schnelle antwort!
leider checke ich den letzten und vorletzten schritt vom ersten post nicht.

: (

wäre nett, wenn du mir weiterhelfen könntest.

mfg,
Hermi

arrow30

18:38 Uhr, 20.11.2009

27 \cdot x + 22 \cdot y = 1

ggt(27,22) mit dem Euklidischen Algorithmus bestimmen:

27 = 22 \cdot 1 + 5

22 = 4 \cdot 5 + 2

5 = 2 \cdot 2 + 1

2 = 2 \cdot 1 + 0 \to

ggt(27,22)=1
nun aus dem Euk. Algorithmus von oben (rückwärts )
ist
I->

1 = 5 - 2 \cdot 2

II->

2 = 22 - 4 \cdot 5

III->

5 = 27 - 22 \cdot 1

nun setzt man

2 = 22 - 4 \cdot 5

dieses in I dann hat man folgende Gleichung:

IV

\to 1 = 5 - 2 \cdot (22 - 4 \cdot 5) \Leftrightarrow 1 = 5 - 2 \cdot 22 + 8 \cdot 5 \Leftrightarrow 1 = 9 \cdot 5 - 2 \cdot 22

aus III wissen wir

5 = 27 - 22 \cdot 1

das setzen wir in IV ein

1 = 9 \cdot (27 - 22 \cdot 1) - 2 \cdot 22

also

1 = 9 \cdot 27 - 9 \cdot 22 - 2 \cdot 22

oderr

1 = 9 \cdot 27 - 11 \cdot 22 \to 27 \cdot x + 22 \cdot y = 1

dann ist

(x_{0}, y_{0}) = (9, - 11)

Composer

16:20 Uhr, 21.11.2009

vielen dank!! deine erklärung hat mich weitergebracht. :-)

mfg,
Hermi

Composer

17:19 Uhr, 21.11.2009

zu früh gefreut. den allerletzten schritt checke ich doch nicht, wie ich mir gedacht habe.

wie kommst du von hier: 1=9*27-9*22-2⋅22 auf sowas:

1 = 9 \cdot 27 - 11 \cdot 22 \to 27 \cdot x + 22 \cdot y = 1

dann ist (x0,y0)=(9,-11)??

arrow30

17:23 Uhr, 21.11.2009

meinst du diesen Schritt ?

1 = 9 \cdot 27 - 11 \cdot 22 \to 27 \cdot x + 22 \cdot y = 1

dann ist

(x_{0}, y_{0}) = (9, - 11)

Antwort ist koeffizientenvergleich

Composer

17:24 Uhr, 21.11.2009

ich meine die ganze letzte zeile.

arrow30

17:27 Uhr, 21.11.2009

1 = 9 \cdot 27 - 9 \cdot 22 - 2 \cdot 22

oder

1 = 9 \cdot 27 - 11 \cdot 22

naja wäre

a = 22

dann würde da folgendes stehen :

1 = 9 \cdot 27 - 9 \cdot a - 2 \cdot a \to 1 = 9 \cdot 27 - 11 \cdot a

Composer

17:38 Uhr, 21.11.2009

danke nochmals für die erklärung!
schönen abend noch!

lg Hermi

Composer

18:44 Uhr, 22.11.2009

Hi nochmals,

tut mir leid, dass ich dich wieder störe.
Ich habe nun dasselbe beispiel, aber mit anderen zahlen zu lösen versucht, aber ich komme hier nicht zu einem lösungsweg.

Ich bin mir nicht sicher, ob ich im selben thread wieder schreiben soll oder einen neuen öffnen soll, daher entschuldige ich mich schon vorher, falls ich etwas falsches getan haben sollte.

Das beispiel sieht folgendermaßen aus:

561 x + 154 y = 11

Habe zuerst den ggt(554,

154)

berechnet:

561 = 154 \cdot 3 + 99

154 = 99 \cdot 1 + 55

99 = 55 \cdot 1 + 44

55 = 44 \cdot 1 + 11

44 = 11 \cdot 4 + 0

Damit das ggt(561,

154) = 11

Nun

561 x + 154 y = 11 | : 11

51 x + 14 y = 1 \to

neue Gleichung

EA nochmals:

51 = 14 \cdot 3 + 9

14 = 9 \cdot 1 + 5

9 = 5 \cdot 1 + 4

5 = 4 \cdot 1 + 1

4 = 1 \cdot 4 + 0

Nun rückwärts berechnen:
I:

1 = 5 - 4 \cdot 1

II:

4 = 9 - 5 \cdot 1

III:

5 = 14 - 9 \cdot 1

IV:

9 = 51 - 14 \cdot 3

Nun setzt man II in I ein, wo die Zahl 4 steht:

1 = 5 - 1 \cdot (9 - 5 \cdot 1) \to 1 = 5 - 1 \cdot 9 + 5 \cdot 1 \to 1 = 2 \cdot 5 - 1 \cdot 9 - - - -

statt

5,

III einsetzen:

1 = 2 \cdot (14 - 9 \cdot 1) - 1 \cdot 9 \to 1 = 2 \cdot 14 - 2 \cdot 9 - 1 \cdot 9

wieder dasselbe spiel...

1 = 2 \cdot 14 - 2 \cdot (51 - 14 \cdot 3) - 1 \cdot 9 - - - -

ab hier weiß ich nicht mehr, wie ich weitermachen soll.
habe ich etwas falsch gemacht?

arrow30

18:51 Uhr, 22.11.2009

1 = 2 \cdot 14 - 2 \cdot 9 - 1 \cdot 9 \to 1 = 2 \cdot 14 - 3 \cdot 9

⋆

du hast also nichts falsches gemacht die

- 1 \cdot 9

kannst du auch mit den anderen Zahlen darstellen :-)

Composer

19:19 Uhr, 22.11.2009

ah...da bin ich aber froh :-)

1 = 2 \cdot 14 - 3 \cdot 9

1 = 2 \cdot 14 - 3 \cdot (51 - 14 \cdot 3) \to 1 = 2 \cdot 14 - 3 \cdot 51 - 14 \cdot 9

ab hier verstehe ich nimmer, wie ich den

x

und

y

zusammenfassen soll.

x = - 17 y =

arrow30

19:24 Uhr, 22.11.2009

1 = 2 \cdot 14 - 3 \cdot (51 - 14 \cdot 3)

→

1 = 2 \cdot 14 - 3 \cdot 51 + 14 \cdot 9

(minus mal minus ergibt immer plus)
und

2 \cdot 14 + 9 \cdot 14 = (2 + 9) \cdot 14 = 11 \cdot 14

also

1 = 11 \cdot 14 - 3 \cdot 51

Composer

19:27 Uhr, 22.11.2009

das mit dem minus habe ich voll vergessen. herzlichen dank! :-)

mfg,
Hermi

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

683004

681524

	Status: nicht eingeloggt	Noch nicht registriert?