Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Euklidischer Algorithmus: Bestimme alle x,y für d

Euklidischer Algorithmus: Bestimme alle x,y für d

Universität / Fachhochschule

Tags: alle x, alle y, bestimmen, Diskrete Mathematik, Euklid, Euklid Algorithmus, Euklidischer Algorithmus

EmreCabber aktiv_icon

14:27 Uhr, 30.07.2017

Aufgabe a habe ich durch den Euklidischen Algorithmus lösen können, nämlich ist der ggT

= 59

.

Nun war ich bei uns in der Universität in der Mathelerngruppe und auch die Mathematiker aus den höheren Semestern konnten mir Aufgabe

2 c

und

2 b

nicht erklären. Ich weiß, dass man a für

b

und

c

braucht.

Ich würde mich über einen Löungsweg sehr freuen! Wenn es nicht zu viel verlangt ist auch wieso dieser Lösungsweg funktioniert/verwendet wird.

Mit freundlichen Grüßen

PS:

Lösung des Problems zusammen mit anderen erarbeiten (empfohlen)
Würde ich gerne machen aber da ich die Klausur zeitnah schreibe wäre ich an " Lösung des Problems mit komplettem Lösungsweg bzw. ausführlicher Beschreibung (setzt voraus, dass Du alle Deine Lösungsversuche zur Frage hinzufügst und Dich aktiv an der Problemlösung beteiligst)" sehr interessiert. Leider habe ich gar keinen Ansatz in unserem Skript sowie 6 Leute aus dem Mathematikfachbereich aus den höheren Semestern konnten mir nicht helfen..

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.)

pleindespoir aktiv_icon

15:13 Uhr, 30.07.2017

y = \frac{3 \cdot 29 x + 31}{2 \cdot 7^{2}}

pwmeyer aktiv_icon

15:42 Uhr, 30.07.2017

Hallo,

für

b)

bestimmst Du zunächst eine Lösung der gegebenen (inhomogenen) Gleichung.

Dazu stellst Du fest, dass

d = 59

(der ggT) die rechte Seite

c

teilt, Faktor

31

.

Dann bestimmt Du

x'

und

y',

so dass

a \cdot x' + b \cdot y' = d

gilt. Das geschieht durch den "umgekehrten Euklidischen Algorithmus", den Du in Literatur und WEB findest - ich wette, auch in Eurer Vorlesung.

Die multiplizierst Du dann mit

31

.

Da die Gleichung linear ist, ist die allgemeine Lösung durch die allgemeine Lösung der homogenen Gleichung gegeben plus eine Lösung der inhomogenen....

Gruß pwm

EmreCabber aktiv_icon

15:44 Uhr, 30.07.2017

Vielen herzlichen Dank euch beiden! Ich habe soweit deine Schritte vollzogen und hänge nun an dem letzten Schritt das mathematisch korrekt aufzuschreiben. Wäre es in Ordnung wenn ich die Schritte hier poste und du mir dabei hilfst im letzten Schritt es mathematisch korrekt aufzuschreiben?

michaL aktiv_icon

16:07 Uhr, 30.07.2017

Hallo,

> Nun war ich bei uns in der Universität in der Mathelerngruppe und auch die Mathematiker aus den höheren
> Semestern konnten mir Aufgabe 2c und 2b nicht erklären.

> Leider habe ich gar keinen Ansatz in unserem Skript sowie 6 Leute aus dem Mathematikfachbereich aus den
> höheren Semestern konnten mir nicht helfen..

Zunächst muss man dann wohl festhalten, dass du die falschen Leute gefragt hast. Such dir eine kompetentere Gruppe, das macht vieles einfacher!

Allerdings stellt sich mir die Frage, warum du das Skript heranziehst. Was ist mit der Mitschrift und den Übungen? So etwas wird doch üblicherweise in den Übungen mal durchge x t?!

Zur Aufgabe:
Zu b) hast du eine nach Überfliegen geeignete Anleitung von pwmeyer erhalten.
Zu c) informiere dich über den chinesischen Restsatz! (Auch so ein Standard, der weder in einer Vorlesung (über Algebra? über Zahlentheorie?) fehlen noch einem höheren Semester unbekannt sein dürfte...

Mfg Michael

PS: Du schriebst:
> Wäre es in Ordnung wenn ich die Schritte hier poste...

Unbedingt!

Mfg Michael

EmreCabber aktiv_icon

18:47 Uhr, 30.07.2017

de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

So nun habe ich diesen mal angewendet aber komme bei

t

auf

- 9,9

und danach kommen nur noch so krumme Zahlen irgendwas muss da ja falsch sein. Ich habe auch irgendwo die Formel

x - (g \cdot y)

gelesen eventuell kann hier jemand was mit anfangen?

a = 5133, b = 5782, q = 0, s = s, t = t

a = 5782, b = 5133, q = 1, s = s, t = t

a = 5133, b = 649, q = 7, s = s, t = t

a = 649, b = 590, q = 1; s = s, t = t

a = 590, b = 59, q = 10, s = s, t = t

a = 59, b = 0, q = q, s = s, t = t

soweit in Ordnung. Nun nutze ich die Formel

x = s \cdot a + t \cdot b

und setze Rückwirkend ein.

Da in der letzten Zeile

b = 0

ist nehmen wir hier für

t

einen beliebigen Wert denn 0*irgendwas

= 0

. Und für

s

nehmen wir einfach 1.

\to 59 = 59 \cdot 1 + 0 \cdot 0

a = 5133, b = 5782, q = 0, s = s, t = t

a = 5782, b = 5133, q = 1, s = s, t = t

a = 5133, b = 649, q = 7, s = s, t = t

a = 649, b = 590, q = 1; s = s, t = t

a = 590, b = 59, q = 10, s = 0, t = t

a = 59, b = 0, q = q, s = 1, t = 0

Für die vorletzte Zeile nehmen wir für

s

den Wert von

t

dadrunter usw.

\to 590 = 0 \cdot 590 + 59 \cdot t \to t = 10

a = 5133, b = 5782, q = 0, s = s, t = t

a = 5782, b = 5133, q = 1, s = s, t = t

a = 5133, b = 649, q = 7, s = s, t = t

a = 649, b = 590, q = 1; s = 10, t = t

a = 590, b = 59, q = 10, s = 0, t = 10

a = 59, b = 0, q = q, s = 1, t = 0

Nun kommt mein Problem.

649 = 10 \cdot 649 + t \cdot 590

< \to

649 = 6490 + 590 t \to t = - 9,9

- 9,9

ist aber nicht eine ganze Zahl.. Und wenn ich dann mit

- 9,9

weitermache wird es schlimmer. Kann hier jemand helfen?

michaL aktiv_icon

19:07 Uhr, 30.07.2017

Hallo,

hm, der erweiterte) euklidische Algorithmus ist korrekt ausgeführt.
Allerdings solltest du die

s = s

und

t = t

fortlassen! Das ist nicht hilfreich.

Du hast damit den euklidischen Algorithmus von oben nach unten korrekt durchgeführt und

ggT (5133, 5782) = 59

erhalten.

Das rückwärtige Einsetzen zur Ermittlung einer (partikulären) Lösung von

5133 s + 5782 t = 59

ist an dieser Stelle nicht nötig!

Ich würde nun folgendes machen, um alle Lösungen von

- 5133 x + 5782 y = 1829

(I)
zu finden:
Teile die Gleichung durch den

ggT (5133, 5782) = 59

.
Ist nämlich die rechte Seite (1829) NICHT durch

ggT (5133, 5782) = 59

teilbar, so hat (i) keine Lösungen!

Wie du aber vermutlich schon gesehen hast, ist 1829 durch 59 teilbar.
Es ergibt sich:

- 87 x + 98 y = 31

(II)

Vermutlich ist dir klar, dass

ggT (87, 98) = 1

gilt (wäre es nicht so, wäre der vorherige ggT ein entsprechendes Vielfaches von 59).
Nun gilt es, EINE Lösung von

87 x + 98 y = 1

(III)
zu finden.
Die suchst du mit dem erweiterten euklidischen Algorithmus.
Versuch den nochmal, diesmal brauchst du auch das rückwärts Einsetzen!

Mfg Michael

EmreCabber aktiv_icon

20:02 Uhr, 30.07.2017

Du rettest mir den Abend! Vielen Dank!

Habe nun raus 9·(-87)

+

8·98

= 1

Meine Gleichung will ja

- 87 \times + 98 y = 31

heißt ich rechne

\cdot 31

Bekomme ich

(9 \cdot 31) \cdot - 87 + (8 \cdot 31) \cdot 98 = 31

Heißt eine Lösung ist

x = 279

und

y = 248

.

Wie gebe ich nun mathematisch korrekt die ganze Lösungsmenge an? Ich habe jetzt ja nur eine und anscheinend gibt es mehrere laut Aufgabenstellung :-)

michaL aktiv_icon

11:51 Uhr, 31.07.2017

Hallo,

sorry, ich habe gestern abend keine Zeit mehr gefunden.

> Habe nun raus 9·(-87) + 8·98 =1

Gut. Das habe ich auch.

> Bekomme ich
>
> (9⋅31)⋅−87+(8⋅31)⋅98=31

Nicht so schnell. Ich würde erst einmal die volle Lösungsgesamtheit von (III) erarbeiten:

87 x + 98 y = 1

(III)

Du hast nun:
> 9·(-87) + 8·98 =1

Die beiden kannst du zusammenbasteln:

87 x + 98 y = 1 = - 87 \cdot 9 + 98 \cdot 8

bzw.

87 x + 98 y = - 87 \cdot 9 + 98 \cdot 8

(IV)

Erkennst du, wie du (IV) umstellen musst, um die Lösungsgesamtheit von (III) zu erhalten?

Mfg Michael

EmreCabber aktiv_icon

12:08 Uhr, 31.07.2017

Kein Problem und leider nein..
Löse ich nach

X

und

Y

jeweils auf bekomme ich eine Lösungsmenge, welche nicht in

Z

liegt.

Und etwas anderes erkenne ich leider auch nicht

: - (

michaL aktiv_icon

12:18 Uhr, 31.07.2017

Hallo,

ups, mir fällt gerade auf, dass ich mich korrigieren muss. Der Gleichung (III) fehlt ein Minuszeichen. (Geht leicht mal verloren. Es spielt keine essentielle Rolle, macht aber vieles einfacher!)

- 87 x + 98 y = 1

(III)

Daraus resultiert, dass (IV) ebenfalls ein Minuszeichen spendiert bekommen muss:

- 87 x + 98 y = - 87 \cdot 9 + 98 \cdot 8

(IV)

Und trotzdem ändert sich (IV) nicht so sehr, als dass man jetzt mehr sähe.
Du hättest auf die Faktoren 87 und 98 achten und diese jeweils auf verschiedenen Seiten sammeln sollen:

98 (y - 8) = 87 (x - 9)

(V)

Fällt dir jetzt auf, wie (V) zur Lösungsgesamtheit von (III) führt?

Mfg Michael

EmreCabber aktiv_icon

12:22 Uhr, 31.07.2017

Ich weiß nicht ob ich ein Brett vor dem Kopf habe oder mein mathematisches Verständnis nicht ausreicht aber leider sehe ich es immer noch nicht..

Je nachdem wie ich umstelle erkenne ich persönlich keinen tieferen Hintergrund dahinter. Sprich wenn ich jetzt noch mit einer der beiden Zahlen teile. Ich erkenne nur das wir ein Vielfaches weniger 8 und 9 haben kann damit aber nicht weiterarbeiten, tut mir leid.

michaL aktiv_icon

12:29 Uhr, 31.07.2017

Hallo,

>>

98 (y - 8) = 87 (x - 9)

(V)

nun,
* 87 und 98 sind teilerfremd und
* (V) muss in der Menge der ganzen Zahlen gelöst werden.

Letztere geht wegen ersterem nur, wenn

87 ∣ (y - 8)

und

98 ∣ (x - 9)

gilt.

Oder in Gleichungen ausgedrückt:

87 k = y - 8

und

98 k = x - 9

Wobei

k

natürlich wieder ganzzahlig sein muss.

(Diese letzte Argumentation ist entscheidend. Durch sie reduziert sich die Menge der "freien" Variablen auf das Minimum 1. Und um sie so führen zu können, waren auch alle diese Umformungen nötig. Es ist entscheidend, diese Stelle zu verstehen!)

Alles klar bis hier hin?
Wie sieht die Lösungsmenge von (III) aus?

Mfg Michael

EmreCabber aktiv_icon

13:15 Uhr, 31.07.2017

Ich will ehrlich sein ich Blick da noch nicht ganz durch..

Also weil die beiden Zahlen Teilerfremd sind gilt das, richtig?
Also ich meine aus

〉

98(y−8)=87(x−9)

(V)

machst du ja 87∣(y−8) und 98∣(x−9). Du darfst die

87

und die

98

vertauschen, weil wir oben gezeigt haben das die Gleichung gilt und die beiden Zahlen teilerfremd sind, richtig?

Wenn ich jetzt bei −87x+98y=1 (III) die Zahlen einsetze komme ich ja auf IV und das hast du schon beantwortet, oder seh ich das falsch?

Ich würde jetzt sagen die Lösungsmenge ist:

98 k = y - 8

und

87 k = x - 9

mit

k, x, y

aus Z?

du hast ja raus 87k=y−8 und 98k=x−9 aber sind dann beides die selben lösungsmengen? sorry wenn ich das offensichtliche gerade nicht sehe..

michaL aktiv_icon

13:57 Uhr, 31.07.2017

Hallo,

> Du darfst die 87 und die 98 vertauschen, weil ...

Hm, wenn ich das lese, gewinne ich den Eindruck, dass du nach Abkürzungen suchst, statt zu verstehen.

Vereinfacht sieht (V) ja so aus:

98 a = 87 b

(V-A)
(Grundmenge ist

ℤ

!)

Und nun geht's los: Die Zahl in (V-A) ist sowohl ein Vielfaches von 98 (sieht man an der linken Seite) als auch eines von 87 (sieht man an der rechten Seite). Weil 87 und 98 teilerfremd sind, muss die Zahl also ein Vielfaches vom

kgV (87, 98)

sein, was nur geht, wenn

a

Vielfaches von 87 und

b

entsprechendes (!) Vielfaches von 98 ist.
(Wie gesagt, der entscheidende Punkt! Auf diese Weise kommt das zustande, was du als Vertauschung bezeichnet hast. Es hat aber eine Ursache!)

Es muss also

a = 87 k

und

b = 98 k

für ein

k \in ℤ

gelten.

Wieder zurück zu (V): Es muss also

87 k = y - 8

und

98 k = x - 9

gelten, woraus du

y = 87 k + 8

und

x = 98 k + 9

folgerst. Die Lösungsgesamtheit für (III) ist also

{(98 k + 9, 87 k + k) ∣ k \in ℤ}

.

Setze doch mal in (III) ein und forme um. Vielleicht erzeugt dies ein Aha-Erlebnis.

Mfg Michael

EmreCabber aktiv_icon

15:18 Uhr, 31.07.2017

Glaub mir ich suche keine Abkürzungen hab hier gefühlt

100

Blätter mit Umformungen und Versuchen vollgeschrieben. Aber durch deine letzte Erklärung bin ich auf folgenden Ansatz gekommen:

Lösungsmenge anhand der speziellen Lösung:

- 5133 \cdot 279 + 5782 \cdot 248 = 1829

L = {(279 +

b*k/(ggT(a,b),

248 -

a*k/ggT(a,b)

}

k

aus

Z

L = {(279 - 5782 \cdot \frac{k}{59}, 248 - 5133 \cdot \frac{k}{59}} k

aus

Z

L = {279 - 98 k, 248 - 87 k}

Bei den

+, -

bin ich mir nicht sicher. Was sagst du hierzu? LG und vielen herzlichen Dank für deine Mühen noch mal!

ledum aktiv_icon

18:36 Uhr, 31.07.2017

Wenn du dir unsicher bist warum nicht für das eine oder andere

k

einsetzen?
Gruß ledum

michaL aktiv_icon

21:07 Uhr, 31.07.2017

Hallo,

> L=\{279−98k,248−87k\}

soll die Lösungsmenge für welche Gleichung sein?

> Bei den +,− bin ich mir nicht sicher.
und
> Glaub mir ich suche keine Abkürzungen
passen nicht zueinander.

Bitte folge zuerst dem von mir vorgegebenen Weg. Er führt sicher ans Ziel, selbst wenn es
* nicht der einzige
* noch der kürzeste/einfachste/schnellste
Weg sein mag.
Wenn du ihn sicher beherrschst, kannst du immer noch nach Abkürzungen suchen. Und sicher beherrschen bedeutet vor allem, mit den Vorzeichen sicher zu sein!

Ledum schrieb:
> Wenn du dir unsicher bist warum nicht für das eine oder andere k einsetzen?

Und sogar noch weiter: Wenn du deine "Lösung" einsetzt, muss die Gleichung (welche auch immer, s.o.) immer stimmen, d.h. das

k

wird sich herauskürzen!

Daher noch einmal meine Bitte:
>> Setze doch mal in (III) ein und forme um. Vielleicht erzeugt dies ein Aha-Erlebnis.

Und danach: Ermittle aus der Lösung für (III) eine für (II) (geht ganz einfach und du befandest dich auch in der Nähe davon)!
Anschließend: Ermittle aus der Lösung für (II) eine für (I), also die eigentliche Ausgangsgleichung. (Lass' dich nicht ins Boxhorn jagen!)

Mfg Michael

EmreCabber aktiv_icon

21:30 Uhr, 31.07.2017

Was genau soll ich da nun einsetzen? Ich poste mal hier meinen Ansatz, welcher auch zu deiner Erklärung passt.

- 87 x + 98 y = 1

war ja unsere III

Nach

y

umformen

- 87 x + 98 y = 1 | + 87 x

98 y = 1 + 87 x | : 98

y = 1 + \frac{87}{98} \frac{x}{98}

Nach

x

umformen

- 87 x + 98 y = 1 | - 98 y

- 87 x = 1 - 98 y | : (- 87)

x = 1 - \frac{98}{- 87} \frac{y}{- 87}

Leider noch kein aha Erlebniss.

Sehe nur das

1 + 87 x

durch

98

teilbar sein muss und das

1 - 98 y

durch

- 87

bzw.

87

teilbar sein muss. Dann wäre das doch der kgV? Ab hier komme ich nicht weiter bin aber sehr daran interessiert mit dir/euch eine Lösung zu erarbeiten! Tut mir leid das mein Verständnis nicht so groß ist.

michaL aktiv_icon

13:51 Uhr, 01.08.2017

Hallo,

uff, es ist tatsächlich nicht so einfach mit dir.

Wir hatten:
>>

- 87 x + 98 y = 1

(III)
und
>>

1 = 98 \cdot 8 - 87 \cdot 9

Dafür hatten wir als Lösungsgesamtheit:

{(98 k + 9, 87 k + 8) ∣ k \in ℤ}

, also

x = 98 k + 9

y = 87 k + 8

Nun wollte ich (wie auch Ledum), dass du diese "Lösung" in (III) einsetzt:

- 87 (98 k + 9) + 98 (87 k + 8) = - 87 \cdot 98 k - 87 \cdot 9 + 98 \cdot 87 k + 98 \cdot 8 = \underset{= 0}{\underset{⎵}{98 \cdot 87 k - 87 \cdot 98 k}} + \underset{= 1}{\underset{⎵}{98 \cdot 8 - 87 \cdot 9}} = 1

Aha-Erlebnis könnte das folgende sein: Wenn du eine spezielle Lösung

(x_{0}, y_{0})

für (III) hast, dann ist doch

(x_{0} + 98, y_{0} + 87)

wieder eine Lösung, da beim Ausmultiplizieren

- 87 (x_{0} + 98) + 98 (y_{0} + 87)

einmal der Term

- 87 \cdot 98

und einmal auch der Term

98 \cdot 87

entsteht, die sic ggenseitig aufheben. (Oben schön zu sehen!)
Auf diese Weise kommt auch das "Vertauschen" der Faktoren zustande, dass du in einem oberen posting angemerkt hattest. Erinnerst du dich?

Der Vollständigkeit halber: Die Faktoren zu tauschen ist zwar niemals falsch, liefert aber nicht (immer) den kleinsten "Abstand" zwischen Lösungen. Wie du vielleicht erwartest, ist es das kgV. Da hier aber 98 und 87 teilerfremd sind, ist das kgV gleich dem Produkt und damit passt es wieder.

Und genau das (die Teilerfremdheit) war in einem vorigen posting der Grund, weswegen ich lieber erst die Lösungsgesamtheit von

- 87 x + 98 y = 1

(III)
statt von einer anderen, wie etwa pwmeyer vorschlägt (sofern ich sein posting korrekt überfliege).

1. Hast du dazu noch weitere Fragen?
2. Kannst du denn jetzt aus der Lösungsmenge für (III) die Lösungsmenge für (II) ableiten?
3. Und daraus die Lösungsmenge von (I) ermitteln?

Mfg Michael

EmreCabber aktiv_icon

15:00 Uhr, 03.08.2017

Wieso wurde der Thread geschlossen? Natürlich habe ich Interesse an einer Lösung hatte nur zu tun. Ich werde versuchen heute Abend/morgen das von dir gesagte umzusetzen und mein Ergebnis hier posten. Bitte nicht wieder schließen, danke!

ledum aktiv_icon

12:45 Uhr, 04.08.2017

Hallo
eigentlich solltest du den thread schliessen, du hast nun in mehreren Foren gute antworten bekommen und gehst in keinem wirklich - nach gründlichem Lesen. auf die Antworten wirklich ein.
Dass du etwa im post von

21 : 30

Uhr,

31.07.2017

Brüche schreibst, in Gleichungen mit ganzen Zahlen hat mit den Tips nichts zu tun.
Also hak möglichst bald selbst ab.
Gruß ledum

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

1382338

1381887

	Status: nicht eingeloggt	Noch nicht registriert?