Euklidischer Algorithmus |
03.06.2018, 12:43 | FelNa1109 | Auf diesen Beitrag antworten » |
Euklidischer Algorithmus (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. |
||
03.06.2018, 12:57 | 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. |
||
03.06.2018, 13:16 | 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 . |
||
03.06.2018, 14:12 | 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. |
||
03.06.2018, 14:18 | 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 |
||
03.06.2018, 15:36 | FelNa1109 | Auf diesen Beitrag antworten » |
Und falls es interessiert (erwarte nicht das das irgendwer hier nachrechnet ) 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. |
||
Anzeige | ||
|
||
03.06.2018, 15:59 | 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 |
||
03.06.2018, 18:12 | 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) |
||
03.06.2018, 18:35 | 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 ? |
||
03.06.2018, 18:46 | Elvis | Auf diesen Beitrag antworten » |
ist schon mal richtig, stimmt auch ... aber wie folgt daraus ? |
||
03.06.2018, 19:24 | 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 |
||
03.06.2018, 19:35 | 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 ... |
||
03.06.2018, 19:45 | FelNa1109 | Auf diesen Beitrag antworten » |
Ok, dann bitte ich einmal höflich um einen elementaren Beweis. Dankeschön |
||
03.06.2018, 19:48 | Elvis | Auf diesen Beitrag antworten » |
Dem Antrag wird stattgegeben: Einerseits Andererseits |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|