Erweiterter Euklidischer Algorithmus

Erste Frage Aufrufe: 127     Aktiv: 27.04.2021 um 12:01

0
 
 
 
Servus!
 
Kann man hier vielleicht jemand ganz kurz helfen?
 
Ich habe etwas über EEA (Erweiterter-euklidischer-algorithmus) recherchiert und habe bisher folgenden Ansatz:
 
Wir nehmen an die Matrikelnummer m wäre 12 13 14 15 
Somit ist der Rest r = 12131415 mod 1000 = 12131,415
 
>>ggT(2021, 12131,415) = 1
12131,415 = 6*2021 + 5,415
2021 = 373,22253*5,415 
-----------------------
 
5,415 = 12131,415 - 6*2021
....
 
Ab hier bin ich nicht weitergekommen, da ich generell sehr unsicher bin, ob dieser Ansatz überhaupt richtig ist? 
Diese Frage melden
gefragt
inaktiver Nutzer

 

Kommentar schreiben

1 Antwort
1
VO=Vorlesung o.ä.? Dann solltest Du dort nachschauen, und nicht anderswo.
Vorher aber übe etwas mit Division mit Rest. Es geht hier nur um ganze Zahl. Der Rest bei Deinem Beispiel ist 415.
Wenn Du Division mit Rest verstanden hast, erst dann (nicht vorher) geht es zum Eukl. Algorithmus, und wenn Du den verstanden hast (nicht vorher) geht es zum Erweiterten Eukl. Alg. Du hast also vorher noch etwas Stoff aufzuarbeiten. Ohne den ist es nicht sinnvoll diese Aufgabe anzugehen.
Kannst gerne Deine Rechnung vom Eukl. Alg. hier zur Kontrolle posten, dann schauen wir weiter.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 13.32K
 

1
Na, das war ja ein schneller Fortschritt! Prima, alles richtig.   ─   mikn 25.04.2021 um 23:58

1
Vorweg: Ich würde meine Matr-Nr hier nicht posten. Für die Aufgabe reicht ja der Rest r.
Nochmal zu a) und auch zu b): Mit dem EA bestimmt man den ggT. Der stellt sich hier als 1 raus. Es gilt: Es gibt x,y mit \(1=2021\cdot x + 604\cdot y \iff ggT (2021,604)=1\).
D.h. Antwort zu b) wäre: Es geht, weil r und 2021 teilerfremd sind. Es geht aber nicht für beliebiges r (da 2021 keine Primzahl ist).
Dein c) verstehe ich nicht: Wo sind denn konkret weitere Paare x,y mit \(1=2021\cdot x + 604\cdot y \)?
  ─   mikn 26.04.2021 um 12:16

1
Du solltest die Paare konkret(!) angeben. Ich sehe nicht wie das aus Deiner Rechnung gehen soll. Eine Lösung haben wir ja (289,-967) (Vorzeichen nicht vergessen!).
Man kann aber noch weitere finden mit der Umformung
\(1=289\cdot 2021-967\cdot 604 = (289+604\,k)\,2021+(-967-2021\,k)\,604\).
Das geht für jedes \(k\in Z\). Kannst Du damit die in c) gesuchte Lösungsmenge formulieren? \(L=\{(x,y) | \ldots \}\)
  ─   mikn 26.04.2021 um 13:21

1
Die Umformung ist nicht meine Idee, sondern die findet man im Internet in Vorlesungsskripten. Natürlich muss sich das k rausheben, sonst wäre die Umformung ja falsch. Die Umformung ist für alle k richtig (bitte davon überzeugen), so dass für jedes k eine weitere Lösung (x,y) entsteht. Probier mal aus.
Es geht hier nur um die Darstellung 1=...., mit dem EEA haben wir jetzt nichts mehr zu tun.
  ─   mikn 26.04.2021 um 19:55

1
Jetzt weißt Du, dass die Umformung stimmt (ginge ohne TR schneller, einfach ausmultiplizieren). Aber c) ist noch nicht gelöst. Es geht darum x,y zu finden, so dass
\(1=x\cdot 2021+y\cdot 604\). Ein Element der Lösungsmenge haben wir schon, \((289,-967)\). Ich versuche mal anders: Es geht darum, Linearkombinationen zu finden, die 2021 und 604 zur 1 kombinieren - den Begriff kennst Du vielleicht aus der Lin. Alg.
Also, findest Du noch weitere Paare (x,y), die das erfüllen?
  ─   mikn 26.04.2021 um 22:30

1
Nein, formal nicht in Ordnung. Hab ja weiter oben schon den Anfang mit L=... vorgegeben, schau da nochmal nach.   ─   mikn 26.04.2021 um 23:22

1
Aha, geht doch!   ─   mikn 26.04.2021 um 23:36

Danke, Meine Geduld ist hier gar nicht so sehr strapaziert worden, da es ja schnelle Fortschritte gab.
Da ich mir diesen Trick für c) selbst aus dem Internet gesucht habe, bin ich nicht 100%ig sicher, dass es nicht noch andere (x,y) als die oben in L beschriebenen gibt. Heißt, ich hab keinen Beweis dafür gefunden, dass das alle sind. Ich gehe aber davon aus, DASS es alle sind (Intuition) und daher müsste das obige L die vollständige Antwort zu c) sein.
  ─   mikn 27.04.2021 um 00:24

Danke, interessant, auf der verlinkten Seite steht auch der Beweis, dass unsere Lösungsmenge richtig ist (d.h. es gibt keine weiteren Lösungen). Und die Umformulierung des Profs klingt so, als wäre er auch nicht ganz sicher. Vermutlich findet er den link dann auch interessant ;-)   ─   mikn 27.04.2021 um 12:01

Kommentar schreiben