Euklidischer Algorithmus

Neue Frage »

FelNa1109 Auf diesen Beitrag antworten »
Euklidischer Algorithmus
Hi, ich bräuchte Hilfe bei der folgenden Aufgabe:

(a)
Zeigen Sie, mit dem Euklidischen Algorithmus, dass für zwei Zahlen gilt:



(b)
Folgern Sie daraus


(c)
Listen Sie in beiden Fällen und jeweils die Elemente von und ihre Inversen auf (am besten in Tabellen mit dem Inversen der Elemente unter den Elementen).

Meine Ideen:
Ich hab mich bis jetzt an der a) versucht. Da das aber relativ viel ist, werd ichs mal ins erste Kommentar verfrachten, damit das Thema (also die Aufgabenstellung) übersichtlich bleibt. Von daher bitte noch etwas Geduld und Danke für die Hilfe.
Elvis Auf diesen Beitrag antworten »

(a) Die Darstellung des ggT als Summe liefert der "erweiterte" euklidische Algorithmus ( https://de.wikipedia.org/wiki/Erweiterte...her_Algorithmus ), wobei mir die Matrizendarstellung besonders zusagt.
(b) ist eine eine einfache Folgerung und (c) ein kleines Beispiel.
 
 
FelNa1109 Auf diesen Beitrag antworten »

zur (a):

Zu zeigen: für mit Euklidischen Algorithmus.

Nach Satz 3.37 (der Algorithmus in meiner VL) erzeugt der Euklidische Algorithmus eine Folge von Resten definiert durch:



Rest der Division von durch falls , sonst Null.


...sowie eine Folge von Quotienten , sodass wir in jedem Schritt folgende Darstellung erhalten:




Man betrachte nun die Restklassen mod b. Offensichtlich gilt

sowie

sind Vielfache von , nach Hinzufügen/Abziehen von Vielfachen von .

die Restklassen sind Vielfache der Restklassen für

Wir konstruieren nun eine Folge wie folgt:






Führt man nun den euklidischen Algorithmus aus, mit

und


ist nach endlich vielen Schritten also für :

und .

Wir erhalten so noch eine weitere Folge mit




Diese Folge ist gegeben durch





Wir erhalten im letzten (ten) Schritt:



Aussage folgt für und .
Elvis Auf diesen Beitrag antworten »

Ja, das ist die klassische Darstellung. Matrizen gefallen mir besser, weil damit alles sehr durchsichtig auf ein Matrizenprodukt zurückgeführt wird und nicht mit endlichen Folgen von Zahlen operiert wird.
FelNa1109 Auf diesen Beitrag antworten »

Also weiter im Text! Zur (b) hätte ich jetzt glaube ich die eine Richtung, aber bei der anderen haperts leider noch.

zur (b):

""

Sei und . Nach der vorherigen Aufgabe .

. Also
FelNa1109 Auf diesen Beitrag antworten »

Und falls es interessiert (erwarte nicht das das irgendwer hier nachrechnet Augenzwinkern ) hab ich für c) folgendes gemacht:

Vorgehensweise:
1. bestimmen für , dann nach b) nicht invertierbar
2. ist , dann nach a)
Also muss bestimmt werden.












Zweite Tabelle geht analog, bin aber zu faul zum Eintippen.
FelNa1109 Auf diesen Beitrag antworten »

Und hier noch die fehlende Richtung von (b):

""

Sei mit (nennen wir mal (x))

, da gilt:




Einen Repräsentanten von kann man mit dem Euklidischen Algorithmus angewendet auf finden. Dann nach Aufgabe a), also insbesondere Ist nun ein Repräsentant von , so gilt wegen (x) auch


smile
Elvis Auf diesen Beitrag antworten »

c) habe ich selbstverständlich überprüft und für gut befunden.
b) die fehlende Richtung fehlt noch immer ... (ich habe einen elementaren Beweis)
FelNa1109 Auf diesen Beitrag antworten »

Danke das du über die c) geschaut hast, weiß ich zu schätzen! Deinem Wortlaut nehm ich mal an das die andere Richtung von der b) passt, also zu der letzten:

Da bin ich ehrlich gesagt, stark am überlegen... Die enthält doch gerade die invertierbaren Restklassen von . Also z.B. , aber sind dann nicht notwendigerweise und immer teilerfremd? Also und damit auch ?
Elvis Auf diesen Beitrag antworten »

ist schon mal richtig, stimmt auch ... aber wie folgt daraus ?
FelNa1109 Auf diesen Beitrag antworten »

Naja, für hätten wir ja . Das heißt ja, das die sich nur um ganzzahlige Vielfache unterscheiden, also

mit

darauf kann man ja den Euklidischen Alg werfen mit und hat dann:

0.Schritt: also
1.Schritt:




also
Elvis Auf diesen Beitrag antworten »

Das ist nicht hinreichend. Damit hast du nur den trivialen Fall a=1 erwischt. Wenn du weiter arbeiten möchtest, darfst du das gerne tun. Bevor du verzweifelt aus dem Kellerfenster springst, darfst du mich auch um meinen elementaren Beweis bitten ... bis 20:00 bin ich online ...
FelNa1109 Auf diesen Beitrag antworten »

Ok, dann bitte ich einmal höflich um einen elementaren Beweis. Dankeschön smile
Elvis Auf diesen Beitrag antworten »

Dem Antrag wird stattgegeben:

Einerseits
Andererseits
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »