linearkombination - erweiterter euklidischer algorithmus |
| 07.10.2004, 18:07 | CrossKing | Auf diesen Beitrag antworten » | ||
| linearkombination - erweiterter euklidischer algorithmus doch zunächst das beispiel: gegeben seien zwei zahlen a, b element Z. aus diesen beiden zahlen soll zunächst der größte gemeinsame teiler bestimmt werden - kein problem. die bestimmung erfolgt nach dem euklidischen algorithmus: gcd(175, 55) 175 = 3*55 + 10 55 = 5*10 +5 10 = 2*5 damit gilt gcd(175, 55) = 5 no problem bis hierher. nun soll der erweiterte euklidische algorithmus angewandt, die linearkombination gebildet werden: a) 5 = 55 - 5*10 b) 5 = 55 - 5*(175 - 3*55) c) 5 = 16*55 - 5*175 == Linearkombination. nun zu meinen problemen. 1. was sagt mir die linearkombination aus? 2. gleichung a) ist klar, auch wie ich auf gleichung b) komme. ich habe aber KEINE ahnung, woher in gleichung c) die 16 kommt und wie überhaupt beide produkte entstehen - kurz, ich verstehe den letzten schritt nicht. kann mir jemand das rezept zur errechnung der linearkombination so erklären dass es nachvollziehbar ist - damit meine ich keine abbildung des falles mit platzhaltern - sondern die abbildung der (meineserachtens) fehlenden zwischenschritte. danke im voraus uwe |
||||
| 07.10.2004, 18:12 | Thomas | Auf diesen Beitrag antworten » | ||
Hi uwe, der letzte Schritt ist nur eine Umformung des vorletzten Schrittes: b) 5 = 55 - 5*(175 - 3*55) c) 5 = 16*55 - 5*175 == Linearkombination. 5 = 55 - 5*(175 - 3*55) 5 = 55 - 5*175 + 15*55 (einfach ausmultipliziert) 5 = 16*55 - 5*175 (zusammengefasst, die 15*55 und die 55) Gruß, Thomas |
||||
| 07.10.2004, 18:18 | CrossKing | Auf diesen Beitrag antworten » | ||
danke, verstanden! 
und was sagt die linearkombination in zusammenhang mit euklidischen algorithmus und gcd / ggT aus? |
||||
| 08.10.2004, 19:14 | CrossKing | Auf diesen Beitrag antworten » | ||
weiss das niemand? 
|
||||
| 06.01.2005, 19:07 | gast | Auf diesen Beitrag antworten » | ||
Naja, machmal ist es praktisch eine Linearkombination einer Zahl durch die Zahlen zu haben. Wirklich interssant wird es wenn man z.B. Restklassenkörper mit Inversen berechnen will ;-) Also ich geb dir ein Beispiel: Du rechnest ab sofort nur noch mehr mit den Zahlen von 0 bis 6. Alles was drüber geht wird abgesäbelt: 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6 usw. Also 3 + 6 = 2, denn 3 + 6 = 9 = 7 + 2 = 0 + 2 ;-) Gesucht: Was mulitpliziert mit 5 ist 1 ? 5 * 3 = 15 = 1. Aber wie kommt man z.B. bei dem selben Spaß drauf, wenn man von 0 bis 100 rechnet? Da braucht man das dann: ggt(5, 101) = 1 Also 1 = 5 * bla + 101 * blub 101 * blub = 0 * blub, also 1 = 5 * bla. Tadaa... |
||||
| 14.10.2007, 11:50 | nobsi | Auf diesen Beitrag antworten » | ||
Das ist aber nicht richtig. Wenn du im 7er-System rechnest (und in dem befindest du dich ja), dann ist 3+6=12 und nicht 2 Denn: denn 3 + 6 = 9 = 7 + 2 = 10 + 2 =12 |
||||
| Anzeige | ||||
|
|
||||
| 14.10.2007, 12:24 | therisen | Auf diesen Beitrag antworten » | ||
Bitte auf das Datum achten! |
||||
| 12.12.2008, 01:26 | foobar | Auf diesen Beitrag antworten » | ||
Sorry falls das sehr spät kommt, ich will das nur richtig stellen, falls jemand so wie ich noch drüber stolpern sollte. Der Poster unmittelbar über mir hat unrecht und hat auch nicht verstanden worum es dem Poster über ihm überhaupt ging. Es ging nicht um das Rechnen im Siebener System sondern um das Rechnen in dem Körper der 7 er Restklassen. Das heisst man definiert die folgende Äquivalenzrelation: x ~ y :<=> 7 | x-y Somit ist zum Beispiel 0 ~ 7, 1~8, 2~9 aber nicht 1~5. Über den Begriff der Äquivalenzklasse kann man nun die Restklassen definieren, wobei man als Repräsentant meistens die zahl zwischen 0 und 6 wählt. Dabei enthält eine Äquivalenzklasse alle Zahlen die zu ihrem Repräsentanten in Relation stehen, die Äquivalenzklasse von 1, auch geschrieben als [1] enhält z.B. unter anderem 8,15,22. Man kann beweisen dass wenn man eine Primzahl wählt (da wo hier jetzt 7 steht, was offensichtlich eine Primzahl ist) man mit diesen Äquivalenzklassen im Prinzip genauso rechnen kann wie mit ganzen Zahlen. So gilt z.B. [3] + [5] = [8] und eben auch [8] = [1]. Üblicherweise lässt man zwecks Vereinfachung der Notation die Klammern weg nachdem man definiert hat, dass man mit der jeweiligen Restklasse rechnet. Und dann sieht das eben so aus: 3+5 = 1 |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
